{"problem":{"name":"[北大集训 2021] Datalab","description":{"content":"**这是一道交互题。** 在 AutoLab 平台上有一台奇怪的 $k$ 位计算机，其中 $k$ 是一个固定的常数 $8192 = 2^{13}$。这台计算机的字长恰好为 $\\frac{k}{8} = 1024 = 2^{10}$，且其存储整数的方式如下： 每个整数会存储在连续的 $k$ 个 bit 中。假设将这 $k$ 个连续 bit 的值按照下标从小到大顺次排列后得到的长度为 $k$ 的 ","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":2000,"memory_limit":524288},"difficulty":{"LuoguStyle":"P7"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP8988"},"statements":[{"statement_type":"Markdown","content":"**这是一道交互题。**\n\n在 AutoLab 平台上有一台奇怪的 $k$ 位计算机，其中 $k$ 是一个固定的常数 $8192 = 2^{13}$。这台计算机的字长恰好为 $\\frac{k}{8} = 1024 = 2^{10}$，且其存储整数的方式如下：\n\n每个整数会存储在连续的 $k$ 个 bit 中。假设将这 $k$ 个连续 bit 的值按照下标从小到大顺次排列后得到的长度为 $k$ 的 01 字符串为 $S$。假设 $S$ 的下标从 $0$ 开始，则这个字符串 $S$ 对应的整数值为 $f(S) = \\sum \\limits_{i=0}^{k-1} [S_i=1] sgn_i 2^i$，其中 $sgn$ 是一个小 W 预先定义的长度为 $k$ 的数组，其下标从 $0$ 开始且 $\\forall 0 \\le i < k,sgn_i \\in \\{-1,1\\}$。出于某些特殊的原因，这台计算机上保证了 $sgn_{k-1} = 1$，$sgn_{k-2} = -1$。而你不知道 $sgn_0,sgn_1,\\cdots,sgn_{k-3}$ 的值。\n\n假设 $L = \\sum \\limits_{i=0}^{k-1} \\min\\{0,sgn_i\\} 2^i$，$R = \\sum \\limits_{i=0}^{k-1} \\max\\{0,sgn_i\\} 2^i$，则发现 $\\forall L \\le x \\le R$，恰好有一个长度为 $k$ 的 01 字符串 $f(T)$，使得 $f(T) = x$（证明略去）。不妨设所有 $[L,R]$ 内的整数构成的集合为 $S$，则 $f$ 是一个从 $\\{0,1\\}^n$ 到 $S$ 的双射。据此我们可以设 $f(x)$ 的反函数 $g(x)$ 存在，且其满足 $\\forall x \\in S,f(g(x)) = x$。\n\n假设存在 $x,y \\in S$ ，则在该计算机上两个整数之间的加法 $\\oplus$ 被定义为 $x \\oplus y \\overset{def}{=} (x + y - L + 2^k) \\bmod 2^k + L$。不难发现 $\\forall x,y \\in S,x \\oplus y \\in S$。因而在这台计算机上加法满足封闭性。同时按照如上规则定义的加法也满足交换律，结合律等性质。这些性质的证明也同样略去。\n\n学生可以通过有限次的询问获得和 $sgn_i$ 相关的信息。每次询问你可以给计算机两个长度为 $k$ 的仅包含 $0,1$ 的字符串 $x,y$，而计算机会返回 $g(f(x) \\oplus f(y))$ 的值。本次的作业要求是在不超过 $m$ 次的询问中求出 $sgn_0,sgn_1,\\cdots,sgn_{k-3}$ 的准确值。\n\n小 Z 是一名聪明绝顶的学生，因而他尝试使用他的 $10^3 \\mathrm{Hz}$ 的超强大脑来手算出每次交互的值。但是他发现给他的处理速度还是跟不上庞大的数据规模。因而它请你帮忙写一个程序，帮助他更快速的完成本次的作业。\n\n---\n\n### 任务\n\n你不需要，也不应该实现主函数，你只需要实现如下一个函数：\n\n1. `std::vector<int> solve(int k,int m)`：\n\n\t- 传入数字的是计算机的字长 $k$ 和询问次数限制 $\\mathrm{m}$。\n\t- 你需要返回一个大小为 $k$ 的 `vector`，其第 $i$ 个元素代表你确定的 $sgn_i$ 的值。\n\n你可以通过如下函数调用 Autolab 上的加法操作。\n\n1. `std::bitset<8192> Add(std::bitset<8192> x,std::bitset<8192> y)`：\n\t- 给定两个大小为 $k$ 的 bitset, 每个 bitset 自低位向高位阅读的结果代表了一个长度为 $k$ 的仅包含 01 的字符串。\n\t- 返回一个大小为 $k$ 的 bitset, 表示 $g(f(x) \\oplus f(y))$ 的值。返回的格式和输入的格式相同。\n\n根据题目要求，你至多只能询问 $\\mathrm{m}$ 次两个整数在这台计算机上的加法结果。也就是说你至多只能调用 $\\mathrm{m}$ 次 `Add` 函数。\n\n评测时，交互库会**恰好**调用 `solve` 一次。\n\n**本题保证所使用的数组 `sgn` 在开始之前已经完全确定，不会根据和你的程序的交互过程动态构造，因此题目中的交互操作都是确定性的，你不需要关心这些操作在交互库中的具体实现。**\n\n**数据保证在调用次数限制下，交互库运行所需的时间不超过 1s；交互库使用的内存大小固定，且不超过 128MB。**\n\n---\n\n### 如何测试你的程序\n\n**试题目录下的 `grader.cpp` 是我们提供的交互库参考实现，最终测试时所用的交互库实现与该参考实现有所不同，因此选手的解法不应该依赖交互库实现。**\n\n1. 你需要在本题目录下使用如下命令编译得到可执行程序：\n   - `g++ grader.cpp sample.cpp -o sample -O2 -lm`\n\n2. 对于编译得到的可执行程序：\n   - 可执行文件将从**标准输入**读入以下格式的数据：\n     - 第一行包含两个整数 $k,\\mathrm{m}$。\n     - 接下来一行 $k$ 个整数，第 $i$ 个数字表示 $sgn_i$。\n   - 读入完成之后，交互库将调用恰好一次函数 $\\texttt{solve}$ 你的函数正确返回后，交互库会判断你的计算是否正确，若正确则会输出 `Correct` 和交互函数调用次数相关信息，否则会输出相应的错误信息。\n\n试题目录下有出题人提供的一份参考代码 `sample.cpp`，注意这份代码 **不保证可以通过所有的测试用例**。\n\n---\n\n### 样例一、二\n\n见附件下载。\n\n这两个样例满足可执行程序的输入格式，因而可以直接输入到可执行程序中。\n\n## Background\n\nCTT2021 D2T2\n\n**特别提醒，由于洛谷交互机制的特殊性，你不能在程序中引用 `datalab.h`，而需要把 `datalab.h` 中的内容加入文件的开头。即，在程序中 `solve` 函数的前面加入以下几行语句：**\n\n```cpp\n#include<bitset>\n#include<vector>\ntypedef std::bitset<8192> Bitset;\nBitset Add(Bitset A,Bitset B);\nstd::vector<int> solve(int k,int LIMIT);\n```\n\n[samples]\n\n## Note\n\n### 评分方式\n\n| subtask | $k$ | $m$ |\n| :----------: | :----------: | :----------: |\n| 1 | $=8192=2^{13}$ | $=8200$ |\n| 2 | $=8192=2^{13}$ | $=5550$ |\n| 3 | $=8192=2^{13}$ | $=4096=2^{12}$ |\n\n对于任意一个子任务中的数据，如果在某一个数据上选手返回了错误的答案，或者是超出了询问次数限制，得分为 $0$。\n\n否则假设在子任务内所有测试点中，询问次数的最大值为 $a$，则对于每个子任务，选手得分为：\n\n- Subtask $1$: $10$\n- Subtask $2$: $15$\n- Subtask $3$: $\\min \\{75,\\lfloor \\frac{13800}{\\max\\{a,1\\}} \\rfloor \\}$\n\n换而言之，当且仅当 $a \\le 184$ 的时候，Subtask $3$ 可以获得满分。\n\n选手在本题为本题三个子任务的得分之和。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP8988","tags":["2021","交互题","Special Judge","O2优化","CTT（清华集训/北大集训）"],"sample_group":[],"created_at":"2026-03-03 11:09:25"}}