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

A - Sieve of Erato67henes#

关键词：签到

Code#

1
// Problem: CF 2195 A
2
// Contest: Codeforces - Codeforces Round 1080 (Div. 3)
3
// URL: https://codeforces.com/contest/2195/problem/A
4
// Time: 2026-05-08 14:17:57
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

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

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

30
    bool fl = false;
31

32
    for (int i = 0; i < n; i++)
33
    {
34
        int x;
35
        cin >> x;
36
        if (x == 67)
37
            fl = true;
38
    }
39

40
    if (fl)
41
        cout << "YES" << endl;
42
    else
43
        cout << "NO" << endl;
44
}
45

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

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

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

56
    return 0;
57
}

B - Heapify 1#

关键词：模拟

思路#

由于只能交换下标为 $2$ 倍关系的数，所以可交换的次数其实不多。暴力即可。

Code#

1
// Problem: CF 2195 B
2
// Contest: Codeforces - Codeforces Round 1080 (Div. 3)
3
// URL: https://codeforces.com/contest/2195/problem/B
4
// Time: 2026-05-08 15:19:19
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

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

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

30
    vector<int> a(n + 1);
31
    for (int i = 1; i <= n; i++)
32
        cin >> a[i];
33

34
    for (int i = 1; i <= n; i++)
35
        for (int j = i; j <= n; j *= 2)
36
            for (int k = i * 2; k <= n; k *= 2)
37
                if (a[k / 2] > a[k])
38
                    swap(a[k / 2], a[k]);
39

40
    if (is_sorted(all(a)))
41
        cout << "YES" << endl;
42
    else
43
        cout << "NO" << endl;
44
}
45

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

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

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

56
    return 0;
57
}

C - Dice Roll Sequence#

关键词：思维，贪心

思路#

注意到两个整数位于相邻面，当且仅当 $s \neq t$ 并且 $s+t \neq 7$ 。并且注意到对于任意的两个面，总存在第三个面和两者均相邻。

考虑遍历 $a_i$ ，如果 $a_i + a_{i + 1} = 7$ 或 $a_i = a_{i + 1}$ ，就一定要有一个值被修改，如果修改 $a_i$ ，后续的 $a_{i + 1}$ 和 $a_{i + 2}$ 可能还有问题，根据上面的结论，我们修改中间的 $a_{i + 1}$ 即可。可以把 $a_{i+1}$ 改成 $0$ 表示已修改，也可以 i++ 跳过。

Code#

1
// Problem: CF 2195 C
2
// Contest: Codeforces - Codeforces Round 1080 (Div. 3)
3
// URL: https://codeforces.com/contest/2195/problem/C
4
// Time: 2026-05-08 16:25:33
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

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

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

30
    vector<int> a(n);
31

32
    for (int i = 0; i < n; i++)
33
        cin >> a[i];
34

35
    int res = 0;
36
    for (int i = 1; i < n; i++)
37
    {
38
        if (a[i - 1] + a[i] == 7 || a[i - 1] == a[i])
39
            res++, i++;
40
    }
41

42
    cout << res << endl;
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
}

D - Absolute Cinema#

关键词：数学，推公式，差分

思路#

NOTE
对于绝对值函数求和的式子，可以从数学的角度看。
对于这样的函数 $f(x) = \sum a_i \cdot |x - i|$ ，一阶导数是斜率，在 $x = i$ 处突变。对于 $y = |x - i|$ ，除了 $x=i$ 这个“拐点”之外，其他所有地方的二阶导数都是 $0$ 。只有在 $x=i$ 处，斜率从 $-1$ 瞬间跳变到 $1$ （变化量为 $2$ ）。
既然我们想求 $a_x$ ，我们只需要对 $f(x)$ 求二阶导数。因为在 $x$ 这个点，其他所有的项 $a_i \cdot |x - i|$ ( $i \neq x$ ) 的二阶导数都是 $0$ ，只有 $a_x \cdot |x - x|$ 在这里会暴露出 $2a_x$ 的值。
而一阶导数对应一维差分，二阶导数对应二维差分，因此对 $f(x)$ 做两次差分就能提取 $a_x$ 。
首尾两项比较特殊，需要单独求解。

Code#

1
// Problem: CF 2195 D
2
// Contest: Codeforces - Codeforces Round 1080 (Div. 3)
3
// URL: https://codeforces.com/contest/2195/problem/D
4
// Time: 2026-05-12 17:42:57
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 = 3e5 + 10;
25

26
ll a[N], res[N];
27

28
void solve()
29
{
30
    ll n;
31
    cin >> n;
32

33
    for (int i = 1; i <= n; i++)
34
        cin >> a[i];
35

36
    for (int i = 1; i <= n - 2; i++)
37
        res[i + 1] = (a[i] - a[i + 1] - (a[i + 1] - a[i + 2])) / 2;
38

39
    ll sum1 = 0, sum2 = 0;
40
    for (int i = 2; i < n; i++)
41
    {
42
        sum1 = sum1 + (n - i) * res[i];
43
        sum2 = sum2 + (i - 1) * res[i];
44
    }
45

46
    cout << (a[n] - sum1) / (n - 1) << " ";
47

48
    for (int i = 2; i < n; i++)
49
        cout << res[i] << " ";
50

51
    cout << (a[1] - sum2) / (n - 1) << endl;
52
}
53

54
int main()
55
{
56
    fastio();
57

58
    int T = 1;
59
    cin >> T;
60

61
    while (T--)
62
        solve();
63

64
    return 0;
65
}

E - Idiot First Search#

关键词：树形DP，dfs

思路#

Step 1 - 完整遍历一个空子树的代价#

首先我们先不考虑起点，假设 Bob 按照规则，从父节点正常进入了一个完全空白的子树 $u$ ，模拟一下他的流程。

他会给 $u$ 写上 ‘L’，然后进入左子树。
左子树也是空白的，他会把左子树完整遍历一遍，最终退回到 $u$ 。
此时 $u$ 上是 ‘L’，他改成 ‘R’，进入右子树。
右子树完整遍历后，再次退回到 $u$ 。
此时 $u$ 上是 ‘R’，他擦除掉，退回到 $u$ 的父节点。

我们发现，当他完整遍历完一个子树并退出时，这个子树里的所有节点都会恢复成初始的空白状态。

那么遍历整个子树 $u$ 并退回父节点，总共需要多少步（秒）？每经过一条边（向下或向上）都需要 1 秒。在一棵大小为 $sz[u]$ 的子树中，共有 $sz[u]-1$ 条边。每条边都会走两遍，再加上最初进入 $u$ 和最后离开 $u$ 的 2 步，总时间为： $T(u) = 2 \times sz[u]$

Step 2 - 从起点第一次到父节点的代价#

现在考虑 Bob 的起点是 $k$ ，它会先遍历完左子树，再遍历完右子树，最后走向父节点。

总代价为： $2 \times sz[k.left] + 2 \times sz[k.right] + 1$ 。由于 $sz[k] = sz[k.left] + sz[k.right] + 1$ ，因此对于任意的起点 $k$ ，Bob 需要消耗 $U(k) = 2 \times sz[k] - 1$ 的代价走到起点 $k$ 的父节点。

TIP
注意：当 Bob 离开 $k$ 节点到达父节点时， $k$ 节点和它的整棵子树都恢复到了完全空白的状态。

Step 3 - 到达父节点后#

现在 Bob 从 $k$ 到达了父节点 $p$ ，父节点此刻是空白的。根据他的运动规则，应该写下 ‘L’，然后走到左边，遍历完左边整棵子树以后再走到右边，也就是说他会再次走一遍 $k$ ，考虑在 $p$ 节点花费的时间，就是 $2 \times sz[p.left] + 2 \times sz[p.right] + 1 = 2 \times sz[p] - 1$

Step 4 - 推公式#

对于从任意节点 $k$ 出发，Bob 向上“逃脱”的过程就是：

逃出 $k$ 到达 $p_1$ ：耗时 $2 \times sz[k] - 1$
逃出 $p_1$ 到达 $p_2$ ：耗时 $2 \times sz[p_1] - 1$
逃出 $p_2$ 到达 $p_3$ ：耗时 $2 \times sz[p_2] - 1$
直到到达节点 1，逃出节点 1 到达最终目的地 0：耗时 $2 \times sz[1] - 1$ 。

所以，如果以 $dp[k]$ 表示从节点 $k$ 到达节点 $0$ 的总时间，公式为： $dp[k] = \sum_{v \in \text{path}(k \to 1)} (2 \times sz[v] - 1)$

Code#

1
// Problem: CF 2195 E
2
// Contest: Codeforces - Codeforces Round 1080 (Div. 3)
3
// URL: https://codeforces.com/contest/2195/problem/E
4
// Time: 2026-05-13 13:08:58
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
const ll mod = 1e9 + 7;
26

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

32
    vector<int> l(n + 1), r(n + 1);
33
    for (int i = 1; i <= n; i++)
34
        cin >> l[i] >> r[i];
35

36
    vector<ll> sz(n + 1, 0);
37

38
    // 计算每个节点子树大小
39
    auto dfs = [&](auto &self, int u) -> void
40
    {
41
        sz[u] = 1;
42

43
        if (l[u])
44
        {
45
            self(self, l[u]);
46
            sz[u] += sz[l[u]];
47
        }
48

49
        if (r[u])
50
        {
51
            self(self, r[u]);
52
            sz[u] += sz[r[u]];
53
        }
54
    };
55

56
    dfs(dfs, 1); // 注意实际能遍历的根节点还是 1
57

58
    vector<ll> dp(n + 1, 0);
59

60
    // 自顶向下计算路径前缀和 dp[u]
61
    auto dfss = [&](auto &self, int u, ll cur) -> void
62
    {
63
        ll t = (2 * sz[u] - 1) % mod;
64
        dp[u] = (cur + t) % mod;
65

66
        if (l[u])
67
            self(self, l[u], dp[u]);
68
        if (r[u])
69
            self(self, r[u], dp[u]);
70
    };
71

72
    dfss(dfss, 1, 0);
73

74
    for (int i = 1; i <= n; i++)
75
        cout << dp[i] << " ";
76

77
    cout << endl;
78
}
79

80
int main()
81
{
82
    fastio();
83

84
    int T = 1;
85
    cin >> T;
86

87
    while (T--)
88
        solve();
89

90
    return 0;
91
}