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; // 翻轉第一個字符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;}
}
代碼流程：
-
生成隨機字符串并查詢：
- 通過
pre()函數生成一個隨機的二進制字符串，并查詢系統的反饋值。 - 如果反饋值為
n，說明已經找到目標字符串，程序終止。 - 如果反饋值為
n / 2，返回該字符串進行進一步操作。
- 通過
-
修改字符串并查詢：
- 對生成的隨機字符串逐步修改，翻轉某些位，檢查每次修改后的反饋結果。
- 如果反饋值為
n / 2，則繼續修改，直到找到正確的字符串。
-
輸出結果：
- 當查詢結果為
n時，輸出結果并退出。 - 如果查詢結果為
0，說明字符串完全不同，需要將所有位翻轉并輸出。
- 當查詢結果為
總結：
這道題目需要通過查詢與反饋來逐步找出隱藏的目標字符串。通過對字符串的逐位修改和反饋的解析，我們能夠有效地逼近并最終找到目標字符串 S。
