补题链接
G - 加边
Description
给你一张 $n$ 个点 $m$ 条边的无向图。可能存在重边或自环。问最少加多少边可以使得所有点的度数都为偶数，允许添加重边和自环。
Solution
显然度数为奇数的点的个数是偶数个。所以我们只需要把度数为奇数的点两两相连即可。
关于此结论的证明
因为一条边连接两个点，因此度数之和等于边数的两倍。
则度数为奇数的点必然为偶数个，这样才能使得度数之和为偶数。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| int n, m;
cin >> n >> m;
auto adj = vector(n + 1, vector<int>{});
for (int i = 0; i < m; i++) {
int u, v;
cin >> u >> v;
adj[u].emplace_back(v);
adj[v].emplace_back(u);
}
vector<int> node;
for (int i = 1; i <= n; i++) {
if (adj[i].size() % 2)
node.emplace_back(i);
}
cout << node.size() / 2 << endl;
for (int i = 0; i < node.size(); i += 2) {
cout << node[i] << " " << node[i + 1] << "\n";
}
|
I - 王国——求策
Description
给定 $2n$ 个点，$1 \sim n$ 和 $n+1 \sim 2n$ 的节点之间两两相连。同时每一个节点 $i$ 有且仅有一个「犯冲」的节点 $a_i$，且 $a_i$ 两两不同。给定 $s$ 和 $t$，问是否存在一条路径能联通 $s$ 和 $t$，且路径中任意两个节点之间不犯冲。
Solution
一般地，对于 $n\ge3$ 的情况，总是存在一个节点 $i $ 使得 $i$ 不与 $s$ 犯冲且不与 $t$ 犯冲。因此我们只需要判断 $s$ 是否与 $t$ 犯冲即可。
特别的，当 $n=1$时，显然不可达，当 $n=2$ 时，同侧的节点也不可达。根据如上逻辑编写代码即可。
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
| int T;
cin >> T;
while (T--) {
int n, s, t;
cin >> n >> s >> t;
vector<int> a(2 * n + 1);
for (int i = 1; i <= n; i++) {
cin >> a[i];
a[a[i]] = a[i];
}
if (s == t) {
cout << "Yes\n";
continue;
}
if (n == 2) {
if (s > t)
swap(s, t);
if (s == 1 and t == 2 or s == 3 and t == 4) {
cout << "No\n";
continue;
}
}
if (a[s] == t or a[t] == s)
cout << "No\n";
else
cout << "Yes\n";
}
|
F - 年少的誓约II
Description
给定初始时间 $t_0$ 和时间区间 $[t_1,t_2]$。求最早的时间 $t$ 使得表针从 $t_0$ 转到 $t_1$ 的角度之和最小。
Solution
👋😭👋时针一定要动🖐️😭🖐️
暴力枚举每一个时间点即可。
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
| int T;
cin >> T;
auto in_range = [](auto v, auto l, auto r) { return l <= v and v <= r; };
auto get_close = [](auto s, auto t) {
if (s > t)
swap(s, t);
return min(t - s, s + 720 - t);
};
// 1 hours = 30d because 30 * 12 = 360
// 1 minutes = 6d because 6 * 60 = 360
// but the Delta is that 30 * (m / 60) = m / 2
// so the h angle = 30 * h + m / 2
// so the m angle = 6 * m
// we times 2
while (T--) {
int x0, y0, x1, y1, x2, y2;
cin >> x0 >> y0 >> x1 >> y1 >> x2 >> y2;
int dis = 114514;
int a0, a1;
for (int h = 23; h >= 0; h--) {
for (int m = 59; m >= 0; m--) {
if (not in_range(60 * h + m, 60 * x1 + y1, 60 * x2 + y2))
continue;
int cur = get_close(60 * x0 + y0, 60 * h + m) +
get_close(12 * y0, 12 * m);
if (cur <= dis) {
dis = cur;
a0 = h, a1 = m;
}
}
}
cout << a0 << " " << a1 << "\n";
}
|
K - 微信小游戏
Description
给定一个 $n\times m$ 的矩阵，每格颜色在 ${1,\dots,m}$，并有一个初始颜色为 0 的“额外方块”。允许随时将额外方块染成任意非零颜色（不计次数），然后执行以下一次 “Shift” 操作（计作 1 次）：
- 选一列 $j$，将该列最下面的颜色弹出到额外方块；其余格下移一格；把当前额外方块放到该列最上方。
要求通过最少次 Shift，使得每列都变成一个单一的非零颜色，且 $m$ 列的颜色两两不同。
Solution
在不重复操作的情况下，我们只能把一列染成其最开头的颜色或完全不同的颜色。记录每一种颜色在开头的最大连续次数，答案就是 $n\times m$ 减去各颜色出现在开头的连续次数之和。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| int n, m;
cin >> n >> m;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
cin >> c[i][j];
}
}
int ans = 0;
vector<int> co(m + 1);
for (int i = 1; i <= m; i++) {
int j;
for (j = 1; j <= n; j++) {
if (c[j][i] != c[1][i])
break;
}
j--;
co[c[1][i]] = max(co[c[1][i]], j);
}
for (int i = 1; i <= m; i++) {
ans += n - co[i];
}
cout << ans << endl;
|
A - GD 终极节奏实验室
Description
给定数组 $a$，统计使得 $\min(a_l,a_{l+1},\dots,a_r)=\gcd(a_l,a_{l+1},\dots,a_r)$ 成立的区间 $[l, r]$ 的个数。
Solution
注意到若 $\min(a_l,a_{l+1},\dots,a_r)=\gcd(a_l,a_{l+1},\dots,a_r)$ 成立，记此区间的最小值为 $m$，最大公约数为 $p$，有 $m\equiv p$，可得 $\forall i(l \le i \le r),a_i\equiv0(\bmod p)$，即每个数都是最小值的倍数或等于最小值。
因此我们对于每一个 $a_i$，只需要找到最大的 $l$ 和 $r$，使得 $\forall i(l_i \le j \le r_i),a_j\equiv0(\bmod a_i),a_j\le a_i$ 成立即可。
此时的答案就是 $\sum_{i=0}^{n}(i-l+1)(r-i+1)$。
我们可以利用单调栈，用维护四个单调栈：
la[i] 表示 i 左侧第一个“小于等于 a[i]”的位置，下一个位置 la[i]+1 就是「a[i] 作为最小值」可以延伸到的最左范围。也就是说 i 的最小值限制实际给出了左侧候选： la[i] + 1 。ra[i] 表示 i 右侧第一个「小于 a[i]」的位置，i 作为最小值的合法区间只能延伸到 ra[i]-1。lb[i] 表示 i 左侧第一个「a[j] % a[i] != 0」的位置，那么 i 要能整除左边所有元素，左边界就得从 lb[i]+1 开始。rb[i] 表示 i 右侧第一个「a[j] % a[i] != 0」的位置，i 能整除右边所有元素，右边界就最多到 rb[i]-1。
按此实现即可。
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
| int n;
cin >> n;
vector<int> a(n), la(n), lb(n, -1), ra(n), rb(n, n);
for (int i = 0; i < n; i++) {
cin >> a[i];
}
stack<int> stk;
for (int i = 0; i < n; i++) {
while (not stk.empty() and a[stk.top()] > a[i])
stk.pop();
la[i] = stk.empty() ? -1 : stk.top();
stk.push(i);
}
stk = {};
for (int i = n - 1; i >= 0; i--) {
while (not stk.empty() and a[stk.top()] >= a[i])
stk.pop();
ra[i] = stk.empty() ? n : stk.top();
stk.push(i);
}
stk = {};
for (int i = n - 1; i >= 0; i--) {
while (not stk.empty() and a[i] % a[stk.top()] != 0) {
lb[stk.top()] = i;
stk.pop();
}
stk.push(i);
}
stk = {};
for (int i = 0; i < n; i++) {
while (not stk.empty() and a[i] % a[stk.top()] != 0) {
rb[stk.top()] = i;
stk.pop();
}
stk.push(i);
}
ll ans = 0;
for (int i = 0; i < n; i++) {
int l = max(la[i], lb[i]) + 1;
int r = min(ra[i], rb[i]) - 1;
if (l <= i and i <= r) {
ans += 1ll * (i - l + 1) * (r - i + 1);
}
}
cout << ans << endl;
|
H - 王国——迁移
Description
有 $n$ 组待搬迁的居民，第 $j$ 组有 $b_j$ 人，禁止搬入城市 $a_j$；保留的 $n$ 座城市中第 $i$ 座有“不满系数” $c_i$。每组居民必须分配到一个不冲突的城市上，若城市 $i$ 上最终搬入总人数为 $d_i$，它的“不满度”为 $c_i,d_i$。要求在所有满足“第 $j$ 组不去 $a_j$”的分配方案里，使得各城市中不满度的最大值最小，输出该最小值。
Solution
最小化最大值，显然使用二分答案法。
我们考虑 check 函数的内容，只需要判断在允许每座城市最多接纳 $\lceil x/c[i]\rceil\lceil x/c[i]\rceil$ 人的条件下，能否把所有组都分配到它们允许的城市里即可。
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
| void solve() {
int n;
cin >> n;
vector<int> a(n + 1), b(n + 1), c(n + 1);
for (int i = 1; i <= n; i++)
cin >> a[i];
for (int i = 1; i <= n; i++)
cin >> b[i];
for (int i = 1; i <= n; i++)
cin >> c[i];
auto check = [&](int x) {
vector<int> d(n + 1);
int sumb = 0, sumd = 0;
for (int i = 1; i <= n; i++) {
d[i] = x / c[i];
sumb += b[i], sumd += d[i];
}
for (int i = 1; i <= n; i++) {
if (b[i] > sumd - d[a[i]]) {
return false;
}
}
if (sumb > sumd)
return false;
return true;
};
int lo = 0, hi = 1e18, ans = -1;
while (lo <= hi) {
int mid = (lo + hi) >> 1;
if (check(mid)) {
ans = mid;
hi = mid - 1;
} else {
lo = mid + 1;
}
}
cout << ans << "\n";
}
|