第八届图灵杯趣味网络国际邀请赛 - 初级组/中级组部分题解。

初级组：

T1：

机器人每次跳正整数距离，若一共跳了 $k$ 次，距离分别为 $x_1,x_2,\ldots x_k$，则 $x_1 + x_2+\cdots+x_k = n$。

消耗的总电量为：$\sum_{i = 1}^{k}|a-x_i|$。

对于固定的 $k$，最小消耗就是 $|n - ka|$。

因为理想情况下每次都跳 $a$，总距离为 $ka$。为了把总距离调整成 $n$，至少需要修改 $|n - ka|$ 的距离，而这个下界一定能够达到。

所以问题变成：选择一个正整数 $k$，使 $|n - ka|$ 最小，也就是寻找距离 $n$ 最近的 $a$ 的正整数倍。

分类讨论。
当 $n < a$ 时 ，不能选择 $k = 0$，只能至少跳一次。直接跳 $n$：$\text{ans}=a - n$。

当 $n\ge a$ 时，令：$r=n\bmod a$。

有两种方法：

跳 ($\left\lfloor\dfrac na\right\rfloor$) 次，把其中一次增加 $r$，消耗 $r$。

跳 ($\left\lceil\dfrac na \right\rceil$) 次，把其中一次减少 $a - r$，消耗 $a - r$。

因此 $\text{ans}=\min(r, a-r)$。

代码

#include<bits/stdc++.h> using namespace std; typedef long long ll; int main() { int T; cin >> T; while (T--) { ll n, a; cin >> n >> a; if (n < a) cout << a - n; else { ll r = n % a; cout << min(r, a - r); } cout << '\n'; } }

时间复杂度：$O(T)$。

T2：设相邻两次到达的节点距离为：$$d_i=\operatorname{dist}(p_i,p_{i+1})。$$

题目的条件就是：$d_1<d_2<\cdots<d_{k-1}。$

也就是说，每次移动的距离必须严格递增。

设树的直径长度为 $D$。

树上任意两点之间的距离都不超过 $D$，而每次移动距离都是正整数，因此严格递增的距离序列最多是：

$$
1,2,\ldots,D。
$$

所以最多有 $D$ 次移动，即：

$$
k\le D+1。
$$

取树上的一条直径，依次记直径上的节点为：

$$
v_0,v_1,\ldots,v_D。
$$

因为它们在同一条路径上，所以：

$$
\operatorname{dist}(v_x,v_y)=|x-y|。
$$

接下来只要排列下标 $0,1,\ldots,D$，使相邻下标差依次为 $1,2,\ldots,D$。

先考虑排列：

$$
0,D,1,D-1,2,D-2,\ldots
$$

它的相邻差依次为：

$$
D,D-1,\ldots,1。
$$

将这个排列倒过来，相邻差就变成：

$$
1,2,\ldots,D。
$$

因此一定能选出直径上的全部 $D+1$ 个节点，达到上界。

# 如何求直径

在树上进行两次 BFS：

1. 从节点 $1$ 出发，找到最远点 $s$。
2. 从 $s$ 出发，找到最远点 $t$，同时记录每个节点的父亲。
3. 从 $t$ 沿父亲一直回到 $s$，得到一条直径。

# 代码

#include<bits/stdc++.h> using namespace std; typedef long long ll; const int N = 2e6 + 5; int h[N], to[N << 1], nx[N << 1], cnt; int q[N], d[N], fa[N], p[N]; void add(int u, int v) { to[++cnt] = v, nx[cnt] = h[u], h[u] = cnt; } int bfs(int s, int n) { memset(d, -1, (n + 1)* sizeof (int)); int l = 0, r = 0, t = s; q[r++] = s; d[s] = 0; fa[s] = 0; while (l < r) { int u = q[l++]; if (d[u] > d[t]) t = u; for (int i = h[u]; i; i = nx[i]) { int v = to[i]; if (d[v] != -1) continue; d[v] = d[u] + 1; fa[v] = u; q[r++] = v; } } return t; } int main() { int n; cin >> n; for (int i = 1, u, v; i < n; i++) { cin >> u >> v; add(u, v), add(v, u); } int s = bfs(1, n), t = bfs(s, n); int m = 0; for (int x = t;; x = fa[x]) { p[m++] = x; if (x == s) break; } cout << m << endl; int mm = m - 1; for (int i = mm; i >= 0; i--) { int x = (i % 2) ? mm - (i >> 1) : (i >> 1); cout << p[x] << " "; } }

时间复杂度：$O(n)$

T3/T1(中级组） :

设某个人属于小组 $g$。由于每个小组的座位构成连续区间，所以其他小组相对于 $g$ 只有两种：

- 整个小组位于 $g$ 的左边。
- 整个小组位于 $g$ 的右边。

当这个人进入时，设：

- $L$ 表示已经进入且小组位于 $g$ 左边的人数。
- $R$ 表示已经进入且小组位于 $g$ 右边的人数。

的下界

无论给这个人安排小组内的哪个座位：

- 左边至少有 $L$ 个已入座的人。
- 右边至少有 $R$ 个已入座的人。

所以这个人至少需要跨过 $\min(L,R)$ 个已经有人坐下的座位。

如果 $L\le R$，就让这个人的座位位于所有已经入座的同组成员左边。

此时他的左边没有已经入座的同组成员，因此从左边进入只会跨过 $L$ 个座位。

如果 $L>R$，就让这个人的座位位于所有已经入座的同组成员右边。

此时从右边进入只会跨过 $R$ 个座位。

因此每个人的最优代价都可以独立达到，答案就是 $\sum\min(L, R)$。

对于每个人记录一种选择：

- 若 $L\le R$，记为向同组已有成员的左边插入。
- 否则，记为向右边插入。

对于一个小组，最终的座位顺序为：

1. 所有向左插入的人，按照进入顺序倒序排列。
2. 所有向右插入的人，按照进入顺序正序排列。

例如某组成员依次选择：

右 右 左 左

最终的相对顺序为：

第 4 人 第 3 人 第 1 人 第 2 人

因此只需统计每组有多少人向左插入，就能直接算出每个人的座位。

用树状数组维护各个小组已经进入的人数。

把每个小组的区间左端点作为它在树状数组中的位置。

设小组 $g$ 的区间左端点为 $s_g$：

$L=\operatorname{sum}(s_g-1)$。

而：$R=i-1-\operatorname{sum}(s_g)$。

其中 $i-1$ 是当前已经进入的总人数，$\operatorname{sum}(s_g)$ 包括左侧小组与当前小组已经进入的人。

时间复杂度为：$O(n\log n)$。

# 代码

#include <bits/stdc++.h> using namespace std; typedef long long ll; const int N = 1e6 + 5; int n, l[N], a[N], c[N], tr[N]; unsigned char d[N]; struct IO { static const int S = 1 << 20; int p = 0, q = 0; char b[S]; char gc() { if (p == q)q = fread(b, 1, S, stdin), p = 0; return p == q ? 0 : b[p++]; } int rd() { int x = 0; char ch = gc(); while (ch < '0' || ch > '9')ch = gc(); while (ch >= '0' && ch <= '9')x = x * 10 + ch - '0', ch = gc(); return x; } } io; struct OUT { static const int S = 1 << 20; int p = 0; char b[S]; ~OUT() { fl(); } void fl() { fwrite(b, 1, p, stdout); p = 0; } void pc(char ch) { if (p == S)fl(); b[p++] = ch; } void wt(ll x) { if (x >= 10) wt(x / 10); pc(x % 10 + '0'); } } out; int sum(int x) { int s = 0; for (; x; x -= x & -x) s += tr[x]; return s; } void add(int x) { for (; x <= n; x += x & -x) tr[x]++; } int main() { n = io.rd(); for (int i = 1, x; i <= n; i++) { x = io.rd(); if (!l[x])l[x] = i; } ll ans = 0; for (int i = 1, x, L, R; i <= n; i++) { x = io.rd(); a[i] = x; L = sum(l[x] - 1); R = i - 1 - sum(l[x]); if (L <= R) d[i] = 0, c[x]++, ans += L; else d[i] = 1, ans += R; add(l[x]); } for (int i = 1; i <= n; i++) if (l[i]) c[i] += l[i], l[i] = c[i] - 1; out.wt(ans); out.pc('\n'); for (int i = 1, x; i <= n; i++) { x = a[i]; if (!d[i]) a[i] = l[x]--; else a[i] = c[x]++; out.wt(a[i]); out.pc(' '); } return 0; }

T4/T2(中级组）：

需要利用一个性质：**能走至少 $k$ 个钉子的起点，一定构成一个前缀和一个后缀。 中间已经失效的点以后永远不会重新有效，因此后续不再扫描它们。

同时去掉复制数组的第三遍循环，直接交换两个 DP 数组。

设当前要求还能碰撞 $k$ 个钉子，点 $j$ 对应的最小限制为 $f_j$。

点 $i$ 可以向左走，当且仅当存在 $j<i$ 满足：

$a_j + f_j\le a_i$。

只要某个 $i$ 满足，那么所有更靠右的点也满足，所以向左转移可行的点构成一个后缀。

同理，向右转移可行的点构成一个前缀。

因此每一层的有效点都是：

$[1,l]\cup[r, n]$。

并且一条长度为 $k + 1$ 的路径删去最后一个点后，就是长度为 $k$ 的路径，所以有效集合只会不断缩小。

# 代码

#include<bits/stdc++.h> using namespace std; #define ll long long const int N = 1e6 + 5; const ll I = 4e18; ll a[N], f0[N], f1[N], v[N]; ll *f = f0, *g = f1; int s[N], n; unsigned char ans[N]; struct IO { static const int S = 1 << 20; int p = 0, l = 0; char b[S]; char gc() { if (p == l)l = fread(b, 1, S, stdin), p = 0; return p == l ? 0 : b[p++]; } ll rd() { ll x = 0; char c = gc(); while (c < '0' || c > '9')c = gc(); while (c >= '0' && c <= '9')x = x * 10 + c - '0', c = gc(); return x; } } io; struct OUT { static const int S = 1 << 20; int p = 0; char b[S]; ~OUT() { fl(); } void fl() { fwrite(b, 1, p, stdout); p = 0; } void pc(char c) { if (p == S)fl(); b[p++] = c; } void wt(int x) { if (x >= 10)wt(x / 10); pc(x % 10 + '0'); } } out; int main() { n = io.rd(); for (int i = 1; i <= n; i++)a[i] = io.rd(); if (n == 1) { out.wt(1); out.pc('\n'); return 0; } ll d = I; for (int i = 1; i < n; i++)d = min(d, a[i + 1] - a[i]); for (int i = 1; i <= n; i++) { ll x = I; if (i > 1)x = min(x, a[i] - a[i - 1]); if (i < n)x = min(x, a[i + 1] - a[i]); f[i] = x << 1; ans[i] = 2; } ll z = (a[n] - a[1]) / d; int lim = 2 + 63 - __builtin_clzll(z); int l = n, r = n + 1; for (int k = 3; k <= lim; k++) { int t = 0, q = 0, pre = 0; for (int o = 0; o < 2; o++) { int L = o ? r : 1, R = o ? n : l; for (int i = L; i <= R; i++) { if (pre) { ll x = a[pre] + f[pre]; while (t && v[t] >= x)t--; if (q > t)q = t; s[++t] = pre; v[t] = x; } while (q < t && v[q + 1] <= a[i])q++; g[i] = q ? (a[i] - a[s[q]]) << 1 : I; pre = i; } } t = q = pre = 0; int nl = 0, nr = n + 1; bool suf = 1, ok = 0; for (int o = 0; o < 2; o++) { int L = o ? l : n, R = o ? 1 : r; if (o && l + 1 < r)suf = 0; for (int i = L; i >= R; i--) { if (pre) { ll x = a[pre] - f[pre]; while (t && v[t] <= x)t--; if (q > t)q = t; s[++t] = pre; v[t] = x; } while (q < t && v[q + 1] >= a[i])q++; if (q) { ll x = (a[s[q]] - a[i]) << 1; if (x < g[i])g[i] = x; } if (g[i] < I) { ans[i] = k; ok = 1; if (suf)nr = i; else if (!nl)nl = i; } else suf = 0; pre = i; } } if (!ok)break; swap(f, g); if (nr == 1)l = n, r = n + 1; else l = nl, r = nr; } for (int i = 1; i <= n; i++) { out.wt(ans[i]); out.pc(' '); } return 0; }

时间复杂度为 $O\left(\sum_k|S_k|\right)$，

其中 $S_k$ 是能够碰撞至少 $k$ 个钉子的起点集合。

T3（中级组）：

## 思路

先考虑一次释放复仇之魂能做什么。

若当前要击杀第 $i$ 个怪物，设它的位置为 $q_i$，其中 $q$ 为 $p$ 的逆排列。

向左释放或向右释放，本质上要求后续被杀怪物的位置单调。因此可以预处理最长单调段，求出从每个怪物开始释放最多能连续击杀到哪里。

于是每次释放对应一个区间 $[l,r]$ 表示从第 $l$ 个怪物开始释放，可以一次杀到第 $r$ 个怪物。

---

如果全部使用骨针攻击，需要攻击 $n$ 次。

对于一个区间 $[l,r]$，释放复仇之魂可以减少：$$r-l$$ 次攻击。

但是释放一次需要消耗 $1$ 点灵魂，而少打 $x$ 次骨针会使之后可用的灵魂少 $x+1$ 点，所以一个收益为 $x$ 的方案实际占用 $x+2$点容量。

因此问题转化为：

> 有若干个任务，每个任务有截止时间 $r$。选择若干任务，使总收益最大，并满足所有前缀中的总占用容量不超过截止时间。

---

按照右端点从小到大处理任务。

维护当前选择的任务：

- 总收益。
- 总占用容量。
- 一个小根堆，存当前收益最小的任务。

当加入一个新区间导致容量超过限制时：

- 如果删除收益最小的任务可以解决超限，就删除它。
- 如果只需要减少部分容量，就缩短该任务的收益。

由于每次删除收益最小的任务一定最优，因此可以通过贪心得到最大收益。

最后答案为：

$$
n-\text{最大减少的攻击次数}
$$。

总时间复杂度为 $O(n\log n)$

#include<bits/stdc++.h> using namespace std; typedef long long ll; const int N = 1e6 + 5; int n, p[N], q[N], a[N], b[N], u[N], d[N], f[N]; int m, hs, h[N], ps[N], y[N]; bool z[N], t[N]; int ky(int x) { return y[x] - (x < m && t[x + 1] && z[x + 1]); } bool cp(int x, int v) { int a = ky(x), b = ky(v); return a < b || (a == b && x > v); } void sw(int x, int v) { swap(h[x], h[v]); ps[h[x]] = x; ps[h[v]] = v; } void up(int x) { while (x > 1 && cp(h[x], h[x >> 1])) sw(x, x >> 1), x >>= 1; } void dn(int x) { while (1) { int v = x, l = x << 1, r = l | 1; if (l <= hs && cp(h[l], h[v])) v = l; if (r <= hs && cp(h[r], h[v])) v = r; if (v == x) return; sw(x, v); x = v; } } void ins(int x) { h[++hs] = x; ps[x] = hs; up(hs); } void fix(int x) { if (!ps[x]) return; int v = ps[x]; up(v); dn(ps[x]); } int pop() { int x = h[1]; ps[x] = 0; if (hs == 1) { hs = 0; return x; } h[1] = h[hs--]; ps[h[1]] = 1; dn(1); return x; } int main() { ios::sync_with_stdio(false); cin.tie(0); cin >> n; for (int i = 1; i <= n; i++) cin >> p[i], q[p[i]] = i; for (int i = 1; i <= n; i++) a[i] = max(a[i - 1], p[i]); for (int i = n; i >= 1; i--) b[i] = max(b[i + 1], p[i]); u[n] = d[n] = n; for (int i = n - 1; i >= 1; i--) { u[i] = q[i] < q[i + 1] ? u[i + 1] : i; d[i] = q[i] > q[i + 1] ? d[i + 1] : i; } for (int i = 1; i <= n; i++) { int r = a[q[i]]; if (r > i && r <= d[i]) f[i] = r; r = b[q[i]]; if (r > i && r <= u[i]) f[i] = r; } int i = 1, lr = -1; ll sm = 0, ans = 0; while (i <= n) { if (!f[i]) { i++; continue; } int l = i, r = f[i], w = r - l; ++m; t[m] = m > 1 && l == lr; int v = w - (t[m] && z[m - 1]); if (v > 0) { z[m] = 1; y[m] = v; sm += v + 2; ans += v; ins(m); if (t[m] && z[m - 1]) fix(m - 1); } while (hs) { int x = h[1], k = ky(x); if (k || sm > r) { if (k && sm <= r) break; ll e = sm - r; if (k && e < k) { y[x] -= e; sm -= e; ans -= e; fix(x); break; } } x = pop(); bool nx = x < m && t[x + 1] && z[x + 1]; bool pr = x > 1 && t[x] && z[x - 1]; int v = y[x]; z[x] = 0; y[x] = 0; sm -= v + 2; ans -= v; if (nx) { y[x + 1]++; sm++; ans++; fix(x + 1); } if (pr) fix(x - 1); } lr = r; i = r; } cout << n - ans << '\n'; }