题解 P2227 【[HNOI2001]洗牌机】

楚泫 · 2018-09-21 18:59:02 · 题解

纯枚举.（qwq）

• 最开始读错了题意，以为是正着推。于是写完后题解对了（特殊情况），交上后30分重新读题才发现不对QAQ
• 输了几组数据打表找规律，于是发现：

  逆推次数=周期数-正推次数（%周期数）

由于逆推过程复杂，蒟蒻实在想不出qaq……思路如下：

• 洗牌过程存在周期数，因此先正推得出周期数 （本题数据不考虑洗牌到一定次数后一直相同，如“12345”这样的情况）
• 于是可求出逆推次数
• 根据逆推的次数正推一下
• 更新，输出！

  代码如下：

#include<iostream>
#include<cstdio>
using namespace std;
int n,s,a[1005],b[1005],c[1005],cnt,z;
int main(){
    scanf("%d%d",&n,&s);
    for(int i=1;i<=n;i++){  //读入 
        scanf("%d",&a[i]);
        b[i]=a[i];  //令b数组与a相同，用于修改判断 
    }           
    for(z=1;z<=n;z++){      //正推（洗牌），推导出第几次时和a相同，得到的z即为周期数 
        for(int j=1;j<=n;j++){
            c[j]=b[b[j]];   //c数组为b正推（洗牌）出的下一个 
        }
        for(cnt=1;cnt<=n;cnt++){
            if(a[cnt]!=c[cnt]) break;   //一旦不同退出循环 
        }
        if(cnt==n+1) break;     //判断是否与a相同，相同则退出循环 
        for(int j=1;j<=n;j++){
            b[j]=c[j];  //让b数组更新为当前数组 
        }
    }
    s=z-s%z;    //重点！倒推次数即周期数-正推次数（%周期） 
    while(s--){     //洗牌 
        for(int j=1;j<=n;j++) b[j]=a[a[j]];
        for(int j=1;j<=n;j++) a[j]=b[j];
    }    
    for(int i=1;i<=n;i++) cout<<a[i]<<" ";  //输出 
}