题解：P10312 [SHUPC 2024] 栅栏密码

· · 题解

思路：

观察题目描述发现当 h 等于三时，一共分成了三行。

先看第一行，打乱前的第一第五第九个字符分别变成了打乱后的第一二三个字符，相邻两个字符之间原本相差 h-1 的两倍。

再看第二行，首行和尾行的间隔依旧不变，假设列数为 i，会有两种情况：

  1. 若当前数为第二行的奇数个字符的时候，下一个字符是 h-i 的两倍。
  2. 若当前数为第二行的偶数个字符的时候，下一个字符是 i-1 的两倍。

第 h 行与第一行是一样的。

再画个只有数字的图来验证我们的思路。

观察后我们可以发现，当 h 为三时，一共分成了三行，打乱前的一、五、九分别变成了打乱后的第一、二、三个数，相邻两个数之间相差四也就是 h-1 的两倍，第 h 行与第一行相同。再看第二行你会发现，首行和尾行的间隔不变假设列数为 i，当前数为第二行的第奇数个数的时候，下一个数字是 h-i 的两倍，若当前数为第二行的第偶数个数的时候，下一个数字是 i-1 的两倍。而且每一行的第一个数字就是这一行的行数。

与我们上面的思路相同，所以可以写成代码。

完整代码：

#include<bits/stdc++.h>
using namespace std;
string s;
char ans[100080]/* 存答案 */;
int han=0/* 第几行 */;
int h,len,pd1,pd2/* 用来判断现在的位置的字符是奇数还是偶数 */;
int check(){// 如思路
    if(han==1||han==h)return pd1+(h-1)*2;
    else{
        if(pd2%2==1)return pd1+(h-han)*2;
        else return pd1+2*(han-1);
    }
}
int main(){// 如思路
    cin>>h;
    cin>>s;
    len=s.size();
    s=" "+s;
    han=pd1=pd2=1;
    for(int i=1;i<=len;i++){ 
        ans[pd1]=s[i];
        pd1=check();
        pd2++;
        if(pd1>len){
            han++;
            pd1=han;
            pd2=1;
        }
    }
    for(int i=1;i<=len;i++)cout<<ans[i];
    return 0;
}