題干：

六一兒童節到了，小朋友們在玩丟手絹的游戲。總共有C個小朋友，編號從1到C，他們站成一個圈，第i(1<i<=C)個人的左邊是i-1，第1個人的左邊是C。第i(1<=i<C)個人的右邊是i+1，第C個人的右邊是1。然后再給出一個常數E。剛開始的時候1號小朋友拿著手絹，接下來游戲開始，在游戲的每一輪，拿手絹的人會把手絹向右邊傳遞E－1個人，拿到手絹的人退出圈，把手絹遞給他右邊的小朋友，剩下的人向中間挨緊，把圈中的空位補滿。然后開始下一輪，如此往復。直到圈中只剩一個人。比如C＝6，E＝5的時候，出圈的順序是5，4，6，2，3，最后1號小朋友留在了圈中。

現在有2G個小朋友，要求一個最小的常數E，使得這2G個小朋友玩了G輪游戲之后，出圈的小朋友編號剛好是G+1到2G。

?

Input

多組測試數據。?
每一行給出一個整數G（ 0 < G < 14），G＝0的時候表示輸入結束。

Output

輸出多行，表示每一組數據的答案。

Sample Input

3 4 0

Sample Output

5 30

解題報告：

預處理打表過即可。

主要是學習一下vector處理這種問題的方法。

vector放入數據之后。

開始遍歷

設置一個變量為當前值，一個變量為變化后的值。

變化后的值為 （當前值+移動數-1）%(vector數組的大小）

讓vis數組標記下變化后的位置的值，表示已經被剔除了。

執行vector.earse(vector.begin()+ 變化后的值),在vector中刪除這個值。

之后讓當前值 等于 變化后的值。

一個循環結束，重復即可。

先上一個非常不清真的代碼：

#include<bits/stdc++.h>using namespace std; bool vis[105]; int n,res,cur; bool solve(int e) {memset(vis,0,sizeof(vis));int i=1;cur = 0;while(i <= (n/2)) {//這里的while也太不清真了、、 int num = 0;while(1) {if(vis[cur]==1) {cur=(cur+1)%n;continue;//這寫的太不清真了，變量加減太隨意。很容易出漏洞啊！！包括那種，高速路加油問題，變量的變化的地點要清真一點！ }cur=(cur+1)%n;if(vis[cur] == 1) continue;num++;if(num == e) {if(cur < (n/2)) return 0;vis[cur]=1;do{cur=(cur+1)%n; }while(vis[cur]);break;}}i++;}return 1; }

所以各種無輸出啊死循環啊的情況、、、?

改進以后

bool solve(int e) {memset(vis,0,sizeof(vis));cur = 0;for(int i = 1; i<=(n/2); i++) {int num = 0;while(1) {cur=(cur+1)%n;if(vis[cur] == 1) continue;num++;if(num == e) {if(cur < (n/2)) return 0;vis[cur]=1;do{cur=(cur+1)%n; }while(vis[cur]);break;}}}return 1; } int main() {int ans[20] = {0,2,7,5,30,169,441,1872,7632,1740,93313,459901,1358657,2504881};while(cin>>n) {if(n == 0) break;printf("%d\n",ans[n]);}return 0 ;}

算是可以輸出了，但是e從2到1000W遍歷的耗時太長啦！所以標解肯定不是這么做的、、說明我們的模擬有問題，然后換了STL中的vector模擬這個過程，去掉一些無用的過程。?

還有一種比較快的方法：（類似約瑟夫環的解法，不知道為什么可以這樣）

#include<bits/stdc++.h>using namespace std; typedef long long ll; const int maxn = 1e3+5; pair<int,int> pr; int arr[maxn]; int n; int ans[20] = {0,2,7,5,30,169,441,1872,7632,1740,93313,459901,1358657,2504881}; bool judge(int k) {int m = 2*n, cur = 1;for(int i=0; i<n; i++){cur = (cur+k)%m;cur==0 ? cur=m : cur=cur;if(cur<=n)return false;m--;}return true; } int main( ) {init( );while(cin>>n && n!=0){for(int i=n; ;i++){if(judge(i)){cout<<i+1<<endl;break;}if(i%(2*n)<n)i += n-1;}//cout<<ans[n]<<endl;}return 0; }

下面是用vector模擬的過程：

#include<iostream> #include<list> #include<vector> #include<algorithm> using namespace std; const int MAXN = 15;//模擬，判斷E時候合適 bool check(int G,int E){if(1+E<G) return false;vector<int> vec;for(int i=1;i<=2*G;i++){vec.push_back(i);}int vis[2*MAXN] = {0};int now = 0,next,len = 2*G+1;for(int i=0;i<G;i++){next = (now+E-1)%(vec.size());vis[vec[next]] = 1;vec.erase(vec.begin()+next);now = next % (vec.size());}//檢查for(int i=G+1;i<=2*G;i++){if(!vis[i]) return false;}return true; }//模擬得到的結果 const int E[] = {0,2,7,5,30,169,441,1872,7632,1740,93313,459901,1358657,2504881};int main() {int G; //記錄1-3的值/*得到結果**/for(int i=1;i<=13;i++){int E=2;while(!check(i,E)) ++E;cout<<E<<",";}while(cin>>G && G){cout<<E[G]<<endl;}return 0; }

?

總結

以上是生活随笔為你收集整理的【51nod - 1875】 丢手绢（约瑟夫问题，可打表，用STL模拟）的全部內容，希望文章能夠幫你解決所遇到的問題。

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