正題

題目鏈接:https://codeforces.com/contest/1556/problem/D

---

題目大意

現(xiàn)在有$n$個你不知道的數(shù)字，你有兩種詢問操作

詢問兩個下標(biāo)的數(shù)字的$and$

詢問兩個下標(biāo)的數(shù)字的$or$

要求在$2n$次操作以內(nèi)求出第$k$小的數(shù)字

$1\le n\le 10^4,0\le a_i\le 10^9$

---

解題思路

顯示我們?nèi)?span id="ze8trgl8bvbq" class="katex--inline">$and$之后為$0$且$or$之后為$1$的位就可以得到兩個數(shù)字的異或，所以我們可以通過$2n?2$次詢問得到所有數(shù)字之間的異或值，那么此時我們就只需要知道一個數(shù)字就可以得到其他所有的。

然后考慮怎么求某一個數(shù)字，我們前面的步驟中拿$1$去$or$和$and$其他所有的值，不難發(fā)現(xiàn)每次我們除了知道異或值還能確定這兩個數(shù)字異或之后為$0$的位上的具體值。

那么我們不知道位的肯定是$1$和其他所有數(shù)字都不同的，也就是這些位上除了$1$其他數(shù)字都相同，那么我們直接拿另外兩個數(shù)$and/or$一下再取這些位上的值就好了。

這樣詢問次數(shù)就是$2n?1$次，可以通過本題。

---

code

#include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int N=1e4+10; int n,k,a[N],p[N]; int main() {scanf("%d%d",&n,&k);int MS=(1<<30)-1,ans=0,bns=0;for(int i=2,x,y;i<=n;i++){printf("and 1 %d\n",i);fflush(stdout);scanf("%d",&x);printf("or 1 %d\n",i);fflush(stdout);scanf("%d",&y);y^=MS;p[i]=(MS^(x|y));ans|=x;bns|=y;}int c=MS^(ans|bns),cns;printf("and 2 3\n");fflush(stdout);scanf("%d",&cns);cns&=c;a[1]=(c^cns)|ans;for(int i=2;i<=n;i++)a[i]=a[1]^p[i];sort(a+1,a+1+n);printf("finish %d\n",a[k]);fflush(stdout);return 0; }

總結(jié)

以上是生活随笔為你收集整理的CF1556D-Take a Guess【交互】的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。