AtCoder Beginner Contest 313D题题解

Odd or Even

问题建模

有n个数，每个数为0或者1，最多可以进行n次询问，每次询问选择k个不同的数，每次询问会得到这些数相加的奇偶性，问这n个数的值分别为多少。

问题分析

1.分析每次查询的作用

每次查询，可以获得这些数相加的奇偶性，即0或者1，则等价于将这些数进行异或得到的异或值。

2.利用异或运算的性质设计查询方法

异或运算有一个性质，就是一个数异或上另一个数偶数次，等价于没有异或该数。所以我们可以构造一种查询方法，其中某一个数被异或奇数次，而剩余数被异或上偶数次，从而得到该数的值。

则可以先进行k+1次查询，每次查询缺少k+1个数中的一个，这样k+1次查询得到的异或值，为k+1个元素每个元素出现奇数次的总异或值，那对于该值异或上前k+1次查询单次得到的异或值，等价于缺少值出现奇数次，其余值出现偶数次，则可以得到缺少值的数值。

然后对于剩下的元素，查询只需要前k-1个数再带一个数的异或值，然后与前k个数的异或值进行比较，若相同，则说明当前元素值与第k个元素相同，否则不同。

#include<bits/stdc++.h>#define x first
#define y second
#define C(i) str[0][i]!=str[1][i]
using namespace std;
typedef unsigned long long ULL;
typedef long long LL;
typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;
const int N =1100, Mod =998244353;
int a[N];
int s[N];
int n,k;void get_k(){///获得前k+1个数每个数出现奇数次的总异或值int res=0;for(int i=1;i<=k+1;i++){cout <<"? ";for(int j=1;j<=k+1;j++){if(j!=i)    cout <<j <<" ";}cout<<endl;cin >>s[i];res^=s[i];}///用总异或值，异或是上缺少某一个值的异或值，从而得到对应为的值for(int i=1;i<=k+1;i++){a[i]=res^s[i];}
}void solve() {cin >>n >>k;get_k();///用前k个数的异或值与后面仅有第k个数不同的异或值作比较，从而得到对应位置的值for(int i=k+2;i<=n;i++){cout <<"? " <<i <<" ";for(int j=1;j<=k-1;j++){cout <<j <<" ";}cout <<endl;cin >>s[i];if(s[i]==s[k+1])   a[i]=a[k];else a[i]=a[k]^1;}cout <<"! ";for(int i=1;i<=n;i++){cout <<a[i] <<" ";}cout <<endl;
}  int main() {int t = 1;//cin >> t;while (t--) solve();return 0;
}