专栏文章

P13105 题解

zztd___
P13105题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@miottp1s
此快照首次捕获于
2025/12/03 01:02
3 个月前
此快照最后确认于
2025/12/03 01:02
3 个月前
查看原文
妙妙交互题。
感觉这种题没有什么通用技巧啊，只能依题目而定。
先考虑 F=10F = 10。
看到 N≤1024N \le 1024 即 N≤210N \le 2 ^ {10}，很容易想到操作次数和 log⁡N\log N 有关系。
想想怎样才能和 log⁡\log 产生关系。
考虑这样的事实：
将 NN 改写为二进制后，NN 的位数是 log⁡N\log N 级别的。
于是我们想到：
用二进制给计算机编号，最后把回答的结果整合回十进制，看看少了哪些数，就知道哪些计算机出了故障。
以第一组样例为例，我们将下面的矩阵一行一行地发送给评测机：
CPP
0 0 0 0 1
0 0 1 1 0
0 1 0 1 0
这个矩阵是什么意思呢？其实如果你竖着看，就会发现，第 ii 行其实是 i−1i - 1 的二进制表达形式。
也就是说，第 11 列就是二进制下的 00，第 22 列就是二进制下的 11，以此类推。
由于 00 和 33 出了故障，所以评测机返还给我们的是这样的：
CPP
0 0 1
0 1 0
1 0 0
整合一下，第一列是 11，第二列是 22，第三列是 44。缺少了 00 和 33，所以答案就是 0 3。
代码应该很好写，就不给了。
或者直接看后面也行。
考虑如何做 F=5F = 5。
容易观察到 BB 的值实际上很小，这也就意味着我们在传输信息的过程中会浪费很多列的信息。
怎么样才能防止浪费呢？
考虑下面的算法：当 NN 比较大的时候，我们将每若干列分成一块。我们取 3232 列分一块，这样我们每一块只存 00 到 3131 的二进制表示，最后再逐块整合统计答案。
为什么这样能减少浪费，且不会产生难以辨别的漏洞呢？因为 BB 最大只有 1515，而块长是 3232，所以即使所有的 BB 在同一块内，也不会让其中一块内的计算机全部故障。
这就意味着，只要在整合后我们发现某一列的结果比后一列大，那就可以说明这两列肯定在不同的块内，我们也就可以统计答案了。
具体的，如果我们发现编号 ii 有缺失，那么这台计算机就是第 (i+32×前面出现的完整的块数)(i + 32 \times \texttt{前面出现的完整的块数}) 台。
由于我比较懒，所以当 NN 较小的时候我直接用了 F=10F = 10 的不分块代码。
CPP
#include <bits/stdc++.h>
using namespace std;
char s[1222][1222];
int flg[1222], z;
signed main() {
	int TT;
	cin >> TT;
	while (TT--) {
		memset(flg, 0, sizeof(flg));
		int n, b, f;
		cin >> n >> b >> f;
		if (n > 32) {
			for (int i = 1; i <= 5; i++) {
				for (int j = 0; j < n; j++)
					cout << (((j % 32) >> (5 - i)) & 1);
				cout << endl;
				for (int j = 1; j <= n - b; j++) cin >> s[j][i];
			}
			int lst = -1, nct = 0;
			for (int i = 1; i <= n - b; i++) {
				int x = 0;
				for (int j = 1; j <= 5; j++)
					x = x * 2 + s[i][j] - 48;
				if (x <= lst) {
					for (int j = 0; j < 32; j++)
						if (!flg[j]) cout << j + 32 * nct << " ";
					nct++;
					for (int j = 0; j < 32; j++) flg[j] = 0;
				}
				flg[x] = 1, lst = x;
			}
			for (int i = 0;i <= (n - 1) % 32;i++)
				if (!flg[i]) cout << i + 32 * nct << " ";
		} else {
			int cnt = 0, tmp = n - 1;
			while (tmp) tmp >>= 1, cnt++;
			for (int i = 1; i <= cnt; i++) {
				for (int j = 0; j < n; j++)
					cout << ((j >> (cnt - i)) & 1);
				cout << endl;
				for (int j = 1; j <= n - b; j++) cin >> s[j][i];
			}
			for (int i = 1; i <= n - b; i++) {
				int x = 0;
				for (int j = 1; j <= cnt; j++) x = x * 2 + s[i][j] - 48;
				flg[x] = 1;
			}
			for (int i = 0; i < n; i++)
				if (!flg[i]) cout << i << " ";
		}
		cout << endl;
		cin >> z;
	}
	return 0;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...