当前位置: 代码迷 >> 综合 >> 【51NOD-1875-丢手绢】 约瑟夫环+暴力
  详细解决方案

【51NOD-1875-丢手绢】 约瑟夫环+暴力

热度:16   发布时间:2023-12-29 02:36:29.0

51NOD1875丢手绢
题意就是约瑟夫环问题,n个人每次向后传递k次然后这个人退出游戏,问最后一个人是谁。
这道题给出n,一共2*n个人进行游戏,要求前n个退出游戏的人序号在n+1-2n之间,
由于这道题n只有14,我们只要暴力算出14种情况即可,但是这里暴力的姿势需要优雅,我们用vector模拟环,用erase模拟退出游戏,然后暴力算就可以了。
代码

#include<stdio.h>
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn =40;
int vis[maxn];
int a[maxn]={
    0,2,7,5,30,169,441,1872,7632,1740,93313,459901,1358657,2504881};
int  solve(int G,int E)//暴力打表代码
{
    int tmp=0;vector<int> v;v.clear();for(int i=0;i<=2*G;i++) vis[i]=0;for(int i=1;i<=2*G;i++) v.push_back(i);for(int i=0;i<G;i++){
    tmp=(tmp+E-1)%(2*G-i);vis[v[tmp]]=1;v.erase(v.begin()+tmp);}for(int i=G+1;i<=2*G;i++) if(!vis[i]) return 0;return 1;
}
int main()
{
    
// for(int i=1;i<=13;i++)
// {
    
// for(int j=1;j<=10000000;j++)
// {
    
// if(solve(i,j))
// {
    
// cout<<j<<",";
// break;
// }
// }
// }int n;while(scanf("%d",&n)!=EOF){
    if(n==0) break;printf("%d\n",a[n]);}return 0;
}