什么叫网站索引,asp.net网站开发框架,网站建设需要大约多少钱,微信网页版本Jump( 2015-2016 ACM-ICPC Northeastern European Regional Contest (NEERC 15). ) 题目大意#xff1a;
在这个交互式问题中#xff0c;你需要通过查询系统#xff0c;逐步找出隐藏的位字符串 S。给定一个偶数 n#xff0c;表示目标位字符串 S 的长度#xff0c;你需要通…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。可以通过以下步骤实现 随机生成字符串首先可以随机生成一个二进制字符串 Q并查询系统的反馈值。如果反馈值为 n则说明已经找到正确的字符串直接退出。 逐步修改字符串如果查询的结果不是 n则意味着 Q 与 S 不完全相同。在这种情况下我们可以逐步修改 Q通过改变某些位并再次查询直到找到正确的字符串。修改的方法可以是根据当前查询的反馈逐步调整字符串直到最终使查询结果为 n。 查询反馈对于每一次查询你会得到反馈 0表示 Q 和 S 在任何位置上都没有匹配。n / 2表示 Q 与 S 在 n / 2 个位置上匹配。n表示 Q 完全匹配 S。 优化查询次数尽可能减少查询次数。通过不断逼近目标字符串 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; // 翻转第一个字符vectorint 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;}
}代码流程 生成随机字符串并查询 通过 pre() 函数生成一个随机的二进制字符串并查询系统的反馈值。如果反馈值为 n说明已经找到目标字符串程序终止。如果反馈值为 n / 2返回该字符串进行进一步操作。 修改字符串并查询 对生成的随机字符串逐步修改翻转某些位检查每次修改后的反馈结果。如果反馈值为 n / 2则继续修改直到找到正确的字符串。 输出结果 当查询结果为 n 时输出结果并退出。如果查询结果为 0说明字符串完全不同需要将所有位翻转并输出。
总结
这道题目需要通过查询与反馈来逐步找出隐藏的目标字符串。通过对字符串的逐位修改和反馈的解析我们能够有效地逼近并最终找到目标字符串 S。
