题解：CF1867E1 Salyg1n and Array (simple version)

mayike · 2024-03-31 21:31:34 · 题解

简单题

题目传送门

思路

首先，必须知道 x \operatorname{xor} x = 0,0 \operatorname{xor} x = x，x 规定为自然数。那么这题就简单了。

作图。

先问 1 区间，再问了 2 区间，则红色区域的异或值被抵消成 0，此时查询后要翻转区间，则区间 2 转成区间 3，再询问区间 4，那么红色区域的异或值就回来了，此时的异或值为区间 1，区间 2 的白色区域以及区间 4 的白色区域的异或值。

因为区间长度为 k，所以这个操作等价于在假设询问过区间 1 的情况下，后两次连续询问的长度是相同且在 1 \le x \le k 里随便拟定长度的。

那么总次数至多为 \frac{n}{k}+2 \le 52 满足条件，因为 n,k 都是偶数，那么我们对 a = n \bmod k，这一段进行两次连续且长度相同的询问即可。

代码也比较短。

#include<bits/stdc++.h>
using namespace std;
#define int long long
signed main(){
    int T,n,k,cnt,ps,ans;
    cin>>T;
    while(T--){
        cin>>n>>k;
        cnt=ps=ans=0;
        int sum=(n-k)/2,x,js;
        cnt=sum/k,ps=sum%k;
        cout<<"? "<<1<<endl;
        cin>>x,ans^=x,js=k+1;
        if(ps!=0){
            cout<<"? "<<js-(k-ps)<<endl;
            cin>>x,ans^=x,js=js+ps;
            cout<<"? "<<js-(k-ps)<<endl;
            cin>>x,ans^=x,js=js+ps;
        }for(int i=1;i<=cnt*2;i++){
            cout<<"? "<<js<<endl;
            cin>>x,ans^=x,js+=k;
        }cout<<"! "<<ans<<endl;
    }
}