Codeforces Round 1102 (Div. 2)

A. Euclid, Sequence and Two Numbers

大致题意

定义一种特殊的序列，满足 $\forall 1 \leq i \leq n - 2, a_{i+2} = a_i \space mod \space a_{i+1}$

现在给出一个数组，确认其是否满足

思路

注意到：我们只需要检查一下数组是否满足就行

AC code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void solve() {
    int _;
    cin >> _;
    for (int ts = 0; ts < _; ++ts) {
        int n;
        cin >> n;
        vector<int> v(n);
        for (int i = 0; i < n; ++i) cin >> v[i];
        sort(v.begin(), v.end(), greater<int>());
 
        bool flag = true;
        for (int i = 0; i < n - 2; ++i) flag &= v[i] % v[i + 1] == v[i + 2];
        if (flag) cout << v[0] << ' ' << v[1] << endl;
        else cout << -1 << endl;
    }
}

B. Palindrome, Twelve and Two Terms

大致题意

给出一个 $n$，要求找到两个数字 $a, b$，满足: $a$ 为回文串，$b$ 为 $12$ 的 $x$ 倍

思路

注意到：$1, 2, 3 \dots 9, 11$ 就是回文串，而一个数去掉一个 $12$ 的倍数的数字后，必定是 $1, 2, 3 \dots 11$

我们可以注意到其中只有 $10$ 不满足回文，其他数字均满足回文，所以如果 $n = 12x + y, y \in \left { 1, 2, 3, \dots 9, 11 \right } $

我们直接把 $b$ 设置为最大可能值，即 $n % 12$ 的结果为 $a$ 即可

接下来讨论 $y = 10$ 的情况，显然，如果我们可以从 $b$ 让一个 $12$ 出来，我们就可以得到 $22$ 这个回文串。所以仅当 $n = 10$ 的时候无解

AC code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#define int long long
 
void solve() {
    int _;
    cin >> _;
    for (int ts = 0; ts < _; ++ts) {
        int n;
        cin >> n;
        if (n == 10) {
            cout << -1 << endl;
        } else if (n % 12 != 10) {
            const int x = n / 12;
            cout << n - x * 12 << ' ' << x * 12 << endl;
        } else {
            const int x = n / 12 - 1;
            cout << n - x * 12 << ' ' << x * 12 << endl;
        }
    }
}

D. XOR, Expression and Two Binary Numbers

大致题意

有 $2^k + 1$ 个数组 $a$，其中第 $1, 2^k + 1$ 两个值已知，其他值未知

剩余值可以通过如下公式算出：如果 $a_i, a_j$ 已知，则 $a_{\frac{i + j}{2}} = a_i XOR a_j$

接下来定义 $x_i$ 为 $a_i$ 这个数值在二进制上，$1$ 的数量，同样的 $y_i$ 为 $0$ 的数量（注意，固定二进制长度为 $n$，即有可能存在前导 0）

问 $\sum_{i=1}^n x_i \times y_i$ 是多少

思路

$XOR$ 运算的性质考察：$A XOR A = 0$，所以我们定义最开始的两个值分别为 $A, B$，那么他们异或结果为 $C = A \space XOR \space B$

那么 $A \space XOR \space B = C$, $A \space XOR \space C = B$, $B \space XOR \space C = A$

那么当 $k = 1$ 时，数组为：$A, C, B$
当 $k = 2$ 时，数组为 $A, B, C, A, B$
当 $k = 3$ 时，数组为 $A, C, B, A, C, B, A, C, B$

以此类推可以发现规律

AC code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#define int long long
 
void solve() {
    int _;
    cin >> _;
    for (int ts = 0; ts < _; ++ts) {
        int n, k;
        cin >> n >> k;
        string a, b, c;
        a.reserve(n);
        b.reserve(n);
        cin >> a >> b;
        c.resize(n);
        for (int i = 0; i < n; ++i) c[i] = a[i] == b[i] ? '0' : '1';
        int ca[2] = {0, 0}, cb[2] = {0, 0}, cc[2] = {0, 0};
        for (int i = 0; i < n; ++i) {
            ++ca[a[i] - '0'];
            ++cb[b[i] - '0'];
            ++cc[c[i] - '0'];
        }
        int va = 0, vb = 0, vc = 0;
        va = ca[0] * ca[1];
        vb = cb[0] * cb[1];
        vc = cc[0] * cc[1];
 
        if (k & 1) cout << ((2LL << (k - 1)) + 1) / 3 * (va + vb + vc) << endl;
        else cout << va + vb + (va + vb + vc) * ((2LL << (k - 1)) - 1) / 3 << endl;
 
    }
}

F. Vessels, Heights and Two Versions (Hard Version)

大致题意

有一个 $n$ 个柱子组成的一个环形的接水容器，现在要求计算：要求某两个相邻的柱子之间没有水，整个容器最多可以承接多少水

思路

首先，观察数据量，显然这道题至少需要在 $O(n log n)$ 时间内，完成 $n$ 个数据计算，那么可以得到，只有两种可能：

  1. 纯离线计算出所有结果
  2. 前一个数据可以通过一定代码推导至下一个结果，且耗时不超过 $O(log n)$

显然看起来 2 方案更可靠一些，我们需要往这个方向考虑。

首先环状的柱子理解较为困难，实际上我们可以考虑将其拆开：沿着不允许有水的两根柱子之间的位置剪开后，可以得到一个水平的柱子图

由于恰好这两个边缘的柱子虽然本来相邻，但是因为他们中间不允许有水，那么其实问题就变成了：

  • 计算当前的水平柱子群能最多维持多少水不往两侧流出（两侧其实就是那个不允许的装水的两个柱子之间的部分）
  • 将第一个柱子挪到最后，重新计算

单独计算一次（独立一次计算）非常容易，就像普通的接雨水那样做就行，那么显然，我们需要计算清楚：

  • 第一个柱子移开后，会导致多少水丢失
  • 第一个柱子放到最后后，会带来多少水

接下来是关于这个问题的一些重要的分析思路

柱子贡献

我们需要计算每一根柱子的贡献，我们有两种方式，以下面的例子为例

方案一：

柱高: 5 3 1 5
水高: 5 5 5
贡献: 9 5 1 0

方案二：

柱高: 5 3 1 5
水高: 5 5 5
贡献: 15 0 0 0

显然方案二下，计算贡献更简单，且适合单调数列来完成计算，但是每次移动柱子则需要更多的计算成本：即还原回方案一

而方案一的计算代价则较大。我选择了方案二进行计算

单调数组

所有的水池会呈现一种抛物曲线形状，例如：$123454321$ 的两端矮，中间高的情况。所以我们在计算的过程中，必然需要从原始数组中提取双向的单调数组

显然，我们取最高的那一个（如果有多个则任取其一）作为固定的点：
左边采用递增数组，右边使用递减数组，就可以很好的维护当前的水位——对于单调数组的每两项相邻值
使用这两个值的下标之差 $\times$ 两个值中的较小者，就是这块维护起来的水池

偏移法

首先，显然，计算每次需要解散、新增的水池，需要做两个事情：计算高度、计算距离。

  • 距离非常容易，即相邻单调数组的相邻两个值的下标差。
  • 但是高度却比较难。
    • 虽然看起来，在单调数组内，我们直接取相邻数据中，较小的那个就行。
    • 但是实际操作中会发现一种情况，即被认为最高的那个柱子发生移动
    • 此时，所有的单调数组就都无效，且需要全部重建：
    • 因为左边肯定已经空了，而右边又突然增加了一个最大的值导致递减数列变成唯一项了（我们的递减数列要求最后一项必须在数组中）

这显然不符合简单设计原则，我的做法是：考虑到循环问题，我们直接将数组拷贝一份，将原来的 $n$ 长度的数组变为 $2n$ 长度，这样循环的过程，就变成了在这个 $2n$ 上截取一度 $n$ 长度的内容，每次移动及将窗口右移一格

同样的，我们可以直接强制设定初始的 $n$ 为 $i \to j$，其中 $j$ 为最大值的下标，这样我们就不存在将这个最大值进行挪动了：它开始在最后面，结束在最前面，恰好完成一轮答案计算

那么我们可知：所有数据最开始都在左边的递增单调数组，右边的为空数组

还原贡献

柱高: 5 3 1 5
水高: 5 5 5
贡献: 15 0 0 0

回到刚刚这个问题，我们还需要解决一个事情是：如何在将 $5$ 移动到最后的过程中，正确还原 $3$、$1$ 的贡献：

这个办法就在最初构建左侧的单调数组的过程中：因为当 $5$ 加入的时候 $3$ 被移除。我们只需要记录这个移除的事件，当 $5$ 被移除的时候，还原这些被移除的值就行。

而因为我们选择了方案二，贡献计算非常简单：当 $3$ 被移回的时候，左边的数组变成 $3(index: 1), 5(index: 3)$，那么可以直接用最小高度 $\times$ 下标差来实时计算贡献

AC code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
#define int long long
 
void solve() {
    int _;
    cin >> _;
    for (int ts = 0; ts < _; ++ts) {
        int n;
        cin >> n;
        vector<int> data(n);
        for (int i = 0; i < n; ++i) cin >> data[i];
        int max_index = 0;
        for (int i = 1; i < n; ++i) max_index = data[i] >= data[max_index] ? i : max_index;
        max_index += max_index == n - 1 ? 0 : n;
        vector<int> l, r, ans(n);
        vector<list<int>> pops(n);
        l.reserve(n);
        r.reserve(n);
 
        auto c_len = [&](int x, int y) {
            x %= n;
            y %= n;
            if (y > x) return y - x;
            else return y - x + n;
        };
 
        // push left
        int cur = 0;
        for (int i = max_index - 1, j = 1; j < n; --i, ++j) {
            while (!l.empty() && data[i % n] > data[l.back() % n]) {
                const int p = l.back();
                pops[i % n].push_back(p);
                l.pop_back();
                const int hei = data[p % n];
                const int len = c_len(p, l.empty() ? max_index : l.back());
                cur -= hei * len;
            }
 
            const int hei = data[i % n];
            const int len = c_len(i, l.empty() ? max_index : l.back());
            cur += hei * len;
            l.push_back(i);
        }
        ans[(max_index + 1) % n] = cur;
        for (int i = max_index + 1 - n, j = 1; j < n; ++i, ++j) {
            // remove l
            l.pop_back();
            int hei = data[i % n];
            int len = c_len(i, l.empty() ? max_index : l.back());
            cur -= hei * len;
 
            // add pops
            for (auto iter = pops[i % n].rbegin(); iter != pops[i % n].rend(); ++iter) {
                hei = data[*iter % n];
                len = c_len(*iter, l.empty() ? max_index : l.back());
                cur += hei * len;
                l.push_back(*iter);
            }
 
            // add r
            while (!r.empty() && data[r.back() % n] < data[i % n]) {
                const int p = r.back();
                r.pop_back();
                hei = data[p % n];
                len = c_len(r.empty() ? max_index : r.back(), p);
                cur -= hei * len;
            }
 
            hei = data[i % n];
            len = c_len(r.empty() ? max_index : r.back(), i);
            cur += hei * len;
            r.push_back(i % n + n);
            ans[(i + 1) % n] = cur;
        }
 
        for (int i = 0; i < n; ++i) cout << ans[i] << " \n"[i == n - 1];
    }
}
ACM&算法
#ACM #Codeforces
Codeforces Round 1102 (Div. 2)
https://blog.mauve.icu/2026/06/13/acm/codeforces/CodeforcesRound1102/
作者
Shiroha
发布于
2026年6月13日
许可协议