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

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

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

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

#include<cstdio>

using namespace std;

int a[],b[];

int n,ans;

bool check(){

    bool flag=;

    for(int i=;i<=n;++i)

        if(a[i]!=b[i]){

            flag=;

            break;

        }

    return flag;

}

int main(){

    for(n=;n<=;++n){

        int hf=n/;

        ans=;

        for(int i=;i<=n;++i)

            a[i]=i,b[i]=i;

        while(){

            for(int i=;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=;i<=n-;i+=){

                int tmp=b[i];

                b[i]=b[i+];

                b[i+]=tmp;

            }

            if(check()) break;

            ++ans;

        }

        printf("%d:%d\n",n,ans+);

    }

    return ;

}

然后就可以找到规律了：

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代码：

#include<cstdio>

using namespace std;

int a[],b[];

int n,ans;

bool check(){

    bool flag=;

    for(int i=;i<=n;++i)

        if(a[i]!=b[i]){

            flag=;

            break;

        }

    return flag;

}

int main(){

    for(n=;n<=;++n){

        int hf=n/;

        ans=;

        for(int i=;i<=n;++i)

            a[i]=i,b[i]=i;

        while(){

            for(int i=;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=;i<=n-;i+=){

                int tmp=b[i];

                b[i]=b[i+];

                b[i+]=tmp;

            }

            if(check()) break;

            ++ans;

        }

        printf("%d:%d\n",n,ans+);

    }

    return ;

}

巴特西

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

最新文章

热门文章