B
题目大意：Niko 初始分数为 $0$ ，一共有 $n$ 回合。第 $i$ 回合可以选择红牌使分数变为 $k-a_i$ ，或选择蓝牌使分数变为 $b_i-k$ 。求最终分数的最大值。
数据范围：$1 \leq t \leq 10^3, 1 \leq n \leq 10^5, -10^9 \leq a_i,b_i \leq 10^9, \sum n \leq 10^5$
思路：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| void solve() {
ll n;
cin >> n;
vl a(n), b(n);
rep(i, 0, n - 1) cin >> a[i];
rep(i, 0, n - 1) cin >> b[i];
ll mixx = 0, maxx = 0;
rep(i, 0, n - 1) {
ll tem = mixx, tem2 = maxx;
mixx = min({tem - a[i], tem2 - a[i], b[i] - tem, b[i] - tem2});
maxx = max({tem - a[i], tem2 - a[i], b[i] - tem, b[i] - tem2});
}
cout << maxx << endl;
return;
}
|
C
题目大意：给定 $n,k$ 和数组 $a$ 。需要找一个最小大小的集合 $B$ ，使每个 $a_i$ 至少有一个因子在 $B$ 中，并且对任意 $b\in B$ ，所有不超过 $k$ 的正倍数都必须在数组 $a$ 中出现。无解输出 $-1$ 。
数据范围：$1 \leq t \leq 10^4, 1 \leq n \leq 2 \cdot 10^5, 1 \leq k \leq 10^9, 1 \leq a_i \leq k, \sum n \leq 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
| void solve() {
ll n, k;
cin >> n >> k;
vl a(n);
rep(i, 0, n - 1) cin >> a[i];
map<ll, ll> ma;
rep(i, 0, n - 1) ma[a[i]]++;
vl b;
for (auto& [x, y] : ma) b.push_back(x);
int l = 0, m = sz(b);
vl res;
map<ll, ll> ma2;
rep(i, 0, m - 1) ma2[b[i]] = i;
vb vis(m, false);
rep(i, 0, m - 1) {
if (vis[i]) continue;
vis[i] = true;
res.push_back(b[i]);
for (ll j = 2 * b[i]; j <= k; j += b[i]) {
if (!ma.count(j)) {
cout << -1 << endl;
return;
}
ll tem = ma2[j];
vis[tem] = true;
}
}
cout << sz(res) << endl;
rep(i, 0, sz(res) - 1) cout << res[i] << ' ';
cout << endl;
return;
}
|
D
题目大意：给定初始整数 $n$ 和操作次数 $k$ 。每次可以选择非负整数 $\ell$ ，令 $n\leftarrow n+2^\ell$ ，本次得分为二进制加法产生的进位次数。求 $k$ 次操作后的最大总得分。
数据范围：$1 \leq t \leq 1000, 1 \leq n < 2^{30}, 0 \leq k \leq 10^9$
思路：
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
| void solve() {
ll n, k;
cin >> n >> k;
if (k >= 32) {
cout << popcount((unsigned)n) + k - 1 << endl;
return;
}
vvl dp(k + 1, vl(k + 5, LLONG_MAX / 3));
dp[0][0] = 0;
rep(i, 0, 30) {
vvl ndp(k + 1, vl(k + 5, LLONG_MAX / 3));
rep(j, 0, k) {
rep(v, 0, k + 2) {
if (dp[j][v] == LLONG_MAX / 3) continue;
rep(l, 0, k - j) {
int tem = (n >> i & 1) + l + v;
if ((tem >> 1) <= k + 2) {
ndp[j + l][(tem >> 1)] = min(ndp[j + l][(tem >> 1)], dp[j][v] + (tem & 1));
}
}
}
}
dp = ndp;
}
ll ans = LLONG_MAX / 3;
rep(i, 0, k + 2) ans = min(ans, dp[k][i] + popcount((unsigned)i));
cout << k + popcount((unsigned)n) - ans << endl;
return;
}
|
E
题目大意：交互题。给定一个长度为 $n$ 的排列，每次选择两个下标 $x,y$ 后，等概率交换 $(x,y)$ 或其关于序列中心的镜像下标对，并返回实际交换的位置。需要在操作次数限制内把排列排序。
数据范围：$1 \leq t \leq 100, 1 \leq n \leq 4000, \sum n \leq 2 \cdot 10^4, \lfloor 2.5n+800 \rfloor$
思路：
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
| pll ask(ll l, ll r) {
cout << "? " << l << ' ' << r << '\n';
cout.flush();
ll op, op2;
cin >> op >> op2;
return {op, op2};
}
void report() {
cout << "! " << '\n';
cout.flush();
}
void solve() {
ll n;
cin >> n;
vl a(n + 1), pos(n + 1);
rep(i, 1, n) cin >> a[i], pos[a[i]] = i;
if (n % 2 == 1) {
while (pos[(n + 1) / 2] != (n + 1) / 2) {
auto [x, y] = ask(pos[(n + 1) / 2], (n + 1) / 2);
swap(a[x], a[y]);
pos[a[x]] = x;
pos[a[y]] = y;
}
}
rep(i, 1, n / 2) {
while (pos[i] + pos[n + 1 - i] != n + 1) {
auto [x, y] = ask(pos[i], n + 1 - pos[n + 1 - i]);
swap(a[x], a[y]);
pos[a[x]] = x;
pos[a[y]] = y;
}
}
rep(i, 1, n / 2) {
while (pos[i] != i || pos[n + 1 - i] != n + 1 - i) {
if (pos[i] != i) {
auto [x, y] = ask(pos[i], i);
swap(a[x], a[y]);
pos[a[x]] = x;
pos[a[y]] = y;
}
if (pos[n + 1 - i] != n + 1 - i) {
auto [x, y] = ask(pos[n + 1 - i], n + 1 - i);
swap(a[x], a[y]);
pos[a[x]] = x;
pos[a[y]] = y;
}
}
}
report();
return;
}
|
F
题目大意：给定非递增数组 $a$ 和 $q$ 个询问 $(l,r,x)$ 。每个询问从左到右处理 $a_l\ldots a_r$ ，维护当前和；一旦当前和达到 $x$ 就清零并计数。输出清零次数和最终剩余和。
数据范围：$1 \leq t \leq 1000, 1 \leq n,q \leq 150000, 1 \leq a_i,x \leq 10^9, 1 \leq l \leq r \leq n, \sum n \leq 150000, \sum q \leq 150000$
思路：
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
| void solve() {
ll n, q, l, r, x;
cin >> n >> q;
vl a(n);
rep(i, 0, n - 1) cin >> a[i];
vl pre(n + 1);
rep(i, 1, n) pre[i] = pre[i - 1] + a[i - 1];
const ll B = sqrt(n);
vector<array<ll, 3>> queries;
vl tem;
rep(i, 0, q - 1) {
cin >> l >> r >> x;
l--, r--;
queries.push_back({l, r, x});
tem.push_back(x);
}
auto sorted = tem;
ranges::sort(sorted);
sorted.erase(unique(all(sorted)), sorted.end());
int m = sz(sorted);
vl id(q);
rep(i, 0, q - 1) { id[i] = ranges::lower_bound(sorted, tem[i]) - sorted.begin(); }
vvl up(B + 1, vl(m, -1));
rep(i, 1, B) {
int cnt = n - i;
rep(j, 0, m - 1) {
while (cnt >= 0 && pre[cnt + i] - pre[cnt] < sorted[j]) {
cnt--;
}
if (cnt >= 0)
up[i][j] = cnt;
else
break;
}
}
rep(i, 0, q - 1) {
auto [l, r, x] = queries[i];
ll cur = l;
ll cnt = 0, re = 0;
rep(j, 1, B) {
if (cur > up[j][id[i]]) continue;
if (cur <= min(r - j + 1, up[j][id[i]])) {
ll tem2 = (min(r - j + 1, up[j][id[i]]) - cur) / j + 1;
cnt += tem2;
cur += tem2 * j;
}
}
while (cur <= r) {
if (pre[r + 1] - pre[cur] < x) {
re = pre[r + 1] - pre[cur];
break;
}
cnt++;
ll tem2 = lower_bound(pre.begin() + cur + 1, pre.begin() + r + 2, pre[cur] + x) - pre.begin();
cur = tem2;
}
cout << cnt << ' ' << re << endl;
}
return;
}
|
