茂名市电白区住房和城乡建设局网站,怎么设计网络营销方案,四川大学毕业设计网站,培训机构管理系统文章目录 [ Odd or Even](https://atcoder.jp/contests/abc313/tasks/abc313_d)问题建模问题分析1.分析每次查询的作用2.利用异或运算的性质设计查询方法 Odd or Even 问题建模
有n个数#xff0c;每个数为0或者1#xff0c;最多可以进行n次询问#xff0c;每次询问选择k个… 文章目录 [ Odd or Even](https://atcoder.jp/contests/abc313/tasks/abc313_d)问题建模问题分析1.分析每次查询的作用2.利用异或运算的性质设计查询方法 Odd or Even 问题建模
有n个数每个数为0或者1最多可以进行n次询问每次询问选择k个不同的数每次询问会得到这些数相加的奇偶性问这n个数的值分别为多少。
问题分析
1.分析每次查询的作用
每次查询可以获得这些数相加的奇偶性即0或者1则等价于将这些数进行异或得到的异或值。
2.利用异或运算的性质设计查询方法
异或运算有一个性质就是一个数异或上另一个数偶数次等价于没有异或该数。所以我们可以构造一种查询方法其中某一个数被异或奇数次而剩余数被异或上偶数次从而得到该数的值。
则可以先进行k1次查询每次查询缺少k1个数中的一个这样k1次查询得到的异或值为k1个元素每个元素出现奇数次的总异或值那对于该值异或上前k1次查询单次得到的异或值等价于缺少值出现奇数次其余值出现偶数次则可以得到缺少值的数值。
然后对于剩下的元素查询只需要前k-1个数再带一个数的异或值然后与前k个数的异或值进行比较若相同则说明当前元素值与第k个元素相同否则不同。
#includebits/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 pairint, int PII;
typedef pairLL, LL PLL;
const int N 1100, Mod 998244353;
int a[N];
int s[N];
int n,k;void get_k(){///获得前k1个数每个数出现奇数次的总异或值int res0;for(int i1;ik1;i){cout ? ;for(int j1;jk1;j){if(j!i) cout j ;}coutendl;cin s[i];res^s[i];}///用总异或值异或是上缺少某一个值的异或值从而得到对应为的值for(int i1;ik1;i){a[i]res^s[i];}
}void solve() {cin n k;get_k();///用前k个数的异或值与后面仅有第k个数不同的异或值作比较从而得到对应位置的值for(int ik2;in;i){cout ? i ;for(int j1;jk-1;j){cout j ;}cout endl;cin s[i];if(s[i]s[k1]) a[i]a[k];else a[i]a[k]^1;}cout ! ;for(int i1;in;i){cout a[i] ;}cout endl;
} int main() {int t 1;//cin t;while (t--) solve();return 0;
}
