洛谷 P2755 洗牌问题

P2755 洗牌问题

题目描述

给你2N张牌，编号为1,2,3..n,n+1,..2n。这也是最初的牌的顺序。 一次洗牌是把序列变为n+1,1,n+2,2,n+3,3,n+4,4..2n,n。可以证 明，对于任意自然数N，都可以在经过M次洗牌后第一次重新得到 初始的顺序。编程对于小于100000的自然数N，求出M的值。

输入输出格式

输入格式：

 

输入：N

 

输出格式：

 

输出：M

 

输入输出样例

输入样例#1： 复制

20

输出样例#1： 复制

20

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
int n,ans;
int num[3000010],bns[3000010];
int main(){
    scanf("%d",&n);
    for(int i=1;i<=2*n;i++)    num[i]=i;
    ans++;
    for(int i=1;i<=2*n;i++)
        if(i%2)    bns[i]=num[n+i/2+1];
        else bns[i]=num[i/2];
    for(int i=1;i<=2*n;i++)    num[i]=bns[i];
    while(1){
        int flag=0;
        for(int i=1;i<=2*n;i++)
            if(num[i]!=i)    flag=1;
        if(!flag)    break;
        ans++;
        for(int i=1;i<=2*n;i++)
            if(i%2)    bns[i]=num[n+i/2+1];
            else bns[i]=num[i/2];
        for(int i=1;i<=2*n;i++)    num[i]=bns[i];
    }
    cout<<ans;
}

思路：只模拟1好点的下标。

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
int n,pos,ans;
int main(){
    scanf("%d",&n);
    if(n==0){ cout<<"1";return 0; }
    pos=1;
    ans++;pos*=2;
    while(1){
        if(pos==1)    break;
        ans++;
        if(pos>n)    pos=pos*2-n*2-1;
        else pos*=2;
    }
    printf("%d",ans);
}