1.Problem - G - Codeforces
(1)题意
(2)思路
因为最多13次,那么不如我们就问13次,然后考虑把每一个位置重新按二进制拆分成一个下标,因为C(13,6) > 1000,因此在数量上是满足得,我们考虑询问每一次在第i位上为1全部放入询问,那么最终得到得答案就是在第i位上不为1得集合得或,最后我们对于每一个位置按重新拆分得下标得0得位置全部或起来就是这个位置去除后的答案。
比如说我们得第j个位置拆分成得新二进制位置为0000111111000,那么在第[5,10]位我们不计算贡献,那么会漏掉一些集合嘛?答案是不会得,因为第除了这个位置本身外,其他位置会在总会在他的某一个为0得位置被计算贡献,因此是不会漏掉得。
(3)代码实现
#include <bits/stdc++.h>
#define rep(i,z,n) for(int i = z;i <= n; i++)
#define per(i,n,z) for(int i = n;i >= z; i--)
#define PII pair<int,int>
#define fi first
#define se second
#define vi vector<int>
#define vl vector<ll>
#define pb push_back
#define sz(x) (int)x.size()
#define all(x) (x).begin(),(x).end()
using namespace std;
using ll = long long;
const int N = 2e5 + 10;
ll w[N];
void solve()
{int n;cin >> n;vector<int> v;rep(i,0,(1<<13)-1) {if(__builtin_popcount(i) == 6) v.pb(i);if(sz(v)>=n) break;}rep(i,0,12) {vector<int> z;rep(j,0,n - 1) {if(v[j] >> i & 1) z.pb(j + 1);}if(!sz(z)) continue;cout << "? " << sz(z);for(auto x : z) cout << ' ' << x;cout << endl;cin >> w[i];}cout << "! ";rep(i,1,n) {ll Ans = 0;rep(j,0,12) {if(!(v[i - 1] >> j & 1)) Ans |= w[j];}cout << Ans << ' ';}cout << endl;
}
int main()
{ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);int T = 1;// cin >> T;while(T --) solve();return 0;
}