NOTE
比赛链接：Codeforces Round 1102.(Div. 2)

A - Euclid, Sequence and Two Numbers#

关键词：数学，思维

思路#

我们需要找到满足欧几里得算法的排列方式的性质。

对于任意两个正整数 $u,v$ ，余数满足： $0\leq u\bmod v<v$ 。

题目要求序列中的每一个数都是正整数，因此余数不能为 $0$ 。于是： $0<a_{i+2}<a_{i+1}$ 。

这意味着： $a_2>a_3>a_4>\cdots>a_n$ 。

同时，题目要求： $a_1=x\geq y=a_2$ ，因此，合法序列必然满足： $a_1\geq a_2>a_3>\cdots>a_n$ 。

当 $n\geq 3$ 时，实际上 $a_1$ 也必须严格大于 $a_2$ 。否则，如果 $a_1=a_2$ ，那么： $a_1\bmod a_2=0$ 。

但 $a_3$ 必须是正整数，所以，当 $n\geq 3$ 时： $a_1>a_2>a_3>\cdots>a_n$ 、

因此满足要求的合法序列一定是严格递减的，只需要将给定数组递减排序，检查每对三元组是否成立即可。

Code#

1
// Problem: CF 2234 A
2
// Contest: Codeforces - Codeforces Round 1102 (Div. 2)
3
// URL: https://codeforces.com/contest/2234/problem/A
4
// Time: 2026-06-07 22:35:09
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
    vector<ll> a(n);
32
    for (auto &x: a)
33
        cin >> x;
34

35
    sort(all(a), greater<ll>());
36

37
    for (int i = 0; i + 2 < n; ++i)
38
    {
39
        if (a[i] % a[i + 1] != a[i + 2])
40
        {
41
            cout << -1 << endl;
42
            return;
43
        }
44
    }
45

46
    cout << a[0] << " " << a[1] << endl;
47
}
48

49
int main()
50
{
51
    fastio();
52

53
    int T = 1;
54
    cin >> T;
55

56
    while (T--)
57
        solve();
58

59
    return 0;
60
}

B - Palindrome, Twelve and Two Terms#

关键词：模拟

思路#

从最接近 $n$ 的 $b$ 值开始模拟即可，虽然还有 $O(1)$ 的解法，但这种解法也是可以通过的。

Code#

1
// Problem: CF 2234 B
2
// Contest: Codeforces - Codeforces Round 1102 (Div. 2)
3
// URL: https://codeforces.com/contest/2234/problem/B
4
// Time: 2026-06-07 22:51:38
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
    ll n;
29
    cin >> n;
30

31
    auto check = [&](ll a) -> bool
32
    {
33
        string s = to_string(a);
34
        string ss = s;
35
        reverse(ss.begin(), ss.end());
36

37
        return ss == s;
38
    };
39

40
    for (ll b = n / 12 * 12; b >= 0; b -= 12)
41
    {
42
        ll a = n - b;
43

44
        if (check(a))
45
        {
46
            cout << a << " " << b << endl;
47
            return;
48
        }
49
    }
50

51
    cout << -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
}

C - Vessels, Heights and Two Versions (Easy Version)#

关键词：图论建模，并查集（DSU）

思路#

假设要求容器 $r$ 保持为空，即 $w_r=0$ ，现在考虑另一个容器 $v$ ，最多能装多少水？

从 $v$ 出发，沿着某条路径 $P$ 走向 $r$ ，假设路径上的隔板高度依次为 $h_{e_1},h_{e_2},\ldots,h_{e_k}$ ，令路径上的最高隔板为 $H=\max_{e \in P} h_e$ 。显然沿着 $P$ 路径可以达到的水位最大是 $H$ ，但 $v \to r$ 不一定只有 $P$ 一条路径，只要存在一条较容易被水流打通的路径，就足以限制 $v$ 的水位。因此： $d_r(v)=\min_{P:v \to r}\left(\max_{e \in P} h_e\right)$ 。我们需要最小化路径最大值，这个答案就是最终容器 $v$ 的最大水位。

此外，可以证明每个容器都取最大值是仍然合法的。

我们考虑使用并查集计算每个容器的答案，首先将所有连接口按照高度从小到大排序。一开始，不加入任何边，每个容器都是一个独立的连通块。随后依次加入高度为 $H$ 的边，并合并边两端的联通块。

当某个容器第一次与空容器 $r$ 连通时，当前处理的高度 $H$ 就是该容器的答案。

原因是：

此时存在一条从该容器到 $r$ 的路径，路径上所有边的高度都不超过 $H$ ；

在处理高度小于 $H$ 的边时，它还无法与 $r$ 连通；

所以能够打通它们的最小瓶颈高度恰好为 $H$ 。

此外，并不需要逐个记录容器答案。假设处理高度为 $H$ 的边时，一侧的连通块已经包含空容器 $r$ ，另一侧不含 $r$ ，大小为 $s$ ，合并后，另一侧连通块中的 $s$ 个容器第一次与 $r$ 连通，因此这 $s$ 个容器的最大水位全部为 $H$ ，答案增加 $H \times s$ 。

Code#

1
// Problem: CF 2234 C
2
// Contest: Codeforces - Codeforces Round 1102 (Div. 2)
3
// URL: https://codeforces.com/contest/2234/problem/C
4
// Time: 2026-06-07 23:03:39
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> fa;
29
    vector<int> sz;
30

31
    DSU()
32
    {
33
    }
34

35
    DSU(int n)
36
    {
37
        init(n);
38
    }
39

40
    void init(int n)
41
    {
42
        fa.resize(n + 1);
43
        sz.assign(n + 1, 1);
44

45
        iota(fa.begin(), fa.end(), 0);
46
    }
47

48
    int find(int x)
49
    {
50
        if (fa[x] == x)
51
            return x;
52

53
        return fa[x] = find(fa[x]);
54
    }
55

56
    bool merge(int x, int y)
57
    {
58
        x = find(x);
59
        y = find(y);
60

61
        if (x == y)
62
            return false;
63

64
        if (sz[x] < sz[y])
65
            swap(x, y);
66

67
        fa[y] = x;
68
        sz[x] += sz[y];
69

70
        return true;
71
    }
72

73
    bool connected(int x, int y)
74
    {
75
        return find(x) == find(y);
76
    }
77

78
    int sze(int x)
79
    {
80
        return sz[find(x)];
81
    }
82
};
83

84
struct Edge
85
{
86
    int u, v;
87
    ll h;
88

89
    bool operator<(const Edge &other) const
90
    {
91
        return h < other.h;
92
    }
93
};
94

95
void solve()
96
{
97
    int n;
98
    cin >> n;
99

100
    vector<Edge> edges;
101

102
    for (int i = 1; i <= n; i++)
103
    {
104
        ll h;
105
        cin >> h;
106

107
        int j = i % n + 1;
108
        edges.push_back({i, j, h});
109
    }
110

111
    sort(all(edges));
112

113
    vector<ll> res(n + 1);
114

115
    for (int i = 1; i <= n; i++)
116
    {
117
        DSU dsu(n);
118
        ll sum = 0;
119

120
        for (auto [u, v, h]: edges)
121
        {
122
            int fu = dsu.find(u), fv = dsu.find(v);
123
            if (fu == fv)
124
                continue;
125

126
            int root = dsu.find(i);
127

128
            if (fu == root)
129
                sum += h * dsu.sz[fv];
130
            else if (fv == root)
131
                sum += h * dsu.sz[fu];
132

133
            dsu.merge(fu, fv);
134
        }
135

136
        res[i] = sum;
137
    }
138

139
    for (int i = 1; i <= n; i++)
140
        cout << res[i] << " \n"[i == n];
141
}
142

143
int main()
144
{
145
    fastio();
146

147
    int T = 1;
148
    cin >> T;
149

150
    while (T--)
151
        solve();
152

153
    return 0;
154
}

A - Euclid, Sequence and Two Numbers#

思路#

Code#

B - Palindrome, Twelve and Two Terms#

思路#

Code#

C - Vessels, Heights and Two Versions (Easy Version)#

思路#

Code#

评论