初级组T1机器人每次跳正整数距离若一共跳了 $k$ 次距离分别为 $x_1,x_2,\ldots x_k$则 $x_1 x_2\cdotsx_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$ 时令$rn\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)$。代码#includebits/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_{i1})。$$题目的条件就是$d_1d_2\cdotsd_{k-1}。$也就是说每次移动的距离必须严格递增。设树的直径长度为 $D$。树上任意两点之间的距离都不超过 $D$而每次移动距离都是正整数因此严格递增的距离序列最多是$$1,2,\ldots,D。$$所以最多有 $D$ 次移动即$$k\le D1。$$取树上的一条直径依次记直径上的节点为$$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。$$因此一定能选出直径上的全部 $D1$ 个节点达到上界。# 如何求直径在树上进行两次 BFS1. 从节点 $1$ 出发找到最远点 $s$。2. 从 $s$ 出发找到最远点 $t$同时记录每个节点的父亲。3. 从 $t$ 沿父亲一直回到 $s$得到一条直径。# 代码#includebits/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$ 个座位。如果 $LR$就让这个人的座位位于所有已经入座的同组成员右边。此时从右边进入只会跨过 $R$ 个座位。因此每个人的最优代价都可以独立达到答案就是 $\sum\min(L, R)$。对于每个人记录一种选择- 若 $L\le R$记为向同组已有成员的左边插入。- 否则记为向右边插入。对于一个小组最终的座位顺序为1. 所有向左插入的人按照进入顺序倒序排列。2. 所有向右插入的人按照进入顺序正序排列。例如某组成员依次选择右 右 左 左最终的相对顺序为第 4 人 第 3 人 第 1 人 第 2 人因此只需统计每组有多少人向左插入就能直接算出每个人的座位。用树状数组维护各个小组已经进入的人数。把每个小组的区间左端点作为它在树状数组中的位置。设小组 $g$ 的区间左端点为 $s_g$$L\operatorname{sum}(s_g-1)$。而$Ri-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$ 可以向左走当且仅当存在 $ji$ 满足$a_j f_j\le a_i$。只要某个 $i$ 满足那么所有更靠右的点也满足所以向左转移可行的点构成一个后缀。同理向右转移可行的点构成一个前缀。因此每一层的有效点都是$[1,l]\cup[r, n]$。并且一条长度为 $k 1$ 的路径删去最后一个点后就是长度为 $k$ 的路径所以有效集合只会不断缩小。# 代码#includebits/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$ 次骨针会使之后可用的灵魂少 $x1$ 点所以一个收益为 $x$ 的方案实际占用 $x2$点容量。因此问题转化为 有若干个任务每个任务有截止时间 $r$。选择若干任务使总收益最大并满足所有前缀中的总占用容量不超过截止时间。---按照右端点从小到大处理任务。维护当前选择的任务- 总收益。- 总占用容量。- 一个小根堆存当前收益最小的任务。当加入一个新区间导致容量超过限制时- 如果删除收益最小的任务可以解决超限就删除它。- 如果只需要减少部分容量就缩短该任务的收益。由于每次删除收益最小的任务一定最优因此可以通过贪心得到最大收益。最后答案为$$n-\text{最大减少的攻击次数}$$。总时间复杂度为 $O(n\log n)$#includebits/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; }