題目鏈接：點擊查看
題目大意：給出一個長度為 n（n 保證了是 2 的冪次），每個數的范圍在 [ 0 , n - 1 ] 的一個陣列，現在要求通過有限次操作確定下來這個陣列：
- 詢問 a[ i ] xor a[ j ] 的答案
- 詢問 a[ i ] or a[ j ] 的答案
- 詢問 a[ i ] and a[ j ] 的答案
題目分析：因為可以詢問任意兩個數異或運算后的答案，根據 ，我們可以先確定出序列中的任意一個數字設為 x，然后對于其他的數字依次詢問與 x 的異或，就可以反推出所有的數字了，所以現在問題轉換成如何在有限次操作中確定下來某個數字的取值
E1 是最多詢問 n + 2 次，E2 是最多詢問 n + 1 次，先簡單說一下 E1 的做法，對于位運算和加法運算之間有個公式是：
對于每組樣例，我們可以任取三個數字 a[ i ] , a[ j ] , a[ k ]，利用上述公式通過六次詢問求出 a[ i ] + a[ j ]，a[ i ] + a[ k ]，a[ j ] + a[ k ]，現在是三個未知數+三個等式就可以分別求出 a[ i ] , a[ j ] , a[ k ] 的值了，對于剩下的 n - 3 個數來說，依次與 a[ i ] 或 a[ j ] 或 a[ k ] 進行異或操作就可以反推出答案了，不過很可惜的是，這樣的做法詢問次數是 6 + ( n - 3 ) = n + 3 次
還是由于異或運算的性質，當我們知道 和
后，將這兩個數進行異或運算就可以直接得到
了，少去一次異或運算的詢問復雜度就是 n + 2 次，已經可以通過 E1 了
到此為止，我們會發現，題目中給定的一個條件我們還沒有用上，就是每個數的范圍都在 [ 0 , n - 1 ] 之內，我們分兩種情況考慮：
- 假設至少存在兩個數 a[ j ] 和 a[ k ] 相等，那么其與第三個數分別異或得到的結果顯然也是相等的，符號語言就是：
，如此一來我們就可以直接通過“與”運算或者“或”運算求出這兩個數了，即
，
，然后對于剩下的 n - 2 個數進行異或運算反推，這種情況的詢問復雜度是 1 + ( n - 2 ) = n - 1 次
- 假設所有的數兩兩都不相同，換句話 n 個數覆寫了 [ 0 , n - 1 ] 這一整個區間，又因為 n - 1 是 2 的冪次減一，換句話說 n - 1 在二進制下全部是 1 ，所以對于任意一個 x 來說，一定存在這一個 y，滿足
，也就是說
，到此為止，根據
這個公式再隨便選一個數字解方程即可，因為根據上述方法得到的 x 和 y 已經滿足了
代碼：
//#pragma GCC optimize(2)
//#pragma GCC optimize("Ofast","inline","-ffast-math")
//#pragma GCC target("avx,sse2,sse3,sse4,mmx")
#include<iostream>
#include<cstdio>
#include<string>
#include<ctime>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<stack>
#include<climits>
#include<queue>
#include<map>
#include<set>
#include<sstream>
#include<cassert>
#include<bitset>
using namespace std;
typedef long long LL;
typedef unsigned long long ull;
const int inf=0x3f3f3f3f;
const int N=1e6+100;
int _xor[N],last[N],a[N];
int interact(int i,int j,const char s[])
{
printf("%s %d %d\n",s,i,j);
fflush(stdout);
int num;
scanf("%d",&num);
return num;
}
int main()
{
#ifndef ONLINE_JUDGE
// freopen("data.in.txt","r",stdin);
// freopen("data.out.txt","w",stdout);
#endif
// ios::sync_with_stdio(false);
memset(last,-1,sizeof(last));
last[0]=1;
int n,id1=-1,id2=-1;
scanf("%d",&n);
for(int i=2;i<=n;i++)
{
_xor[i]=interact(1,i,"XOR");//_xor[i]=a[1]^a[i]
if(last[_xor[i]]!=-1)//a[1]^a[last[_xor[i]]]==a[1]^a[i]
id1=last[_xor[i]],id2=i;//a[id1]=a[id2]
last[_xor[i]]=i;
}
if(id1!=-1)//存在兩個相同的數字
{
a[id1]=a[id2]=interact(id1,id2,"AND");
a[1]=a[id1]^_xor[id1];
for(int i=2;i<=n;i++)
a[i]=_xor[i]^a[1];
}
else//所有數字都不相同
{
int id1=last[n-1];//a[1]^a[id1]=n-1 -> a[1]&a[id1]=0
int id2=id1!=2?2:3;//隨便再選一個數
int sum1=n-1;//a[1]+a[id1]
int sum2=_xor[id2]+2*interact(1,id2,"AND");//a[1]+a[id2]
int sum3=(_xor[id1]^_xor[id2])+2*interact(id1,id2,"AND");//a[id1]+a[id2]
a[1]=(sum1+sum2-sum3)/2;
for(int i=2;i<=n;i++)
a[i]=_xor[i]^a[1];
}
printf("!");
for(int i=1;i<=n;i++)
printf(" %d",a[i]);
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/yidong/226891.html
標籤：其他