link

題意： $n$個人圍成一圈，一開始每個人都有$k$張卡片，每回合$n?1$個人會給左邊$?\frac{x}{2}?$，給右邊$?\frac{x}{2}?$，剩下一個人會把所有的卡片都給右邊。每次詢問一個位置，返回當前位置人擁有的卡片。詢問不超過1000次，找到只把卡片給右邊人的位置。

思路： 通過模擬可以發現，這個特殊人的卡片數量是不變的，且從他開始向右卡片數量$>k$的人是隨著回合數增加而增加的，最后會達到一個不變的平衡。讓后發現詢問次數不超過1000，而$\sqrt{1e5}=314(大概)。$這就提示我們可以分塊來做。我們可以先讓他進行$\sqrt{n}$回合，讓后我們從$1$開始，每次加$\sqrt{n}$，直至當前的人的卡片$>k$，讓后我們從這個人的位置往左走到第一個卡片數量$<=k$的位置即為我們需要求的位置，輸出即可。
但是這樣會有點小問題，如果我們進行$\sqrt{n}$輪后$>k$的人數不足$\sqrt{n}$怎么辦呢？比如例子：$n=4$且$k=2$，特殊的人在第一個位置，這樣最終$>k$的人為1，讓后我就把每次加$\sqrt{n}$改成了加$\sqrt{n}?1$，這樣就解決問題了。我也不會證，但是確實這樣是可以過的。

//#pragma GCC optimize(2) #include<cstdio> #include<iostream> #include<string> #include<cstring> #include<map> #include<cmath> #include<cctype> #include<vector> #include<set> #include<queue> #include<algorithm> #include<sstream> #include<ctime> #include<cstdlib> #define X first #define Y second #define L (u<<1) #define R (u<<1|1) #define pb push_back #define mk make_pair #define Mid (tr[u].l+tr[u].r>>1) #define Len(u) (tr[u].r-tr[u].l+1) #define random(a,b) ((a)+rand()%((b)-(a)+1)) #define db puts("---") using namespace std;//void rd_cre() { freopen("d://dp//data.txt","w",stdout); srand(time(NULL)); } //void rd_ac() { freopen("d://dp//data.txt","r",stdin); freopen("d://dp//AC.txt","w",stdout); } //void rd_wa() { freopen("d://dp//data.txt","r",stdin); freopen("d://dp//WA.txt","w",stdout); }typedef long long LL; typedef unsigned long long ULL; typedef pair<int,int> PII;const int N=1000010,mod=1e9+7,INF=0x3f3f3f3f; const double eps=1e-6;int n,k;int query(int pos) {printf("? %d\n",pos); fflush(stdout);int x; scanf("%d",&x);return x; }int main() { // ios::sync_with_stdio(false); // cin.tie(0);scanf("%d%d",&n,&k);int block=sqrt(n);for(int i=1;i<=block;i++) query(i);for(int i=1;i<=n;i+=block-1){if(query(i)>k){int pos=i-1;if(pos==0) pos=n;while(query(pos)>k){pos--;if(pos==0) pos=n;}printf("! %d\n",pos); fflush(stdout);return 0;}}return 0; } /**/

總結

以上是生活随笔為你收集整理的Codeforces Round #694 (Div. 2) E. Strange Shuffle 交互 + 思维分块的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。