NOTE
比赛链接：Codeforces Round 1072 (Div. 3)

关键词：签到

Code#

1
// Problem: CF 2184 A
2
// Contest: Codeforces - Codeforces Round 1072 (Div. 3)
3
// URL: https://codeforces.com/contest/2184/problem/A
4
// Time: 2026-05-14 22:55:01
5
#include <bits/stdc++.h>
6
using namespace std;
7

8
// clang-format off
9
#define endl '\n'
10
#define all(x) (x).begin(), (x).end()
11
#define fastio() ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
12
// clang-format on
13

14
using ll = long long;
15
using ull = unsigned long long;
16
using pii = pair<int, int>;
17
using pdd = pair<double, double>;
18
using pll = pair<long long, long long>;
19
using i128 = __int128;
20

21
const int dx[] = {-1, 0, 1, 0, -1, 1, 1, -1};
22
const int dy[] = {0, 1, 0, -1, 1, 1, -1, -1};
23
const int inf = 0x3f3f3f3f;
24
const int N = 0;
25

26
void solve()
27
{
28
    int n;
29
    cin >> n;
30

31
    if (n == 2)
32
        cout << 2 << endl;
33
    else if (n == 3)
34
        cout << 3 << endl;
35
    else
36
        cout << n % 2 << endl;
37
}
38

39
int main()
40
{
41
    fastio();
42

43
    int T = 1;
44
    cin >> T;
45

46
    while (T--)
47
        solve();
48

49
    return 0;
50
}

B - Hourglass#

关键词：分类讨论

思路#

题目问的是在第 $m$ 分钟这个瞬间，沙漏的上半部分还剩多少沙子。

我们首先考虑：在翻转之前，沙子能不能全漏完？ 这将问题分成了两大类： $s \le k$ （能漏完/刚好漏完）和 $s > k$ （漏不完）。

当 $s \le k$ 时，在翻转之前沙子就漏光了，因此每次反转都会重置沙漏成上半部分满，下半部分空的初始状态。既然每次反转都会重置，我们就不关心之前翻了多少次，只需要关心当前处于这轮周期的第几分钟，也就是 m % k。初始时上半部分有 $s$ 的沙子，漏了 m % k 分钟，理论上还剩 s - m % k 的沙子。但如果 m % k 已经大于 $s$ 了（说明沙子早就漏光了），剩下的沙子不能是负数，所以是 $0$ 。

当 $s > k$ 时，沙漏的状态会在偶数周期和奇数周期之间变化。对于偶数周期，当周期开始时，上半部分总是有 $s$ 的沙子；对于奇数周期，当周期开始时，上半部分总是有 $k$ 的沙子。我们首先需要计算经历了多少个完整的周期，即 cnt = m / k。在当前周期内度过的时间仍然是 m % k，讨论当前周期的奇偶性，然后拿总数 $k$ 或者 $s$ 减掉 m % k 即可。

NOTE
刚开始考虑的时候，并没有把问题分成这两类，而是统一去考虑奇偶周期了。思维还是不够清晰。

Code#

1
// Problem: CF 2184 b
2
// Contest: Codeforces - Codeforces Round 1072 (Div. 3)
3
// URL: https://codeforces.com/contest/2184/problem/b
4
// Time: 2026-05-15 15:53:27
5
#include <bits/stdc++.h>
6
using namespace std;
7

8
// clang-format off
9
#define endl '\n'
10
#define all(x) (x).begin(), (x).end()
11
#define fastio() ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
12
// clang-format on
13

14
using ll = long long;
15
using ull = unsigned long long;
16
using pii = pair<int, int>;
17
using pdd = pair<double, double>;
18
using pll = pair<long long, long long>;
19
using i128 = __int128;
20

21
const int dx[] = {-1, 0, 1, 0, -1, 1, 1, -1};
22
const int dy[] = {0, 1, 0, -1, 1, 1, -1, -1};
23
const int inf = 0x3f3f3f3f;
24
const int N = 0;
25

26
void solve()
27
{
28
    int s, k, m;
29
    cin >> s >> k >> m;
30

31
    if (s == k) // 可以合并成 s <= k
32
        cout << s - m % k << endl;
33
    else if (s < k)
34
        cout << max(0, s - m % k) << endl;
35
    else
36
    {
37
        int cnt = m / k;
38
        if (cnt % 2)
39
            cout << k - m % k << endl;
40
        else
41
            cout << s - m % k << endl;
42
    }
43
}
44

45
int main()
46
{
47
    fastio();
48

49
    int T = 1;
50
    cin >> T;
51

52
    while (T--)
53
        solve();
54

55
    return 0;
56
}

C - Huge Pile#

关键词：一维BFS

思路#

我们发现一个性质：同一个深度的节点最多只能有两个不同的值，因此整个拆分过程中产生的状态其实很少。大约只有 $2 \times \log_2 N \approx 60$ 个状态。并且我们需要知道到达每种状态的“最小步数”，考虑使用一维BFS求解。

注意：过程中发现 $t < k$ 时剪枝。这道题的 map 类似于记忆化搜索，当我们已经搜过这个状态，就不需要再搜了。

Code#

1
// Problem: CF 2184 C
2
// Contest: Codeforces - Codeforces Round 1072 (Div. 3)
3
// URL: https://codeforces.com/contest/2184/problem/C
4
// Time: 2026-05-16 12:00:31
5
#include <bits/stdc++.h>
6
using namespace std;
7

8
// clang-format off
9
#define endl '\n'
10
#define all(x) (x).begin(), (x).end()
11
#define fastio() ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
12
// clang-format on
13

14
using ll = long long;
15
using ull = unsigned long long;
16
using pii = pair<int, int>;
17
using pdd = pair<double, double>;
18
using pll = pair<long long, long long>;
19
using i128 = __int128;
20

21
const int dx[] = {-1, 0, 1, 0, -1, 1, 1, -1};
22
const int dy[] = {0, 1, 0, -1, 1, 1, -1, -1};
23
const int inf = 0x3f3f3f3f;
24
const int N = 0;
25

26
int n, k;
27

28
int bfs()
29
{
30
    queue<int> q;
31
    map<int, int> dist;
32

33
    q.push(n), dist[n] = 0;
34

35
    while (!q.empty())
36
    {
37
        int t = q.front();
38
        q.pop();
39

40
        if (t == k)
41
            return dist[t];
42

43
        if (t < k)
44
            continue;
45

46
        int ls = t / 2, rs = (t + 1) / 2;
47

48
        if (!dist.count(ls))
49
        {
50
            dist[ls] = dist[t] + 1;
51
            q.push(ls);
52
        }
53
        if (!dist.count(rs))
54
        {
55
            dist[rs] = dist[t] + 1;
56
            q.push(rs);
57
        }
58
    }
59

60
    return -1;
61
}
62

63
void solve()
64
{
65
    cin >> n >> k;
66

67
    cout << bfs() << endl;
68
}
69

70
int main()
71
{
72
    fastio();
73

74
    int T = 1;
75
    cin >> T;
76

77
    while (T--)
78
        solve();
79

80
    return 0;
81
}

D - Unfair Game#

关键词：组合数学，推公式

思路#

考虑一个数变为 $0$ 的最小步数，显然能除以 $2$ 就一定要除以 $2$ ，否则只能减 $1$ 。

对于任意的初始数字，考虑它的二进制形式。每移出一个二进制位（除以 $2$ ），需要 $1$ 步，如果碰到了 $1$ ，需要先把它减成 $0$ 再除以 $2$ ，因此 $f(a) = \text{二进制长度} + \text{二进制中 1 的个数} - 1$ 。

要求我们统计在 $[1, n]$ 中，有多少个数字满足 $f(a) > k$ ，我们将 $[1, 2^d]$ 范围内的数分为两部分：

数字 $a = 2^d$ 本身：

它的长度是 $d+1$ ，包含 1 个 1。所以 $f(n) = (d+1) + 1 - 1 = d+1$ 。

如果 $d+1 > k$ ，答案直接 +1。
数字 $a \in [1, 2^d - 1]$ ：

这些数字的最高位必定在第 $L$ 位（从右往左数，从 1 开始），其中 $L \in [1, d]$ 。
- 对于一个固定的长度 $L$ ，它的最高位必定是 1。
- 剩下的 $L-1$ 个低位，可以是 0 也可以是 1。假设其中有 $p$ 个 1（ $p \in [0, L-1]$ ）。
- 那么这个数字的总 1 个数为 $p+1$ 。
- 根据公式， $f(a) = L + (p+1) - 1 = L + p$ 。

我们要找的是 $L + p > k$ 的数字个数。

因为在一个长度为 $L-1$ 的区域里选出 $p$ 个位置填 1，方案数就是组合数 $C(L-1, p)$ 。

由于 $d$ 比较小，使用杨辉三角递推出组合数即可。

Code#

1
// Problem: CF 2184 D
2
// Contest: Codeforces - Codeforces Round 1072 (Div. 3)
3
// URL: https://codeforces.com/contest/2184/problem/D
4
// Time: 2026-05-16 12:39:16
5
#include <bits/stdc++.h>
6
using namespace std;
7

8
// clang-format off
9
#define endl '\n'
10
#define all(x) (x).begin(), (x).end()
11
#define fastio() ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
12
// clang-format on
13

14
using ll = long long;
15
using ull = unsigned long long;
16
using pii = pair<int, int>;
17
using pdd = pair<double, double>;
18
using pll = pair<long long, long long>;
19
using i128 = __int128;
20

21
const int dx[] = {-1, 0, 1, 0, -1, 1, 1, -1};
22
const int dy[] = {0, 1, 0, -1, 1, 1, -1, -1};
23
const int inf = 0x3f3f3f3f;
24
const int N = 55;
25

26
int c[N][N];
27

28
void init()
29
{
30
    for (int i = 0; i <= 50; i++)
31
    {
32
        c[i][0] = c[i][i] = 1;
33
        for (int j = 1; j < i; j++)
34
            c[i][j] = c[i - 1][j] + c[i - 1][j - 1];
35
    }
36
}
37

38
void solve()
39
{
40
    int n, k;
41
    cin >> n >> k;
42

43
    int d = __lg(n);
44

45
    ll res = 0;
46
    for (int i = 1; i < d; i++)
47
        for (int j = 0; j <= i; j++)
48
            if (i + j + 1 > k)
49
                res += c[i][j];
50

51
    if (d + 1 > k)
52
        res++;
53

54
    cout << res << endl;
55
}
56

57
int main()
58
{
59
    fastio();
60

61
    int T = 1;
62
    cin >> T;
63

64
    init();
65

66
    while (T--)
67
        solve();
68

69
    return 0;
70
}

E - Exquisite Array#

关键词：并查集，离线处理

思路#

首先求一个差分数组，即 $D_i = |p_i - p_{i+1}|$ ，长度为 $n - 1$

现在问题变成了：在数组 $D$ 中，一个连续的子段如果所有元素都 $\ge k$ ，那么它就对应原数组中的一个满足要求的数组。

假设这个连续子段的长度为 $L$ ，这个区间的内部会产生 $\frac{L \times (L + 1)}{2}$ 个合法子段。

TIP
对于某个特定的 $k$ ，我们需要找出 $D$ 数组中所有完全由 $\ge k$ 的元素组成的“连续段”，算出每个连续段长度 $L$ 对应的 $\frac{L(L+1)}{2}$ ，将它们全部累加起来，就是答案。

假设我们从小到大枚举 $k$ 并计算结果，随着 $k$ 的增大，前面已经合法的 $D_i$ 会变得不合法，我们考虑从大到小倒序枚举 $k$ 。

随着 $k$ 的减小，越来越多的 $D_i$ 会变得合法（我们可以把它们看作是一个个被“激活”的节点）。原本断开的连续段，会因为新节点的“激活”而被连接（合并）在一起，使用并查集动态维护联通块。

NOTE
因为我们要计算贡献，当我们激活一个位置 $i$ 时，我们都需要计算包含 $i$ 的这个连续合法区间现在的长度。
因此使用并查集维护连通性和连通块的长度。

完整流程#

预处理：将所有 $D_i$ 的位置，按照值域放进若干个桶里。使用 vector<int> pos[x]，存下所有 $D_i = x$ 的下标 $i$ 。（注意 unordered_map 容易被卡，尽量使用 vector。
初始化并查集和维护变量：维护一个变量 cur 代表当前的合法子段总数。使用 vector<bool> active(n, false) 记录每个差值位置是否被“激活”。
倒序遍历并计算结果。当遍历到某一个 $k$ 时：
1. 拿出 pos[k] 里的所有下标 $i$ 。
2. 将下标 $i$ 标记为“已激活”。它本身形成了一个长度为 $1$ 的连通块，此时 cur 增加 $\frac{1 \times 2}{2} = 1$ 。
3. 检查左邻居 $i-1$ ：如果 $i-1$ 也是“已激活”的，我们就需要把 $i$ 和 $i-1$ 所在的连通块合并。
  
  合并前，我们先从 cur 中减去这两个独立连通块原本的贡献。
  
  合并后，把它们的大小相加得到新的 $L_{new}$ ，再给 cur 加上新连通块的贡献 $\frac{L_{new}(L_{new}+1)}{2}$ 。
4. 检查右邻居 $i+1$ ：同理，如果 $i+1$ 也是“已激活”的，执行相同的合并与贡献更替操作。
5. 把所有的 $i \in pos[k]$ 处理完之后，当前的 cur 就是 $k$ 对应的答案，存入结果数组。

Code#

1
// Problem: CF 2184 E
2
// Contest: Codeforces - Codeforces Round 1072 (Div. 3)
3
// URL: https://codeforces.com/problemset/problem/2184/E
4
// Time: 2026-05-13 22:20:17
5
#include <bits/stdc++.h>
6
using namespace std;
7

8
// clang-format off
9
#define endl '\n'
10
#define all(x) (x).begin(), (x).end()
11
#define fastio() ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
12
// clang-format on
13

14
using ll = long long;
15
using ull = unsigned long long;
16
using pii = pair<int, int>;
17
using pdd = pair<double, double>;
18
using pll = pair<long long, long long>;
19
using i128 = __int128;
20

21
const int dx[] = {-1, 0, 1, 0, -1, 1, 1, -1};
22
const int dy[] = {0, 1, 0, -1, 1, 1, -1, -1};
23
const int inf = 0x3f3f3f3f;
24
const int N = 0;
25

26
struct DSU
27
{
28
    vector<int> parent;
29
    vector<int> sz;
30
    int comp_cnt;
31

32
    DSU(int n)
33
    {
34
        parent.resize(n + 1);
35
        iota(parent.begin(), parent.end(), 0);
36
        sz.assign(n + 1, 1);
37
        comp_cnt = n;
38
    }
39

40
    int find(int i)
41
    {
42
        if (parent[i] == i)
43
            return i;
44
        return parent[i] = find(parent[i]);
45
    }
46

47
    bool unite(int i, int j)
48
    {
49
        int pi = find(i);
50
        int pj = find(j);
51
        if (pi != pj)
52
        {
53
            if (sz[pi] < sz[pj])
54
                swap(pi, pj);
55
            parent[pj] = pi;
56
            sz[pi] += sz[pj];
57
            comp_cnt--;
58
            return true;
59
        }
60
        return false;
61
    }
62

63
    bool connected(int i, int j)
64
    {
65
        return find(i) == find(j);
66
    }
67

68
    int size(int i)
69
    {
70
        return sz[find(i)];
71
    }
72
};
73

74
void solve()
75
{
76
    int n;
77
    cin >> n;
78

79
    vector<int> a(n), d(n - 1);
80
    for (int i = 0; i < n; i++)
81
        cin >> a[i];
82

83
    vector<vector<int>> mp(n);
84
    for (int i = 0; i < n - 1; i++)
85
    {
86
        d[i] = abs(a[i] - a[i + 1]);
87
        mp[d[i]].push_back(i);
88
    }
89

90
    DSU dsu(n);
91
    ll cur = 0;
92

93
    vector<ll> res(n);
94
    vector<bool> active(n, false);
95

96
    auto calc = [](ll sz) { return sz * (sz + 1) / 2; };
97

98
    for (int k = n - 1; k >= 0; k--)
99
    {
100
        for (auto i: mp[k])
101
        {
102
            active[i] = true;
103
            cur += calc(1);
104

105
            if (i > 0 && active[i - 1])
106
            {
107
                ll sz1 = dsu.size(i - 1);
108
                ll sz2 = dsu.size(i);
109

110
                cur -= calc(sz1) + calc(sz2);
111
                dsu.unite(i - 1, i);
112
                cur += calc(dsu.size(i));
113
            }
114

115
            if (i < n - 2 && active[i + 1])
116
            {
117
                ll sz1 = dsu.size(i + 1);
118
                ll sz2 = dsu.size(i);
119

120
                cur -= calc(sz1) + calc(sz2);
121
                dsu.unite(i + 1, i);
122
                cur += calc(dsu.size(i));
123
            }
124
        }
125
        res[k] = cur;
126
    }
127

128
    for (int k = 1; k < n; k++)
129
        cout << res[k] << " ";
130
    cout << endl;
131
}
132

133
int main()
134
{
135
    fastio();
136

137
    int T = 1;
138
    cin >> T;
139

140
    while (T--)
141
        solve();
142

143
    return 0;
144
}

A - Social Experiment#

Code#

B - Hourglass#

思路#

Code#

C - Huge Pile#

思路#

Code#

D - Unfair Game#

思路#

Code#

E - Exquisite Array#

思路#

完整流程#

Code#