补题链接
唉唉，感觉区域赛好难。
去年的 $\texttt{Louisdlee}$ 太强。
C. Conquer the Multiples
这里就放新生赛的题解了。
题目描述
哈基詹与哈基君正在愉快地进行小游戏，规则如下：
- 选定一个正整数连续序列 $[l,,r]$ 和一个正整数变量 $x\gets l$。
- 两名玩家轮流从序列中删除一个能被 $x$ 整除的数 。哈基詹总是先手。每次操作后 $x \gets x + 1$。如果某位玩家当前无法删去这样的数，则该玩家输掉游戏。
显然哈基詹和哈基君都是绝顶聪明的，他们都会以最佳策略进行行动，你能判断出这场别样的数字大战的赢家是谁吗？
题解
首先不难想到对于 $x$ 我们在序列中可以删除的数为 $x,2x,3x,\ldots,nx$，同时有 $x$ 的初始值为 $l$，则当 $r \lt 2l$ 时，我们只能删除 $x$ 本身。这样游戏就变成了轮流取一个数问最后谁没取到的经典问题，有当序列长度为奇数时先手必赢，长度为偶数时先手必败的结论。
然后我们不难发现，若一个人拿到的第一个 $x$ 为偶数，那么此人往后只能选择偶数。而当 $x$ 为奇数时，$2x$ 为偶数，因此若一个人拿到的第一个 $x$ 为奇数，此人在一定条件下也能选择偶数。这样就导致了偶数数量的减少，使得只能选择偶数的那个人少了一个可以选择的数，当 $x \gt \frac{r}{2}$ 时，游戏转变为如上所述的轮流取数的问题，而偶数方因为必然选择的数已经被取走而陷入必败的局面。
因此当 $l$ 为奇数，$r \lt 2l$ 时，区间长度为奇数 Alice 赢，否则 Bob 赢；$r \ge 2l$ 时，则 Alice 一定赢（做法就是开局把 $2l$ 删除）。
当 $l$ 为偶数时，因为 $2l$ 也是偶数，如果开局能把 $2l$ 拿走，则后期必然导致无路可走，因此 Alice 开局只能拿 $l$，问题转换为在 Bob 视角下的以奇数开局：则当 $r\lt2(l+1)$ 时，问题取决于区间长度奇偶性（因为二人都无法拿走任何东西）；$r\ge2(l+1)$ 时则 Bob 必赢。
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
| #include <bits/stdc++.h>
using namespace std;
int main() {
cin.tie(nullptr)->sync_with_stdio(false);
int t;
cin >> t;
while (t--) {
int l, r;
cin >> l >> r;
if (r < 2 * (l + !(l % 2))) { // 这里合并了 l 奇偶不同的判断，偶数则判断 2*(l+1)
if ((r - l + 1) % 2) {
cout << "Alice\n";
} else {
cout << "Bob\n";
}
} else {
if (l % 2) {
cout << "Alice\n";
} else {
cout << "Bob\n";
}
}
}
return 0;
}
|
I. In Search of the Ultimate Artifact
其实比上一题简单。
给定一个数组，每 $k$ 个元素可以合并成一个元素，其值等于这 $k$ 个元素的乘积，问最后数组中最大值是多少。
解法很显然，排序后从第一个元素开始合并往后 $k-1$ 个元素就行，如果有 $0$ 就特判一下，然后需要注意取模的问题……总而言之需要一些细节。
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
| #include <bits/stdc++.h>
using namespace std;
using i64 = long long;
const int MOD = 998244353;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t;
cin >> t;
while (t--) {
int n, k;
cin >> n >> k;
vector<i64> p(n);
for (int i = 0; i < n; i++) cin >> p[i];
sort(p.begin(), p.end(), greater<>()); // 降序排列
i64 cs = p[0] % MOD; // 当前最大值
for (int i = 1; i + k - 2 < n; i += k - 1) {
bool hasZero = false;
i64 tms = 1;
for (int j = 0; j < k - 1; j++) {
if (p[i + j] == 0) {
hasZero = true;
break;
}
tms = (tms * (p[i + j] % MOD)) % MOD;
}
if (hasZero) break;
cs = (cs * tms) % MOD;
}
cout << cs % MOD << "\n";
}
return 0;
}
|
B. Basic Graph Algorithm
感觉一点也不基础。
给定一个无向图和一个 DFS 顺序，问最少要加几条边才能达成此顺序。
我操，不保证不存在重边。
总而言之直接模拟这个 DFS 过程，如果接下来还有能走的点但不是按顺序的点的话就加边。
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
| #include <bits/stdc++.h>
using namespace std;
int main() {
cin.tie(nullptr)->sync_with_stdio(false);
int n, m;
cin >> n >> m;
vector<pair<int, int>> ans;
vector adj(n + 1, vector<int>{});
vector adv(n + 1, set<int>{});
for (int i = 0; i < m; i++) {
int u, v;
cin >> u >> v;
adj[u].emplace_back(v);
adj[v].emplace_back(u);
adv[u].emplace(v);
adv[v].emplace(u);
}
vector<int> p(n);
for (int i = 0; i < n; i++) {
cin >> p[i];
}
int pos = 0;
auto dfs = [&](this auto dfs, int u) -> void {
for (auto v : adj[u])
adv[v].erase(u);
while (not adv[u].empty() and pos < n) {
if (adv[u].contains(p[pos])) {
adv[u].erase(p[pos]);
dfs(p[pos++]);
} else {
ans.emplace_back(u, p[pos]);
dfs(p[pos++]);
}
}
};
while (pos < n) {
dfs(p[pos++]);
}
cout << ans.size() << "\n";
for (auto [u, v] : ans)
cout << u << " " << v << "\n";
return 0;
}
|
D - Decrease and Swap
给定长度为 $n$ 的序列 $a$，$a_i$ 为 $0$ 或者 $10^{18}$。每次操作可以选一个 $1 \le i \le n-2$，然后 $a_i \gets a_i - 1$，交换 $a_{i+1}$ 和 $a_{i+2}$。问是否能把序列变成全 $0$。
首先我们可以明显地感觉出来如果最后两个东西是 $0$ 的话，我们一定可以完成该操作。
然后再手玩一下剩下的情况即可。（其实是不想写了)
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
| #include <bits/stdc++.h>
using namespace std;
void solve() {
int n;
cin >> n;
string s;
cin >> s;
if (s[n - 1] == s[n - 2] and s[n - 1] == '0') {
cout << "Yes\n";
return;
}
if (n == 3) {
cout << "No\n";
return;
}
// 神秘八岐大蛇变换
// 其实本质上就是在摊大饼
for (int l = 0, r = 1; l < n - 2; l++) {
if (s[l] == '0')
continue;
r = l + 1;
int cnt = 1;
while (r < n - 2 and r - l + 1 <= cnt * 2)
cnt += s[r++] == '1';
for (int i = l; i < r; i++)
s[i] = '0';
int cost = 0;
for (int i = l; i < r; i += 2)
s[i] = '1', cost++;
for (int i = r - 1; i >= l; i--) {
if (s[i] == '1')
continue;
if (cost == cnt)
break;
s[i] = '1';
cost += 1;
}
l = r - 1;
}
string ss = "";
ss += s[n - 3];
ss += s[n - 4];
if (ss == "11")
cout << "Yes\n";
else if (ss == "00")
cout << "No\n";
else if (ss == "01") {
if (s[n - 2] == '0' and s[n - 1] == '1')
cout << "No\n";
else
cout << "Yes\n";
} else if (n >= 5 and s[n - 5] == '1')
cout << "Yes\n";
else
cout << "No\n";
}
int main() {
cin.tie(nullptr)->sync_with_stdio(false);
int T;
cin >> T;
while (T--) {
solve();
}
return 0;
}
|