题解 P7750 [COCI2013-2014#2] SLOM

· · 题解

我们对 6 个字符进行变化，我们不难发现变换是这样的（此处显示的是一开始是第几个字符）：

一开始：1,2,3,4,5,6

第一次：1,6,2,5,3,4

第二次：1,4,6,2,3,5

第三次：1,5,4,2,6,3

第四次：1,3,5,6,4,2

第五次：1,2,3,4,5,6

这启示我们，变换序列是存在循环的！

经过多次尝试，我们发现，字符串长度为 4，循环次数为 3，但是如果字符串长度为 8，循环次数为 4，而当字符串长度为 11，循环次数为 6……得出结论：字符串长度与单词循环次数没有直接关系。

此时我们可以考虑通过代码暴力算出对于长度为 n 的单词单次循环次数。写一个暴力的变换以及对应的检查就行了。思路就是先压一个序列，让它不停地变换直到回到原来压的的序列的样子（比如我压的就是 1 到 n）。

此时我们有了单次循环次数，我们可以大大地减少操作的次数。而对于后续的操作，我们可以推出它从最后一次循环结束后它又做了多少次变换 r，即 r \gets X\bmod \operatorname{solve}(|s|)（其中 X 和 s 均为原题目中的变量，\operatorname{solve} 函数为求循环次数的函数，下同）。

根据循环的特征，在一个单次循环消耗 rd 次的循环中，如果我们做了 x (x<rd) 次，要想还原，我们可以倒推 x 次，也可以再做 rd-x 次，所以，我们只需让现有的字符串再变换 \operatorname{solve}(|s|)-r 次就行了。

另附：AC 代码（不要抄！）。

#include<bits/stdc++.h>
using namespace std;
string st;int x,rd,rin;
vector<int>a;
bool check(int t){
    if(t==0) return 0;
    for(int i=0;i<a.size();++i){
        if(a[i]!=i+1) return 0;
    }
    return 1;
}
int solve(int n){
    a.clear();
    int i;
    for(i=1;i<=n;++i) a.push_back(i);
    for(i=0;;++i){
//      printf("%dth change:",i);
//      for(int j=0;j<n;++j) printf("%d ",a[j]);
//      puts("");
        if(check(i)) break;
        for(int j=0;j<a.size()>>1;++j){ 
            int tmp=a.back();
            a.pop_back();
            a.insert(a.begin()+(j<<1|1),tmp);
        }
    } 
//  printf("change time:%d",i);
    return i;
}
int main(){
    scanf("%d",&x);
    cin>>st;
    rd=solve(st.size());
    rin=x%rd;
    for(int i=0;i<rd-rin;++i){
        for(int j=0;j<st.size()>>1;++j){ 
            string tmp="";
            tmp+=(char)st[st.size()-1];
            st.erase(st.size()-1,1);
            st.insert(j<<1|1,tmp);
        }
    }
    cout<<st;
    return 0;}