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 <bits/stdc++.h>
#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<int> 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。