题意：
给出n个数，其中有两个特殊的数值为y，其他不特殊的数值为x，现要求你与评测机交互进行不超过19次询问找出两个特殊值得位置，询问是：你给出该数列的一个任意子集，评测机返回该子集内所有数的异或值。
思路：
贼6的二进制思维题，也是头一回做的交互题。自己想不出来，看的大佬的博客。
由于保证x和y值不同且都不为0，所以每次询问的子集异或值只会有四种取值(x, y, x^y, 0)，然后观察发现当该异或值为y或者x^y时，表明该子集中一定只存在一个y。又，因为值为y的两个位置pos1，pos2肯定不同，那么pos1和pos2的二进制形式一定至少存在一位它们俩是不同的，那么我们就根据二进制位确定子集，即从二进制低位到高位每次都选取该位为1的位置组成一个集合进行询问，因为n <= 1000，那么我们最多花费9次(如果前9次都不可行，第10次必定能行)就能将所有数分为两个集合，使每个集合都有且仅有一个y。那么我们再至多通过9次询问不断缩小其中一个集合就能确定出一个y的位置。然而再怎么求第二个位置呢？显然只剩一次询问是无法确定的了，其实我们在前9次询问中寻找pos1和pos2位二进制位不同的时候，通过一个bit来记录两个二进制位是否相同，相同则令bit当前位为0，不同当前位为1(所以我们在前面询问时不管分没分成两个集合都要询问完所有位了，所以最多达到10次)。最后求出ans1，与bit异或一下就是ans2了。
代码：
#include <bits/stdc++.h> using namespace std; int n, x, y, _xor, bit; set<int> s1, s2; set<int>::iterator it; vector<int> vt1, vt2; string str; string chg(int x) { string res; while(x) res += x+'0', x /= 10; reverse(res.begin(), res.end()); return " " + res; } void find(int pos) { for(int i = 0; i <= 9; ++i) { if(i == pos) continue; str = ""; vt1.clear(), vt2.clear(); for(it = s2.begin(); it != s2.end(); ++it) if((*it)&(1<<i)) str += chg(*it), vt1.push_back(*it); else vt2.push_back(*it); if(vt1.empty()) continue; cout << ("?"+chg(vt1.size())+str) << endl; // fflush(stdout); cin >> _xor; if(_xor == (x^y) || _xor == y) { for(int j = 0; j < vt2.size(); ++j) s2.erase(vt2[j]); } else { for(int j = 0; j < vt1.size(); ++j) s2.erase(vt1[j]); } } int ans1 = *(s2.begin()), ans2 = 0; ans2 = ans1^bit; if(ans1 > ans2) swap(ans1, ans2); cout << "! " << ans1 << " " << ans2 << endl; } void work() { int pos = -1; bit = 0; for(int i = 0; i <= 9; ++i) { str = ""; s1.clear(); for(int j = 1; j <= n; ++j) if(j&(1<<i)) str += chg(j), s1.insert(j); if(s1.empty()) continue; cout << ("?"+chg(s1.size())+str) << endl; // fflush(stdout); cin >> _xor; if(_xor == (x^y) || _xor == y) { bit += 1<<i; if(s2.empty()) s2 = s1, pos = i; } } find(pos); } int main() { ios::sync_with_stdio(0); cin >> n >> x >> y; work(); return 0; }
继续加油~
