B
题目大意：迷宫中有 $n$ 个单元格，其中单元格 $i$（$1 \leq i \leq n$）距离出口有 $n - i$ 公里。特别地，单元格 $n$ 就是出口。注意每个单元格仅与出口相连，无法从其他任何单元格直接到达。每个单元格最初恰好困住一个人。你希望通过在每个单元格 $i$（$1 \leq i \leq n$）安装传送器来帮助所有人尽可能接近出口，该传送器会将单元格 $i$ 中的人传送到另一个单元格 $a_i$。迷宫主人发现了你的行为。她觉得有趣，但要求你满足以下条件： - 每个人都必须恰好使用传送器 $k$ 次。
数据范围：$1 \le t \le 10^4$，$2 \leq n \leq 2 \cdot 10^5$，$1 \leq k \leq 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
| void solve() {
int n, k;
cin >> n >> k;
vi res(n);
if (k % 2 == 1) {
rep(i, 0, n - 2) res[i] = n;
res[n - 1] = n - 1;
} else {
res[n - 2] = n;
rep(i, 0, n - 1) {
if (i == n - 2) continue;
res[i] = n - 1;
}
}
rep(i, 0, n - 1) cout << res[i] << ' ';
cout << endl;
return;
}
|
C
题目大意：你和你的团队不懈努力，最终得到了一个满足以下性质的正整数序列 $a_1, a_2, \ldots, a_{2n+1}$： - 对于所有 $1 \le i \le 2n + 1$，有 $1 \le a_i \le 10^{18}$。- $a_1, a_2, \ldots, a_{2n+1}$ 两两互不相同。- $a_1 = a_2 - a_3 + a_4 - a_5 + \ldots + a_{2n} - a_{2n+1}$。然而，与你合作的人为了抢先发表这个序列而背叛了你。
数据范围：$1 \le t \le 10^4$，$1 \leq n \leq 2 \cdot 10^5$，$1 \leq b_i \leq 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
| void solve() {
int n;
cin >> n;
vl a(2 * n);
rep(i, 0, 2 * n - 1) cin >> a[i];
ranges::sort(a);
ll tem1 = 0;
ll tem2 = 0;
rep(i, 0, n - 2) tem2 += 1LL * a[i];
rep(i, n - 1, 2 * n - 1) tem1 += 1LL * a[i];
ll tem = tem1 - tem2;
vl b(2 * n + 1);
for (int i = 0; i <= 2 * n; i += 2) b[i] = a[2 * n - 1 - i / 2];
for (int i = 1; i < 2 * n - 1; i += 2) b[i] = a[(i - 1) / 2];
b[2 * n - 1] = tem;
for (ll p : b) cout << p << ' ';
cout << endl;
return;
}
|
D
题目大意：考虑以下游戏。 游戏中每个关卡包含 $n$ 对门。每对门包含一个左门和一个右门。每个门执行以下两种操作之一： - 加法操作 (+ $a$)：将该通道的人数增加固定值 $a$。- 乘法操作 (× $a$)：将该通道当前人数乘以整数 $a$。这意味着该通道人数将增加 $(a - 1)$ 倍当前值。每个操作产生的新增人员可以分配到任意通道。但已存在于某个通道的人员不可转移到另一个通道。初始时，每个通道各有 $1$ 人。
数据范围：$1 \leq t \leq 10^4$，$1 \leq n \le 30$，$1 \le a \le 1000$，$2 \le a \le 3$。
思路：
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
| void solve() {
int n;
cin >> n;
vector<pll> ma(n);
vector<pair<char, char>> op(n);
rep(i, 0, n - 1) { cin >> op[i].first >> ma[i].first >> op[i].second >> ma[i].second; }
vector<pll> suf(n + 1);
suf[n].first = suf[n].second = 1;
frep(i, n - 1, 0) {
suf[i] = suf[i + 1];
if (op[i].first == 'x') suf[i].first += max(suf[i + 1].first, suf[i + 1].second) * (ma[i].first - 1);
if (op[i].second == 'x') suf[i].second += max(suf[i + 1].first, suf[i + 1].second) * (ma[i].second - 1);
}
ll l = 1, r = 1;
rep(i, 0, n - 1) {
ll tem = 0;
if (op[i].first == '+')
tem += ma[i].first;
else
tem += (ma[i].first - 1) * l;
if (op[i].second == '+')
tem += ma[i].second;
else
tem += (ma[i].second - 1) * r;
if (suf[i + 1].first >= suf[i + 1].second)
l += tem;
else
r += tem;
}
cout << l + r << endl;
return;
}
|
E
题目大意：这是一道交互题。存在两个隐藏的非负整数 $x$ 和 $y$（$0 \leq x, y < 2^{30}$）。你最多可以提出 2 次以下形式的询问： - 选择一个非负整数 $n$（$0 \leq n < 2^{30}$）。
数据范围：$1 \le t \le 10^4$。
思路：
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
| const int tem1 = 715827882;
const int tem2 = 357913941;
ll ask(ll l) {
cout << l << '\n';
cout.flush();
ll op;
cin >> op;
return op;
}
ll report() {
cout << "! " << '\n';
cout.flush();
ll op;
cin >> op;
return op;
}
void report2(ll x) {
cout << x << '\n';
cout.flush();
}
void solve() {
ll tem3 = ask(tem1);
tem3 -= 2 * tem1;
ll tem4 = ask(tem2);
tem4 -= 2 * tem2;
ll m = report();
ll x = 0, y = 0;
for (int i = 0; i < 30; i += 2) {
if ((tem3 >> i) & 1)
x |= (1LL << i);
else if ((tem3 >> (i + 1)) & 1)
x |= (1LL << i), y |= (1LL << i);
}
for (int i = 1; i < 30; i += 2) {
if ((tem4 >> i) & 1)
x |= (1LL << i);
else if ((tem4 >> (i + 1)) & 1)
x |= (1LL << i), y |= (1LL << i);
}
report2((x | m) + (y | m));
return;
}
|
F
题目大意：给定二进制字符串 $v$，其分数由某个切分点左右两段的函数值乘积取最大得到，其中 $F(v,l,r)$ 与区间长度和 $0$ 的个数有关。需要按题意处理字符串与询问，计算对应分数。
数据范围：$1 \le t \le 10^4$，$1 \leq n \leq 2 \cdot 10^5$，$1 \leq q \leq 2 \cdot 10^5$，$1 \leq i \leq n$，$\sum n \le 2 \cdot 10^5$，$\sum q \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
26
27
28
29
30
31
32
| const ll MOD = 998244353;
ll mul(ll x, ll y) { return x * y % MOD; }
ll qpow(ll x, ll y) {
ll z = 1;
while (y > 0) {
if (y & 1) z = mul(z, x);
x = mul(x, x);
y >>= 1;
}
return z;
} // 求x**y%MOD
// 注意：当MOD为质数时， (x/y)%MOD=(x*(y**(MOD-2)))%MOD，即y在模MOD意义下的逆元为b^{-1} \equiv b^{p-2} mod p
void solve() {
int n, q, x;
cin >> n >> q;
string s;
cin >> s;
ll tot = 0;
rep(i, 0, n - 1) tot += (s[i] == '1' ? 1 : -1);
rep(i, 0, q - 1) {
cin >> x;
x--;
tot -= (s[x] == '1' ? 2 : -2);
s[x] = (s[x] == '1' ? '0' : '1');
cout << (n <= 4 ? qpow((1 << (4 - n)), MOD - 2) * (tot * tot % MOD + n - 2 + MOD) % MOD
: qpow(2, n - 4) * (tot * tot % MOD + n - 2 + MOD) % MOD)
<< endl;
}
return;
}
|
