B
题目大意：我们称一个字符串 $t$ 是交替字符串，如果对于每一个 $i$（$1 \leq i \leq n-1$），都有 $t_i \neq t_{i+1}$ 成立。给定一个只包含字母 “a” 和／或 “b” 的字符串 $s$。
数据范围：$1 \leq t \leq 10^4$，$2 \leq |s| \leq 2 \cdot 10^5$，$\sum |s| \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
23
24
25
| void solve() {
string s;
cin >> s;
int n = sz(s);
bool flag = true;
rep(i, 0, n - 2) {
if (s[i] == s[i + 1]) {
flag = false;
break;
}
}
if (flag) {
cout << "YES" << endl;
return;
}
int ans = 0;
rep(i, 0, n - 2) {
if (s[i] == s[i + 1]) ans++;
}
if (ans > 2)
cout << "NO" << endl;
else
cout << "YES" << endl;
return;
}
|
C
题目大意：有一个 $2\times n$ 个单元格的表格。每个单元格是红色或黑色。你要修改一些单元格的颜色使存在将所有单元格配为 $n$ 对的方案且满足： - 每一对单元格颜色相同。- 每一对单元格位置相邻。请您求出修改单元格数量的最小值。
数据范围：$t(1\le t\le 10^4)$，$n(1\le n \le 2\times 10^5)$，$\sum n \le 2\times 10^5$。
思路：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| void solve() {
ll n;
cin >> n;
vector<vector<char>> ma(2, vector<char>(n));
rep(i, 0, 1) { rep(j, 0, n - 1) cin >> ma[i][j]; }
vector<int> dp(n);
if (ma[0][0] == ma[1][0])
dp[0] = 0;
else
dp[0] = 1;
if (n == 1) {
cout << dp[0] << endl;
return;
}
dp[1] = min(dp[0] + (ma[0][1] != ma[1][1]), (ma[0][0] != ma[0][1]) + (ma[1][0] != ma[1][1]));
rep(i, 2, n - 1) {
dp[i] = min(dp[i - 1] + (ma[0][i] != ma[1][i]), dp[i - 2] + (ma[0][i - 1] != ma[0][i]) + (ma[1][i - 1] != ma[1][i]));
}
cout << dp[n - 1] << endl;
return;
}
|
D
题目大意：给你两个整数 $n$ 和 $x$。考虑序列 $[1,2,3,\dots,n]$。需要找出其中包含 $x$ 且异或结果为 $0$ 的子区间的数量。换句话说，需要计算满足 $1\le l\le x\le r\le n$ 且 $l\oplus (l+1)\oplus\dots\oplus r=0$ 的 $(l,r)$ 对的数目，其中 $\oplus$ 表示按位异或。
数据范围：$t (1 \le t \le 2 \times 10^5 )$，$x(1 \le x \le n \le 10^{18})$。
思路：
1
2
3
4
5
6
7
8
9
10
11
| const ll MOD = 998244353;
void solve() {
ll n, x;
cin >> n >> x;
ll tem = (1 + x / 4) % MOD;
ll tem2 = (x + 2) / 4 % MOD;
ll tem3 = (1 + (n + 1) / 4 - tem + MOD) % MOD;
ll tem4 = ((n + 3) / 4 - tem2 + MOD) % MOD;
cout << (tem * tem3 % MOD + tem2 * tem4 % MOD) % MOD << endl;
return;
}
|
E
题目大意：给定一个包含 $n$ 个整数坐标点的数组 $p$。这些点均匀分布在某个边平行于坐标轴的矩形内。需要放置若干个圆，使得满足以下条件： - 每个圆的半径均为 $r$，且圆心的坐标为整数； - 任意两个圆的交集面积为 $0$（圆可以相切但不能重叠）； - 至少有 $89\%$ 的点落在某个圆内部或圆的边界上（即落在圆内或圆上的点的数量不少于 $\frac{89n}{100}$）。你并不知道数组 $p$ 中点分布所在的矩形，但除样例外，在所有测试数据中保证一个半径为 $r$ 的圆的面积不超过此矩形面积的 $\frac{1}{10}$。
数据范围：$4 \le n \le 10^4$，$10^2 \le r \le 10^3$，$-10^5 \le p_x, p_y \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
| mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
void solve() {
ll n, r;
cin >> n >> r;
vector<pll> ma(n);
rep(i, 0, n - 1) cin >> ma[i].first >> ma[i].second;
ll bias = 1e5;
ll tem = 0;
while (tem * tem < 3 * r * r) tem++;
while (true) {
ll dx = rng() % (2 * r);
ll dy = rng() % tem;
int cnt = 0;
set<pii> res;
for (auto& [x, y] : ma) {
ll tx = x + bias;
ll ty = y + bias;
ll cntx = tx / (2 * r);
ll cnty = ty / tem;
bool flag = false;
rep(i, cntx - 2, cntx + 2) {
if (flag) break;
rep(j, cnty - 2, cnty + 2) {
ll tx2 = i * 2 * r + (j % 2 == 0 ? r : 0) + dx;
ll ty2 = j * tem + dy;
ll dis = (tx2 - tx) * (tx2 - tx) + (ty2 - ty) * (ty2 - ty);
if (dis <= r * r) {
flag = true;
res.insert({tx2 - bias, ty2 - bias});
}
}
}
if (flag) cnt++;
}
if (cnt * 100 >= 89 * n) {
cout << sz(res) << endl;
for (auto& [x, y] : res) cout << x << ' ' << y << endl;
return;
}
}
return;
}
|
