西安邀请赛-L（打表找规律）

一时失言乱红尘 2021-12-21 01:05 288阅读 0赞

题目链接：https://nanti.jisuanke.com/t/39279

题意：给定n个不同的数表示的序列，定义两种操作：1. 交换前一半和后一半（如果有奇数个，则中间的不管）。2. 交换每个偶数位和它之前的数（如果有奇数个，最后一个不管）。问通过这两种操作，可以得到多少个不同的序列。

思路：典型的打表找规律的题，下次比赛吸取教训。打表的代码如下：

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include<cstdio>
    using namespace std;
    
    int a[10005],b[10005];
    int n,ans;
    
    bool check(){
        bool flag=1;
        for(int i=1;i<=n;++i)
            if(a[i]!=b[i]){
                flag=0;
                break;
            }
        return flag;
    }
    
    int main(){
        for(n=1;n<=30;++n){
            int hf=n/2;
            ans=0;
            for(int i=1;i<=n;++i)
                a[i]=i,b[i]=i;
            while(1){
                for(int i=1;i<=hf;++i){
                    int tmp=b[i];
                    b[i]=b[n-hf+i];
                    b[n-hf+i]=tmp;
                }
                if(check()) break;
                ++ans;
                for(int i=1;i<=n-1;i+=2){
                    int tmp=b[i];
                    b[i]=b[i+1];
                    b[i+1]=tmp;
                }
                if(check()) break;
                ++ans;
            }
            printf("%d:%d\n",n,ans+1);
        }
        return 0;
    }

然后就可以找到规律了：

n%4==0: ans=4

n%4==1: if(n==1) ans=1

else ans=2\*n

n%4==2: ans=n

n%4==3: if(n==3) ans=6

else ans =12

AC代码：

转载于:https://www.cnblogs.com/FrankChen831X/p/10927161.html

[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20211220/95477d0c713c4773afc8ecf0bf56a00a.png