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

2401_87743789

121人浏览 · 2026-07-30 17:29:05

2401_87743789 · 2026-07-30 17:29:05 发布

初级组：

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';
}