D
题目大意：Alice 和 Bob 得到一个长度为 $n$ 的二进制字符串 $s$，以及一个整数 $k$（$1\leq k < n$）。如果 Alice 能够将 $s$ 的所有字符都变成 $0$，则 Alice 获胜。如果 Alice 无法在有限步内获胜，则 Bob 获胜。Alice 和 Bob 轮流操作，Alice 先手。- 在 Alice 的回合，她可以选择 $s$ 中任意一个长度为 $k$ 的子序列 $^{\text{∗}}$，然后将该子序列中的所有字符都变为 $0$。- 在 Bob 的回合，他可以选择 $s$ 中任意一个长度为 $k$ 的子串 $^{\text{†}}$，然后将该子串中的所有字符都变为 $1$。
数据范围：$1 \leq t \leq 10^4$，$2\leq n \leq 2\cdot 10^5$，$1\leq k < n$，$\sum n \le 2\cdot 10^5$。
思路：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| void solve() {
ll n, k;
cin >> n >> k;
string s;
cin >> s;
ll tot = 0;
rep(i, 0, n - 1) tot += (s[i] == '1');
if (tot <= k) {
cout << "Alice" << endl;
return;
}
if (2 * k <= n) {
cout << "Bob" << endl;
return;
}
cout << "Alice" << endl;
return;
}
|
E
题目大意：定义一个数组的 $\mathrm{MEX}$（最小排除值）为该数组中未出现的最小非负整数。$\mathrm{MEX}([3, 1, 0, 1]) = 2$，因为 $0$ 和 $1$ 在数组中，但 $2$ 不在。$\mathrm{MEX}([0, 3, 1, 2]) = 4$，因为 $0, 1, 2, 3$ 都在数组中，但 $4$ 不在。给定一个大小为 $n$ 的非负整数数组 $a$。对于所有 $k$（$0 \leq k \leq n$），统计从 $a$ 中恰好移除 $k$ 个值后，$\mathrm{MEX}(a)$ 可能的不同取值数量。
数据范围：$1 \leq t \leq 10^4$，$1 \leq n \leq 2 \cdot 10^5$，$0 \leq a_i \leq n$，$\sum n \le 2 \cdot 10^5$。
思路：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| void solve() {
ll n;
cin >> n;
vl a(n);
rep(i, 0, n - 1) cin >> a[i];
map<ll, ll> ma;
rep(i, 0, n - 1) ma[a[i]]++;
vl res(n + 2);
ll cnt = 0;
while (ma.count(cnt)) cnt++;
rep(i, 0, cnt) {
ll tem = ma[i], tem2 = n - i;
if (tem <= tem2) {
res[tem]++;
res[tem2 + 1]--;
}
}
rep(i, 1, n) res[i] += res[i - 1];
rep(i, 0, n) cout << res[i] << ' ';
cout << endl;
return;
}
|
F
题目大意：称一个长度为 $n$ 的排列 $p$ 是“好”的，如果对于所有 $2 \leq i \leq n$，都有 $\gcd(p_i, i) > 1$。需要在所有长度为 $n$ 的“好”排列中，找到一个定点数最少的“好”排列。如果有多个这样的排列，输出任意一个即可。
数据范围：$1 \leq t \leq 10^4$，$2 \leq n \leq 10^5$，$\sum n \le 10^5$。
思路：
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
| constexpr int MX = 1e5 + 1;
bool pd[MX];
vi primes;
int minp[MX];
auto init = [] {
rep(i, 2, MX - 1) {
if (!pd[i]) {
primes.push_back(i);
minp[i] = i;
}
for (int& p : primes) {
if (1LL * p * i >= MX) break;
pd[i * p] = true;
minp[i * p] = max(minp[i], p);
if (i % p == 0) break;
}
}
return 0;
}();
void solve() {
ll n;
cin >> n;
vl a(n + 1);
a[1] = 1;
ll cnt = 0;
map<ll, vl> ma;
rep(i, 2, n) { ma[minp[i]].push_back(i); }
for (auto& [x, y] : ma) {
int m = sz(y);
rep(i, 0, m - 1) { a[y[(i + 1) % m]] = y[i]; }
}
rep(i, 1, n) cout << a[i] << ' ';
cout << endl;
return;
}
|
G
题目大意：给定一个整数 $m$ 和一个由 $< m$ 的非负整数构成的序列 $a$。需要处理以以下格式给定的操作： - $1$ $i$ $x$：将 $a_i$ 赋值为 $x$。- $2$ $k$：询问如果你可以选择 $a$ 若干个元素 $a_i$（也可不选），将其变成 $(a_i+x\times k) \pmod m$，其中 $x$ 为任意正整数（不同元素选取的 $x$ 可以不同），是否可能让 $a$ 变得单调不降。
数据范围：$1 \le t \le 10^4$，$2 \le n \le 10^5$，$2 \le m \le 5\cdot 10^5$，$1 \le q \le 10^5$，$0 \le a_i,x < m$，$1 \le k < m$，$\sum n,\sum q \le 10^5$。
思路：
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
| constexpr int MX = 5e5 + 5;
vector<int> divisors[MX];
auto init = [] {
for (int i = 1; i < MX; i++) {
for (int j = i; j < MX; j += i) {
divisors[j].push_back(i);
}
}
return 0;
}();
void solve() {
ll n, m, q, op, x, y;
cin >> n >> m >> q;
vl a(n);
rep(i, 0, n - 1) cin >> a[i], a[i] = a[i] % m;
map<ll, ll> ma;
for (auto p : divisors[m]) {
rep(i, 0, n - 2) {
if (a[i] % p > a[i + 1] % p) ma[p]++;
}
}
rep(i, 0, q - 1) {
cin >> op;
if (op == 1) {
cin >> x >> y;
x--;
for (auto& p : divisors[m]) {
if (x > 0 && a[x] % p < a[x - 1] % p) ma[p]--;
if (x < n - 1 && a[x] % p > a[x + 1] % p) ma[p]--;
}
a[x] = y % m;
for (auto& p : divisors[m]) {
if (x > 0 && a[x] % p < a[x - 1] % p) ma[p]++;
if (x < n - 1 && a[x] % p > a[x + 1] % p) ma[p]++;
}
} else {
cin >> x;
ll tem = __gcd(x, m);
if (ma[tem] < m / tem)
cout << "YES" << endl;
else
cout << "NO" << endl;
}
}
return;
}
|
