Jump( 2015-2016 ACM-ICPC Northeastern European Regional Contest (NEERC 15).

)

Jump( [2015-2016 ACM-ICPC Northeastern European Regional Contest (NEERC

15)]( . )

题目大意：

在这个交互式问题中，你需要通过查询系统，逐步找出隐藏的位字符串 S。给定一个偶数 n，表示目标位字符串 S 的长度，你需要通过与系统交互，查询一组长度为 n 的二进制字符串 Q。系统会返回一个整数，表示字符串 Q 与目标字符串 S 在对应位置上相同的位数。 定义一个交互问题 Jump(Q)，如下所示：

• 当 OneMax(Q) = n 或 OneMax(Q) = n / 2 时，Jump(Q) 返回 OneMax(Q)。
• 其他情况下，Jump(Q) 返回 0。 其中 OneMax(Q) 表示字符串 Q 中与隐藏字符串 S 相同的位数。你的目标是通过最少的查询次数，找出字符串 S。

问题的特点：

• 其实你会发现，你找到n/2的答案时用不了任何算法，你如直接挂茅台随机。
• 因为你会发现随机出答案 n/2 容易得多，不需要花多少次数，你不能指望直接随机到 n，因为这几乎不可能。
• 从 n/2 推到n就很简单了吧，先把第一位翻转，之后循环后面的每一位，看看与第一位上的数正误是否相同。就这么简单。

题解思路：

本题的关键在于如何通过交互查询逐步逼近隐藏的字符串 S。可以通过以下步骤实现：

1. 随机生成字符串 ：首先可以随机生成一个二进制字符串 Q，并查询系统的反馈值。如果反馈值为 n，则说明已经找到正确的字符串，直接退出。
2. 逐步修改字符串 ：如果查询的结果不是 n，则意味着 Q 与 S 不完全相同。在这种情况下，我们可以逐步修改 Q，通过改变某些位，并再次查询，直到找到正确的字符串。修改的方法可以是根据当前查询的反馈，逐步调整字符串，直到最终使查询结果为 n。
3. 查询反馈 ：对于每一次查询，你会得到反馈：

• 0：表示 Q 和 S 在任何位置上都没有匹配。
• n / 2：表示 Q 与 S 在 n / 2 个位置上匹配。
• n：表示 Q 完全匹配 S。

4. 优化查询次数 ：尽可能减少查询次数。通过不断逼近目标字符串 S，每次通过修改少量位来增加匹配的位数，从而更快找到 S。

代码解析：

#include #define endl ‘\n’ #define int long long #define BoBoowen ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); using namespace std; const int mod = 1e9 + 7; const int inf = 0x3f3f3f3f; const int N = 5e5 + 10; mt19937 rnd(114514); // 用于生成随机数 int n; // 用于发送查询并获取反馈 int query(string s) { int ans = 0; cout « s « endl; // 输出查询字符串 cin » ans; // 获取反馈 return ans; } // 生成一个随机的查询字符串并进行查询 string pre() { while (1) { string s; for (int i = 0; i < n; i++) // 生成长度为n的随机二进制字符串 { s += rnd() % 2 + ‘0’; } int ans = query(s); // 查询 if (ans == n) // 如果完全匹配，退出 { exit(0); } if (ans == n / 2) // 如果有n/2个匹配位，返回该字符串 return s; } } signed main() { cin » n; // 读取字符串长度 string t = pre(); // 生成随机字符串并进行查询 t[0] ^= 1; // 翻转第一个字符 vector s1; s1.push_back(0); // 尝试修改其他字符 for (int i = 1; i < n; i++) { t[i] ^= 1; // 翻转第i个字符 int ans = query(t); // 查询 t[i] ^= 1; // 恢复原状态 if (ans != n / 2) // 如果返回的结果不是n/2，则记录该字符位置 s1.push_back(i); } t[0] ^= 1; // 恢复第一个字符 for (auto v : s1) // 翻转记录的字符位置 t[v] ^= 1; int ans = query(t); // 再次查询 if (ans == n) // 如果完全匹配，退出 return 0; if (ans == 0) // 如果没有匹配，翻转所有位输出 { for (int i = 0; i < n; i++) t[i] ^= 1; cout « t; return 0; } }

代码流程：

1. 生成随机字符串并查询 ：

• 通过 pre() 函数生成一个随机的二进制字符串，并查询系统的反馈值。
• 如果反馈值为 n，说明已经找到目标字符串，程序终止。
• 如果反馈值为 n / 2，返回该字符串进行进一步操作。

2. 修改字符串并查询 ：

• 对生成的随机字符串逐步修改，翻转某些位，检查每次修改后的反馈结果。
• 如果反馈值为 n / 2，则继续修改，直到找到正确的字符串。

3. 输出结果 ：

• 当查询结果为 n 时，输出结果并退出。
• 如果查询结果为 0，说明字符串完全不同，需要将所有位翻转并输出。

总结：

这道题目需要通过查询与反馈来逐步找出隐藏的目标字符串。通过对字符串的逐位修改和反馈的解析，我们能够有效地逼近并最终找到目标字符串 S。