B
题目大意：Doran 和 Krug 正在一个由 $(n + 1) \times (n + 1)$ 个格子组成的网格上玩游戏，网格上的每个单元格坐标是从 $0$ 到 $n$（包含 $0$ 和 $n$）的整数对。Krug 的目标是尽可能长时间不被 Doran 抓住，而 Doran 的目标是尽快抓住 Krug。当 Doran 和 Krug 站在同一个格子上时，称 Doran 抓住了 Krug。游戏规则如下，Krug 和 Doran 轮流行动，Krug 先手： - Krug 可以选择留在原地，或者移动到上下左右相邻的格子（不可斜向移动）。
数据范围：$(1 \le t \le 10^4)$，$(1 \le n \le 10^9, 0 \le r_K, c_K, r_D, c_D \le n, (r_K, c_K) \ne (r_D, c_D))$。
思路：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| using i128 = __int128_t;
void solve() {
ll n, st1, fs1, st2, fs2;
cin >> n >> st1 >> fs1 >> st2 >> fs2;
if (st1 == st2 && fs1 == fs2)
cout << 0 << endl;
else if (st1 == st2)
cout << (fs1 > fs2 ? n - fs2 : fs2) << endl;
else if (fs1 == fs2)
cout << (st1 > st2 ? n - st2 : st2) << endl;
else {
ll tem = (fs1 > fs2 ? n - fs2 : fs2);
ll tem2 = (st1 > st2 ? n - st2 : st2);
cout << max(tem, tem2) << endl;
}
return;
}
|
C
题目大意：Keria 厌倦了为远程输出型英雄提供支援，现在她设计了一个关于支持区间查询的数据结构问题。对于一个长度为 $m$ 的数组 $b = [b_1, b_2, \ldots, b_m]$，其中 $b_i=0$ 或 $b_i=1$，定义如下的“三元组移除”操作： 1. 选择三个下标 $1 \le i < j < k \le m$，使得这三个位置上的元素相同（即 $b_i = b_j = b_k$）。2. 将这三个元素从数组中移除。该操作的代价为 $\min(k-j, j-i)$。移除后，剩余的数组连接起来，重新编号。我们的目标是通过三元组移除操作，将数组 $b$ 变为空。数组的总代价定义为：将数组清空所需一系列三元组移除操作代价之和的最小值。
数据范围：$1 \le t \le 10^4$，$1 \le n, q \le 250\,000$，$1 \le l_i \le r_i \le n$，$\sum n \le 250\,000$，$\sum q \le 250\,000$。
思路：
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
| using i128 = __int128_t;
void solve() {
ll n, q, x, y;
cin >> n >> q;
vl a(n);
rep(i, 0, n - 1) cin >> a[i];
vl pre(n);
pre[0] = a[0];
rep(i, 1, n - 1) pre[i] = pre[i - 1] + a[i];
vl pre2(n);
pre2[0] = 0;
rep(i, 1, n - 1) pre2[i] = pre2[i - 1] + (a[i] == a[i - 1]);
rep(i, 0, q - 1) {
cin >> x >> y;
x--, y--;
ll tem = (x == 0 ? 0 : pre[x - 1]);
ll tem2 = pre[y] - tem;
if (tem2 % 3 != 0 || (y - x + 1 - tem2) % 3 != 0) {
cout << -1 << endl;
continue;
}
ll tem3 = pre2[x];
ll tem4 = pre2[y] - tem3;
cout << ((y - x + 1) / 3) + (tem4 == 0) << endl;
}
return;
}
|
D
题目大意：对于一个长度为 $m$ 的数组 $b=[b_1,b_2,\ldots,b_m]$（$b_i \geq 2$），考虑由 Poby 和 Rekkles 进行的如下二人游戏： - 两位玩家轮流行动，Poby 先手。- 在 Poby 的回合，他必须选择一个 $x \ge 2$ 的元素，将其替换为 $\left\lfloor \frac{x}{2} \right\rfloor$。即选择 $i$（$1 \leq i \leq m$）且 $b_i \ge 2$，然后执行 $b_i := \left\lfloor \frac{b_i}{2} \right\rfloor$。
数据范围：$1 \le t \le 10^4$，$1 \le n, q \le 250\,000$，$2 \le a_i \le 10^9$，$1 \le l_j \le r_j \le n$，$\sum n \le 250\,000$，$\sum q \le 250\,000$。
思路：
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
| using i128 = __int128_t;
void solve() {
ll n, q, x, y;
cin >> n >> q;
vl a(n);
rep(i, 0, n - 1) cin >> a[i];
vl b(n);
rep(i, 0, n - 1) {
if ((a[i] & (a[i] - 1)) == 0)
b[i] = 1;
else if (((a[i] - 2) & (a[i] - 1)) == 0)
b[i] = 2;
else
b[i] = 3;
}
vl pre(n);
vl pre2(n);
vl pre3(n);
pre[0] = 1LL * log2(a[0]);
pre2[0] = (b[0] == 2);
pre3[0] = (b[0] == 3);
rep(i, 1, n - 1) {
pre[i] = pre[i - 1] + 1LL * log2(a[i]);
pre2[i] = pre2[i - 1] + (b[i] == 2);
pre3[i] = pre3[i - 1] + (b[i] == 3);
}
rep(i, 0, q - 1) {
cin >> x >> y;
x--, y--;
ll tem = (x == 0 ? 0 : pre[x - 1]);
ll tem2 = (x == 0 ? 0 : pre2[x - 1]);
ll tem3 = (x == 0 ? 0 : pre3[x - 1]);
cout << pre[y] - tem + (pre2[y] - tem2) / 2 + (pre3[y] - tem3) << endl;
}
return;
}
|
E
题目大意：这是一个交互题。Faker 又在调皮了。你让他出一道好玩的查询题，结果他却出了一道需要你来和他互动的题。Faker 把一个排列藏了起来，而需要通过与他的互动来推断出一些有趣的信息。给定一个整数 $n$。Faker 藏了一个长度为 $n^2+1$ 的排列 $p_1, p_2, \ldots, p_{n^2+1}$。你的目标是找出这个隐藏排列中长度恰好为 $n+1$ 的单调子序列（递增或递减皆可）。可以证明，任意长度为 $n^2+1$ 的排列都必然包含一个长度为 $n+1$ 的单调子序列。关于这个证明的更多信息，你可以参考维基百科页面。
数据范围：$1 \le t \le 5000$，$1 \le n \le 100$，$\sum (n^2+1) \le 10\,001$。
思路：
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
| vl ask(ll k, vl& res) {
cout << "? " << k << ' ';
rep(i, 0, k - 1) cout << res[i] << ' ';
cout << '\n';
cout.flush();
ll op;
cin >> op;
vl res2(op);
rep(i, 0, op - 1) cin >> res2[i];
return res2;
}
void report(vl& res) {
cout << "! ";
rep(i, 0, sz(res) - 1) cout << res[i] << ' ';
cout << '\n';
cout.flush();
}
void solve() {
ll n;
cin >> n;
vl tem;
rep(i, 1, n * n + 1) tem.push_back(i);
vl pa(n * n + 5);
rep(i, 1, n) {
vl op = ask(sz(tem), tem);
if (sz(op) >= n + 1) {
vl res;
rep(i, 0, n) res.push_back(op[i]);
report(res);
return;
}
int m = sz(op);
int l = 0, las = 0;
for (auto& p : tem) {
if (l <= m - 1 && op[l] == p)
las = p, l++;
else
pa[p] = las;
}
map<ll, ll> ma;
rep(i, 0, m - 1) ma[op[i]]++;
vl ntem;
for (auto& p : tem) {
if (ma.count(p)) continue;
ntem.push_back(p);
}
tem = ntem;
}
vl res;
ll tem2 = tem[0];
rep(i, 0, n) {
res.push_back(tem2);
tem2 = pa[tem2];
}
ranges::reverse(res);
report(res);
return;
}
|
F
题目大意：Zeus 正在分析战斗录像，以了解对手的攻击模式。对手有一个特殊能力：如果在 $z$ 时间内命中同一个目标三次，他的第三次攻击就会变得非常强力。为了避免被对手触发强化攻击，Zeus 不能让对手在 $z$ 时间内连续命中三次。设 $Y = \{y_1, y_2, \ldots, y_m\}$ 为包含 $m$ 个时间戳的多重集，每个 $y_i$ 代表对手攻击命中的时刻。我们称 $Y$ 是安全的，当且仅当对任意三个时间戳 $\{y_i, y_j, y_k\}$（$1 \le i < j < k \le m$），都有 $\max(y_i, y_j, y_k) - \min(y_i, y_j, y_k) > z$，其中 $z$ 是给定的时间窗口。
数据范围：$1 \le t \le 20000$，$1 \le n \le 250000$，$1 \le z \le 10^9$，$1 \le x_i \le 10^9$，$1 \le q \le 250000$，$1 \le l \le r \le n$，$\sum n \le 250000$，$\sum q \le 250000$。
思路：
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
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
| using i128 = __int128_t;
const ll MX = 20;
void solve() {
ll n, q, x, y, z;
cin >> n >> z;
vl a(n);
rep(i, 0, n - 1) cin >> a[i];
vl pa(n + 1, n);
vvl up(n + 1, vl(MX, n));
ll r = 0;
rep(l, 0, n - 1) {
while (r <= n - 1 && a[r] <= a[l] + z) r++;
pa[l] = r;
}
pa[n] = n;
rep(i, 0, n) up[i][0] = pa[i];
rep(j, 1, MX - 1) {
rep(i, 0, n) {
ll mid = up[i][j - 1];
up[i][j] = up[mid][j - 1];
}
}
vl dep(n + 1);
dep[n] = 0;
frep(i, n - 1, 0) dep[i] = dep[pa[i]] + 1;
auto lca = [&](ll u, ll v) {
if (dep[u] > dep[v]) swap(u, v);
ll d = dep[v] - dep[u];
rep(j, 0, MX - 1) {
if ((d >> j) & 1) v = up[v][j];
}
if (u == v) return u;
frep(j, MX - 1, 0) {
if (up[u][j] != up[v][j]) {
u = up[u][j];
v = up[v][j];
}
}
return up[u][0];
};
vector<vector<pll>> up2(n + 1, vector<pll>(MX, {n, 0}));
rep(i, 0, n - 1) {
ll tem = lca(i, i + 1);
up2[i][0].first = tem;
up2[i][0].second = dep[i] + dep[i + 1] - 2 * dep[tem];
}
rep(j, 1, MX - 1) {
rep(i, 0, n) {
ll mid = up2[i][j - 1].first;
up2[i][j].first = up2[mid][j - 1].first;
up2[i][j].second = up2[i][j - 1].second + up2[mid][j - 1].second;
}
}
auto calc = [&](ll x, ll y) {
ll tem = 1;
frep(i, MX - 1, 0) {
if (up[x][i] <= y) {
x = up[x][i];
tem += (1LL << i);
}
}
return tem;
};
cin >> q;
rep(i, 0, q - 1) {
cin >> x >> y;
x--, y--;
if (y - x + 1 <= 2) {
cout << y - x + 1 << endl;
continue;
}
ll tem = 0;
frep(i, MX - 1, 0) {
if (up2[x][i].first <= y) {
tem += up2[x][i].second;
x = up2[x][i].first;
}
}
if (x <= y) tem += calc(x, y);
if (x + 1 <= y) tem += calc(x + 1, y);
cout << tem << endl;
}
return;
}
|
