B
题目大意：你正在分析一个无限的网格，坐标为 $(X, Y)$（特别地，$(0, 0)$ 正上方的格子是 $(0, 1)$，正右方的格子是 $(1, 0)$）。初始时，只有 $(0, 0)$ 这个格子是黑色的。你得到一个长度为 $n$ 的字符串 $a_1a_2\ldots a_n$，每个字符都是 $\texttt{"4"}$ 或 $\texttt{"8"}$，描述了 $n$ 次扩展操作。对于每一次 $i$，所有格子会同时进行如下操作： - 如果 $s_i = \texttt{"4"}$：对于每一个格子，若它与某个黑色格子正交相邻（即有一条边相接），它会变成黑色；否则，它的状态不变。
数据范围：$1 \le t \le 10^4$，$1 \le n \le 2 \cdot 10^5, -10^9 \le x, y \le 10^9$，$\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
23
24
| void solve() {
int n;
ll x, y;
cin >> n >> x >> y;
x = abs(x), y = abs(y);
string s;
cin >> s;
ll tem1 = 0, tem2 = 0;
ll res1 = x + y, res2 = x - y;
int tot1 = 0, tot2 = 0;
rep(i, 0, n - 1) {
if (s[i] == '4') {
tot1++;
} else {
tot2++;
}
}
if (tot1 + tot2 >= max(x, y) && x + y <= tot1 + 2 * tot2) {
cout << "YES" << endl;
return;
}
cout << "NO" << endl;
return;
}
|
C
题目大意：给定三个正整数 $n$、$k$ 和 $q$。你还会得到 $q$ 个三元组 $(c, l, r)$，其中 $1 \leq c \leq 2$，$1 \leq l \leq r \leq n$。
数据范围：$1 \le t \le 500$，$1 \leq k \leq n \leq 100$，$1 \leq q \leq 100$。
思路：
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() {
int n, k, q;
int c, l, r;
cin >> n >> k >> q;
vector<set<int>> ma(n);
vi a(n, 1e9);
rep(i, 0, q - 1) {
cin >> c >> l >> r;
l--, r--;
rep(j, l, r) ma[j].insert(c);
}
int cnt = 0;
rep(i, 0, n - 1) {
if (ma[i].count(1) && !ma[i].count(2)) {
a[i] = k;
}
if (!ma[i].count(1) && ma[i].count(2)) {
a[i] = cnt;
cnt = (cnt + 1) % k;
}
}
rep(i, 0, n - 1) cout << a[i] << ' ';
cout << endl;
return;
}
|
D
题目大意：你正在关注亿人游戏（Billion Players Game）世界锦标赛。有 $10^9$ 名选手参加，你想预测你最喜欢的主播 Godflex 的最终排名 $p$。经过最近比赛情况的分析，你确定 $l \leq p \leq r$，但除此之外，没有更多的信息。
数据范围：$1 \le t \le 10^4$，$1 \leq n \leq 2 \cdot 10^5$，$1 \leq l \leq r \leq 10^9$，$1 \leq a_i \leq 10^9$，$\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
22
23
24
25
26
27
| void solve() {
int n, l, r;
cin >> n >> l >> r;
vl a(n);
rep(i, 0, n - 1) cin >> a[i];
ranges::sort(a);
vl pre(n);
vl suf(n + 1);
pre[0] = a[0];
suf[n - 1] = a[n - 1];
rep(i, 1, n - 1) pre[i] = pre[i - 1] + a[i];
frep(i, n - 2, 0) suf[i] = suf[i + 1] + a[i];
ll ans = 0;
// 枚举选择a[i]-p的数量
// 假设a[i]-p的数量为y，p-a[i]的数量为x
// 当y>=x时，p应该取l
// 当y<x时，p应该取r
rep(i, 0, n - 1) {
if (a[i] < l) ans += l - a[i], a[i] = l;
if (a[i] > r) ans += a[i] - r, a[i] = r;
}
for (int i = 0, j = n - 1; i < j; i++, j--) {
ans += a[j] - a[i];
}
cout << ans << endl;
return;
}
|
