做网站应该掌握的技术,技术支持 金华网站建设,custed谁做的网站,wordpress本地添加图片不显示图片题干#xff1a;
六一儿童节到了#xff0c;小朋友们在玩丢手绢的游戏。总共有C个小朋友#xff0c;编号从1到C#xff0c;他们站成一个圈#xff0c;第i(1iC)个人的左边是i-1#xff0c;第1个人的左边是C。第i(1iC)个人的右边是i1#xff0c;第C个人的…题干
六一儿童节到了小朋友们在玩丢手绢的游戏。总共有C个小朋友编号从1到C他们站成一个圈第i(1iC)个人的左边是i-1第1个人的左边是C。第i(1iC)个人的右边是i1第C个人的右边是1。然后再给出一个常数E。刚开始的时候1号小朋友拿着手绢接下来游戏开始在游戏的每一轮拿手绢的人会把手绢向右边传递E1个人拿到手绢的人退出圈把手绢递给他右边的小朋友剩下的人向中间挨紧把圈中的空位补满。然后开始下一轮如此往复。直到圈中只剩一个人。比如C6E5的时候出圈的顺序是54623最后1号小朋友留在了圈中。
现在有2G个小朋友要求一个最小的常数E使得这2G个小朋友玩了G轮游戏之后出圈的小朋友编号刚好是G1到2G。 Input
多组测试数据。 每一行给出一个整数G 0 G 14G0的时候表示输入结束。
Output
输出多行表示每一组数据的答案。
Sample Input
3
4
0
Sample Output
5
30
解题报告
预处理打表过即可。
主要是学习一下vector处理这种问题的方法。
vector放入数据之后。
开始遍历
设置一个变量为当前值一个变量为变化后的值。
变化后的值为 当前值移动数-1%(vector数组的大小
让vis数组标记下变化后的位置的值表示已经被剔除了。
执行vector.earse(vector.begin() 变化后的值),在vector中删除这个值。
之后让当前值 等于 变化后的值。
一个循环结束重复即可。
先上一个非常不清真的代码
#includebits/stdc.husing namespace std;
bool vis[105];
int n,res,cur;
bool solve(int e) {memset(vis,0,sizeof(vis));int i1;cur 0;while(i (n/2)) {//这里的while也太不清真了、、 int num 0;while(1) {if(vis[cur]1) {cur(cur1)%n;continue;//这写的太不清真了变量加减太随意。很容易出漏洞啊包括那种高速路加油问题变量的变化的地点要清真一点 }cur(cur1)%n;if(vis[cur] 1) continue;num;if(num e) {if(cur (n/2)) return 0;vis[cur]1;do{cur(cur1)%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(cur1)%n;if(vis[cur] 1) continue;num;if(num e) {if(cur (n/2)) return 0;vis[cur]1;do{cur(cur1)%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(cinn) {if(n 0) break;printf(%d\n,ans[n]);}return 0 ;}
算是可以输出了但是e从2到1000W遍历的耗时太长啦所以标解肯定不是这么做的、、说明我们的模拟有问题然后换了STL中的vector模拟这个过程去掉一些无用的过程。
还有一种比较快的方法类似约瑟夫环的解法不知道为什么可以这样
#includebits/stdc.husing namespace std;
typedef long long ll;
const int maxn 1e35;
pairint,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 i0; in; i){cur (curk)%m;cur0 ? curm : curcur;if(curn)return false;m--;}return true;
}
int main( )
{init( );while(cinn n!0){for(int in; ;i){if(judge(i)){couti1endl;break;}if(i%(2*n)n)i n-1;}//coutans[n]endl;}return 0;
}下面是用vector模拟的过程
#includeiostream
#includelist
#includevector
#includealgorithm
using namespace std;
const int MAXN 15;//模拟判断E时候合适
bool check(int G,int E){if(1EG) return false;vectorint vec;for(int i1;i2*G;i){vec.push_back(i);}int vis[2*MAXN] {0};int now 0,next,len 2*G1;for(int i0;iG;i){next (nowE-1)%(vec.size());vis[vec[next]] 1;vec.erase(vec.begin()next);now next % (vec.size());}//检查for(int iG1;i2*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 i1;i13;i){int E2;while(!check(i,E)) E;coutE,;}while(cinG G){coutE[G]endl;}return 0;
}
