P10312 [SHUPC 2024] 栅栏密码

· · 题解

P10312 [SHUPC 2024] 栅栏密码 题解

题目链接

题意分析

定义一种加密方式，现给出经过这种加密的密文 s 和加密时的参数 h，要求求出明文，也就是加密前的字符串 plain。

加密方式分析

当 h=3 时，明文一共分成了三行，打乱前的第 1,5,9 号分别变成了打乱后的第 1,2,3 号，这两个数之间相差 4，也就是 (h-1) \times 2。同时，由栅栏的对称性可知，第 h 行与第 1 行规律相同。

再看第 2 行，会是 2n-5 吗？我将数据放大再研究一番，当 |s|=35,h=5 时，如下图所示：

我们发现：首行和尾行的间隔依旧不变，假设当前行数为 i，当当前数为第 i 行的奇数的时候，下一个数字 (h-i) \times 2，若当前数为第 i 行偶数的时候，下一个数字是 (i-1) \times 2。而每一行的第一个数字对应的列数就是这一行的行数。

参考代码

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 10;
char str[maxn];//记录密文
char ans[maxn];//记录明文
int key, line, len, sit, ssit; //用于判断当前字符的位置为奇数还是偶数
int check() {
    if (line == 1 || line == key) {//第一行和最后一行
        return sit + (key - 1) * 2;
    } else {
        if (ssit % 2 == 1) {//奇数位置
            return sit + (key - line) * 2;
        } else {
            return sit + 2 * (line - 1);//偶数位置
        }
    }
}
int main() {
    int i;
    cin >> key;
    cin >> str;
    len = strlen(str);
    for (i = len; i > 0; i--)str[i] = str[i - 1];
    //为了直观一些，统一前挪一位，方便操作
    line = 1;
    sit = 1;
    ssit = 1;
    for (i = 1; i <= len; i++) { //将密码对应在明文上
        ans[sit] = str[i];
        sit = check();
        ssit++;
        if (sit > len) { //超出范围，往回构造
            line++;//到下一行了
            sit = line; //每一行第一个字符的位置恰好与行数的数字一样
            ssit = 1;
        }
    }
    for (i = 1; i <= len; i++) printf("%c", ans[i]);
    return 0;
}

完结撒花~