AI 验题报告

共使用 $12$ 个模型进行验题，情况分布如下所示

题目评分如下，参考CodeFores评分机制

题号	题目	rating	主要难点
A	还差几个座位	800	取模，处理已经整除的情况
B	成对亮灯	900	发现零的数量的奇偶性不变
C	连号免单券	1000	总和减去最大相邻和
D	安静的一侧	1200	枚举分界点，在线维护两侧修改次数
E	打包的顺序	1700	有序集合与动态相邻关系的同步维护
F	双色通行证	1500	将颜色加入状态，进行多源 BFS
G	蒂娜的谜箱	2200	循环移位覆盖、计数分治、询问次数证明

A. 还差几个座位

数学，模运算

每张桌子有 $k$ 个座位，要求所有使用中的桌子都坐满，因此最终人数必须是 $k$ 的倍数。我们需要找到最小的非负整数 $x$，使得 $n+x$ 能被 $k$ 整除。

设：

$$r=n\bmod k.$$

当 $r=0$ 时，现有人数已经满足要求，答案为 $0$。

当 $r>0$ 时，只需要补齐到下一个 $k$ 的倍数，答案为 $k-r$。

可以统一写成：

$$\boxed{\text{ans}=(k-n\bmod k)\bmod k}$$

最后一次取模用于处理 $n$ 已经是 $k$ 的倍数的情况。

参考代码

#include<bits/stdc++.h>

using i64 = long long;

int main() {
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);
	
	int t;
	std::cin >> t;
	while (t--) {
		i64 n, k;
		std::cin >> n >> k;
		std::cout << (k - n % k) % k << "\n";
	}
	
	return 0;
}

B. 成对亮灯

思维，字符串

每次操作可以翻转任意两盏不同的灯，目标是让所有灯都变为点亮状态。注意，选中的两盏灯不要求相邻。

设当前熄灭的灯，也就是字符 $0$ 的数量为 $z$。

一次操作对 $z$ 的影响只有三种：

$$z\longrightarrow \begin{cases} z-2, & \text{选择两盏熄灭的灯};\\ z, & \text{选择一盏熄灭的灯和一盏点亮的灯};\\ z+2, & \text{选择两盏点亮的灯}. \end{cases}$$

因此，熄灭灯数量的奇偶性不会改变。

目标状态的熄灭灯数量为 $0$，所以当 $z$ 为奇数时，一定无解。

当 $z$ 为偶数时，将所有熄灭的灯两两配对，每对进行一次操作，就可以让所有灯点亮，共需要 $\frac z2$ 次操作。

所以：

$$\boxed{ \text{ans}= \begin{cases} -1&, z\text{ 为奇数};\\ \cfrac z2&, z\text{ 为偶数}. \end{cases} }$$

参考代码

#include<bits/stdc++.h>

using i64 = long long;

int main() {
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);
	
	int t;
	std::cin >> t;
	while (t--) {
		int n;
		std::string s;
		std::cin >> n >> s;
		int cnt = std::count(s.begin(), s.end(), '0');
		if (cnt % 2 == 0) {
			std::cout << cnt / 2 << "\n";
		} else {
			std::cout << -1 << "\n";
		}
	}
	
	return 0;
}

C. 连号免单券

数学，枚举

优惠券至多使用一次，并且只能让原顺序中编号相邻的两件商品免单，不能调整商品顺序。

设所有商品的总价为：

$$S=\sum_{i=1}^{n}a_i.$$

如果选择第 $i$ 件和第 $i+1$ 件商品免单，需要支付的金额就是：

$$S-(a_i+a_{i+1}).$$

由于所有价格都是正数，且至少有两件商品，使用优惠券一定比不使用更优。

总价 $S$ 固定，所以最小化支付金额，等价于最大化免单金额：

$$\boxed{ \text{ans} = \sum_{i=1}^{n}a_i - \max_{1\le i<n}(a_i+a_{i+1}) }$$

遍历数组时，同时维护总价和相邻两项之和的最大值即可。

不必存储整个数组，只需要保留上一个读入的价格。

不能直接选择价格最高的两件商品，因为它们可能不相邻。例如序列 $(100,1,100)$ 中，两件价格为 $100$ 的商品不能同时免单。

题目给出的范围为 $n\le 2\times 10^5$、$a_i\le 10^9$，因此总价可能达到 $2\times 10^{14}$，需要使用 long long。

参考代码

#include<bits/stdc++.h>

using i64 = long long;

void solve() {
	int n;
	std::cin >> n;
	std::vector<i64> a(n);
	i64 sum = 0;
	for (int i = 0; i < n; i++) {
		std::cin >> a[i];
		sum += a[i];
	}
	i64 mx = 0;
	for (int i = 0; i < n - 1; i++) {
		mx = std::max(mx, a[i] + a[i + 1]);
	}
	std::cout << sum - mx << "\n";
}

int main() {
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);
	
	int t;
	std::cin >> t;
	while (t--) {
		solve();
	}
	
	return 0;
}

D. 安静的一侧

思维，枚举

最终要求所有 0 都位于所有 1 的左侧，全为 0 或全为 1 也合法。每次操作可以翻转一个位置。

因此，最终字符串一定具有以下形式：

$$\underbrace{00\cdots 0}_{k\text{ 个}} \underbrace{11\cdots 1}_{n-k\text{ 个}},$$

其中：

$$0\le k\le n.$$

我们可以枚举这个分界点 $k$。

对于固定的 $k$，前 $k$ 个位置必须全部变为 0，因此需要翻转其中原本为 1 的位置；后 $n-k$ 个位置必须全部变为 1，因此需要翻转其中原本为 0 的位置。

设：

$$L_1(k)=\text{前 }k\text{ 个位置中 }1\text{ 的数量},$$ $$R_0(k)=\text{后 }n-k\text{ 个位置中 }0\text{ 的数量}.$$

那么分界点为 $k$ 时的最少操作次数为：

$$\operatorname{cost}(k)=L_1(k)+R_0(k).$$

答案为：

$$\boxed{ \text{ans}=\min_{0\le k\le n} \left(L_1(k)+R_0(k)\right) }$$

初始化时考虑了 $k=0$，扫描结束时考虑了 $k=n$，因此不会遗漏全为 1 或全为 0 的情况。

参考代码

#include<bits/stdc++.h>

using i64 = long long;

void solve() {
	int n;
	std::string s;
	std::cin >> n >> s;
	int zero = 0, one = 0;
	zero = std::count(s.begin(), s.end(), '0');
	int ans = std::min(zero, n - zero);
	for (int i = 0; i < n; i++) {
		if (s[i] == '1') {
			one ++;
		} else {
			zero --;
		}
		ans = std::min(ans, one + zero);
	}
	std::cout << ans << "\n";
}

int main() {
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);
	
	int t;
	std::cin >> t;
	while (t--) {
		solve();
	}
	
	return 0;
}

E. 打包的顺序

双向链表，数据结构，堆，集合

每次必须选择当前相邻且重量之和最小的一对；如果有多对并列，必须选择最靠左的一对。

如果每次都遍历整个序列寻找最小相邻和，单次需要 $O(n)$ 时间，进行 $n-1$ 次合并后，总时间复杂度为 $O(n^2)$。

我们使用 双向链表维护相邻关系，有序集合维护候选合并对，将复杂度降为 $O(n\log n)$。

1. 维护当前的包裹序列

使用数组模拟双向链表：

• pre[i] 表示包裹 $i$ 左侧的包裹；
• nxt[i] 表示包裹 $i$ 右侧的包裹；
• weight[i] 表示包裹 $i$ 当前的重量。

不存在前驱或后继时，使用 $0$ 表示。

合并相邻包裹 $x,y$ 时，保留左侧包裹的编号 $x$，将其重量增加为两者之和，再从链表中删除 $y$。

这样，每个当前包裹的编号始终等于它所包含的原始包裹中的最左编号。

因此，当前包裹从左到右的顺序，与保留编号的大小顺序一致。

2. 快速选择下一对包裹

对于每个存在右邻居的包裹 $i$，向 set 中加入：

$$\left( \operatorname{weight}[i] + \operatorname{weight}[\operatorname{nxt}[i]], \ i \right).$$

set 按二元组的字典序排序，即首先比较相邻重量之和，再比较左侧包裹的编号。

因此，集合中的第一个元素恰好对应题目要求合并的一对：重量之和最小，并且在并列时最靠左。

3. 一次合并如何更新

设当前选中的两个包裹为 $x,y$，其左右邻居分别为 $l,r$。局部结构为：

$$l\longleftrightarrow x\longleftrightarrow y\longleftrightarrow r.$$

合并之前，先从集合中删除受到影响的旧相邻对：

$$(l,x),\quad (x,y),\quad (y,r).$$

不存在端点的相邻对直接忽略。

然后将 $x,y$ 合并，保留编号 $x$，局部结构变为：

$$l\longleftrightarrow x\longleftrightarrow r.$$

将新重量加入答案，再向集合中加入新的相邻对：

$$(l,x),\quad (x,r).$$

其他相邻对没有发生变化，不需要更新。

实现时，必须先删除旧记录，再修改重量和链表，否则无法根据旧的重量之和删除对应元素。

参考代码

#include<bits/stdc++.h>

using i64 = long long;

void solve() {
	int n;
	std::cin >> n;
	std::vector<i64> a(n);
	std::vector<int> pre(n), nxt(n);
	for (int i = 0; i < n; i++) {
		std::cin >> a[i];
		pre[i] = i - 1;
		nxt[i] = i + 1;
	}
	std::set<std::pair<i64, int>> st;
	for (int i = 0; i < n - 1; i++) {
		st.insert({a[i] + a[i + 1], i});
	}
	i64 ans = 0;
	// (L, x) (x, y) (y, R)
	while (st.size()) {
		auto [v, x] = *st.begin();
		ans += v;
		
		int y = nxt[x];
		int L = pre[x];
		int R = nxt[y];

		st.erase(st.begin());
		if (L != -1) {
			st.erase({a[L] + a[x], L});
		}
		if (R != n) {
			st.erase({a[y] + a[R], y});
		}
		a[x] = v;
		nxt[x] = R;
		if (R != n) {
			pre[R] = x;
			st.insert({a[x] + a[R], x});
		}
		if (L != -1) {
			st.insert({a[L] + a[x], L});
		}
	}
	std::cout << ans << "\n";
}

int main() {
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);
	
	int t;
	std::cin >> t;
	while (t--) {
		solve();
	}
	
	return 0;
}

F. 双色通行证

图论，多源BFS

只有通道颜色与当前通行证颜色相同，才能通过该通道；每次通过后，通行证立即变色。

初始颜色可以自由选择，但不能通过停留改变颜色。

本题的关键是：仅记录当前所在房间，不足以描述完整状态，还必须记录通行证的当前颜色。

即使两次到达同一个房间，只要通行证颜色不同，之后能够通过的通道就可能不同。因此，不能只使用 visited[u] 标记房间是否被访问过。

定义：

$$\operatorname{dist}[u][c]$$

表示到达房间 $u$，并且此时通行证颜色为 $c$ 的最短时间，其中 $c\in\{0,1\}$。

对于当前状态 $(u,c)$，只有颜色为 $c$ 的通道可以通过。如果该通道通向房间 $v$，通过后的状态为：

$$(u,c)\longrightarrow(v,c\oplus 1),$$

其中 $\oplus$ 表示异或。对于二进制颜色，$c\oplus 1$ 就是另一种颜色。

每次状态转移都消耗 $1$ 分钟，因此可以使用 BFS。

因为初始颜色可以自由选择，将：

$$\operatorname{dist}[1][0] = \operatorname{dist}[1][1] = 0$$

作为两个起始状态，同时加入队列，执行多源 BFS。

最后，在终点的两个状态中取可达距离的最小值：

$$\text{ans} = \min\bigl( \operatorname{dist}[n][0], \operatorname{dist}[n][1] \bigr),$$

其中不可达的状态不参与取最小值。若两个状态都不可达，则输出 $-1$。

当 $n=1$ 时，起点就是终点，初始化已经保证答案为 $0$。

参考代码

#include<bits/stdc++.h>

using i64 = long long;

void solve(){
	int n, m;
	std::cin >> n >> m;
	std::vector<std::vector<std::pair<int, int>>> e(n + 1);
	for (int i = 1; i <= m; i++) {
		int u, v, c;
		std::cin >> u >> v >> c;
		e[u].push_back({v, c});
		e[v].push_back({u, c});
	}
	std::queue<std::pair<int, int>> q;
	std::vector<std::array<int, 2>> dist(n + 1, {-1, -1});
	dist[1][0] = dist[1][1] = 0;
	q.push({1, 0});
	q.push({1, 1});

	while (q.size()) {
		auto [u, c] = q.front();
		q.pop();

		for (auto [v, w] : e[u]) {
			if (w != c || dist[v][c ^ 1] != -1) {
				continue;
			}
			dist[v][c ^ 1] = dist[u][c] + 1;
			q.push({v, c ^ 1});
		}
	}
	int ans = 1e9;
	for (int c = 0; c <= 1; c++) {
		if (dist[n][c] == -1) {
			continue;
		}
		ans = std::min(ans, dist[n][c]);
	}
	std::cout << (ans == 1e9 ? -1 : ans) << "\n";
}

int main() {
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);
	
	int t;
	std::cin >> t;
	while (t--) {
		solve();
	}
	
	return 0;
}

G. 蒂娜的谜箱

交互题，分治

本题允许将部分位置填为 $0$，表示留空；但每次询问中的所有非零数字必须互不相同。

因此，不能把同一个数字放到很多位置，直接询问它是否位于某个位置集合中。

我们使用 循环移位覆盖所有可能匹配，再通过分治定位正确位置 的方法。

1. 构造循环移位排列

对于每个：

$$d=0,1,\ldots,n-1,$$

构造一个排列 $q^{(d)}$：

$$q_i^{(d)} = ((i-1+d)\bmod n)+1, \qquad 1\le i\le n.$$

例如，当 $n=4$ 时，构造出的四个排列为：

d = 0：1 2 3 4
d = 1：2 3 4 1
d = 2：3 4 1 2
d = 3：4 1 2 3

分别询问这 $n$ 个完整排列，设第 $d$ 个排列得到的回复为 $r_d$。

这些排列具有一个关键性质：

对于每个固定位置 $i$，随着 $d$ 遍历 $0$ 到 $n-1$，$q_i^{(d)}$ 恰好遍历数字 $1$ 到 $n$ 各一次。

因此，无论隐藏排列中的 $p_i$ 是多少，都恰好存在一个移位 $d$，满足：

$$q_i^{(d)}=p_i.$$

也就是说，每个位置恰好在一个移位排列中匹配正确。于是：

$$\boxed{ \sum_{d=0}^{n-1}r_d=n }$$

这是控制询问次数的关键：虽然我们构造了 $n$ 个排列，但它们包含的正确匹配总数只有 $n$，并不是 $n^2$。

2. 分治定位某个排列中的正确位置

固定一个移位 $d$。

我们已经知道完整排列 $q^{(d)}$ 中有 $r_d$ 个正确位置，但还不知道这些位置在哪里。

定义递归过程：

$$\operatorname{solve}(d,l,r,cnt),$$

表示已经知道 $q^{(d)}$ 在区间 $[l,r]$ 中恰好有 $cnt$ 个正确位置，需要将它们全部找出。

有以下三种情况。

当 $cnt=0$ 时，整个区间没有正确位置，直接返回。

当 $cnt=r-l+1$ 时，整个区间都正确，直接确定：

$$p_i=q_i^{(d)},\qquad l\le i\le r.$$

其他情况，将区间从中点：

$$mid=\left\lfloor\frac{l+r}{2}\right\rfloor$$

分成左右两部分。

只询问左半区间：在 $[l,mid]$ 中保留 $q^{(d)}$ 的数字，其余位置全部填 $0$。

设交互器回复为 $x$，则左半区间恰好有 $x$ 个正确位置。由于整个区间的正确数量已经知道，右半区间的正确数量就是：

$$cnt-x.$$

于是递归处理：

$$\operatorname{solve}(d,l,mid,x),$$ $$\operatorname{solve}(d,mid+1,r,cnt-x).$$

右半区间不需要再单独询问，其正确数量可以通过减法得到。

对于每个移位 $d$，调用：

$$\operatorname{solve}(d,1,n,r_d).$$

处理完所有移位后，就能恢复完整排列。

3. 分治过程示例

以隐藏排列：

$$p=(3,1,4,2)$$

为例。考虑移位排列：

$$q^{(2)}=(3,4,1,2).$$

完整询问的回复为 $2$，说明其中有两个正确位置。

先询问左半部分：

? 3 4 0 0

回复为 $1$，所以左半部分有一个正确位置，右半部分也有一个正确位置。

继续定位左半部分，询问：

? 3 0 0 0

回复为 $1$，因此可以确定 $p_1=3$，而第 $2$ 个位置在当前移位中不匹配。

定位右半部分时，询问：

? 0 0 1 0

回复为 $0$。由于右半部分总共有一个正确位置，因此正确位置只能是第 $4$ 个，可以确定 $p_4=2$。

其他移位同理，可以确定剩余位置。

询问次数证明

设：

$$L=\lceil\log_2 n\rceil.$$

首先，询问全部循环移位排列需要 $n$ 次。

对于固定移位 $d$，其正确匹配总数为 $r_d$。

考虑该移位的分治树。在任意一层中，各个区间互不相交，并且每个需要继续发起询问的区间至少包含一个正确匹配。

因此，同一层需要询问的区间数量不会超过 $r_d$。

分治最多有 $L$ 层需要发起询问，所以该移位的分治询问次数至多为：

$$r_dL.$$

对所有移位求和，分治询问次数至多为：

$$\sum_{d=0}^{n-1}r_dL = L\sum_{d=0}^{n-1}r_d = nL.$$

加上最初的 $n$ 次完整排列询问，总询问次数满足：

$$Q\le n+n\lceil\log_2 n\rceil.$$

题目规定 $n\le 100$，最多允许 $8n$ 次尝试。由于：

$$\lceil\log_2 100\rceil=7,$$

所以：

$$\boxed{ Q\le n+7n=8n }$$

因此，该算法具有确定性的最坏情况保证，不依赖随机化。

参考代码

#include <bits/stdc++.h>

using i64 = long long;

int query(std::vector<int> &v, int l, int r) {
    std::cout << "?";
    for (int i = 0; i < v.size(); i++) {
        std::cout << " " << ((l <= i && i <= r) ? v[i] : 0);
    }
    std::cout << std::endl;

    int val;
    std::cin >> val;
    return val;
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int n;
    std::cin >> n;
    std::vector<int> ans(n), cnt(n);
    std::vector tmp(n, std::vector<int>(n));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            tmp[i][j] = (i + j) % n + 1;
        }
        cnt[i] = query(tmp[i], 0, n - 1);
    }
    
    auto dfs = [&](auto &&self, std::vector<int> &v, int l, int r, int count) -> void {
        if (count == 0) {
            return;
        }
        if (count == r - l + 1) {
            for (int i = l; i <= r; i++) {
                ans[i] = v[i];
            }
            return;
        }
        int mid = (l + r) / 2;
        int left = query(v, l, mid);
        self(self, v, l, mid, left);
        self(self, v, mid + 1, r, count - left);
    };

    for (int i = 0; i < n; i++) {
        dfs(dfs, tmp[i], 0, n - 1, cnt[i]);
    }

    std::cout << "!";
    for (int i = 0; i < n; i++) {
        std::cout << " " << ans[i];
    }
    std::cout << std::endl;

    return 0;
}