密码破解者

GitHub 跳转原题关系图返回列表

把所有加密操作按相反顺序依次撤销，其中分别实现栅栏密码、维吉尼亚密码和 QWE 键盘码的逆变换即可还原原文。

OJ: luogu

题目 ID: P2636

难度:普及/提高-

标签:字符串模拟推导

日期: 2026-06-20 23:48

题意

题目给出一个最终密文，以及它曾经经历过的 N 层加密方式。

加密方式只有三种：

栅栏密码
维吉尼亚密码
QWE 键盘码

输入中的操作顺序就是真实加密顺序，要求输出最后解密得到的原文。

思路

先看一个可以直接验证想法的朴素解：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144#include <bits/stdc++.h>
using namespace std;

struct Operation {
    int type;
    int rail;
    string key;
};

int n;
string s;
vector<Operation> ops;

char qwe_inv_upper[26];

void build_qwe_inverse() {
    string keyboard = "QWERTYUIOPASDFGHJKLZXCVBNM";
    for (int i = 0; i < 26; i++) {
        qwe_inv_upper[keyboard[i] - 'A'] = char('A' + i);
    }
}

int letter_value(char ch) {
    if ('A' <= ch && ch <= 'Z') {
        return ch - 'A';
    }
    if ('a' <= ch && ch <= 'z') {
        return ch - 'a';
    }
    return 0;
}

char decode_vigenere_char(char ch, int shift) {
    if ('A' <= ch && ch <= 'Z') {
        int x = ch - 'A';
        x = (x - shift + 26) % 26;
        return char('A' + x);
    }
    if ('a' <= ch && ch <= 'z') {
        int x = ch - 'a';
        x = (x - shift + 26) % 26;
        return char('a' + x);
    }
    return ch;
}

char decode_qwe_char(char ch) {
    if ('A' <= ch && ch <= 'Z') {
        return qwe_inv_upper[ch - 'A'];
    }
    if ('a' <= ch && ch <= 'z') {
        char up = char(ch - 'a' + 'A');
        char plain = qwe_inv_upper[up - 'A'];
        return char(plain - 'A' + 'a');
    }
    return ch;
}

string decode_vigenere(const string &cipher, const string &key) {
    string plain = cipher;
    int key_len = (int) key.size();
    for (int i = 0; i < (int) plain.size(); i++) {
        int shift = letter_value(key[i % key_len]);
        plain[i] = decode_vigenere_char(plain[i], shift);
    }
    return plain;
}

string decode_qwe(const string &cipher) {
    string plain = cipher;
    for (int i = 0; i < (int) plain.size(); i++) {
        plain[i] = decode_qwe_char(plain[i]);
    }
    return plain;
}

// brute.cpp：更直观的栅栏密码逆变换。
// 直接把每一列的字符回填到每一组对应的位置，再顺序读出所有分组。
string decode_rail_bruteforce(const string &cipher, int width) {
    int len = (int) cipher.size();
    int groups = (len + width - 1) / width;

    vector<int> row_len(groups, 0);
    for (int i = 0; i < groups; i++) {
        row_len[i] = min(width, len - i * width);
    }

    vector<string> rows(groups);
    for (int i = 0; i < groups; i++) {
        rows[i] = string(row_len[i], '?');
    }

    int pos = 0;
    for (int col = 0; col < width; col++) {
        for (int row = 0; row < groups; row++) {
            if (col < row_len[row]) {
                rows[row][col] = cipher[pos];
                pos++;
            }
        }
    }

    string plain;
    plain.reserve(len);
    for (int row = 0; row < groups; row++) {
        plain += rows[row];
    }
    return plain;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    build_qwe_inverse();

    cin >> n;
    cin >> s;

    ops.resize(n);
    for (int i = 0; i < n; i++) {
        cin >> ops[i].type;
        ops[i].rail = 0;
        ops[i].key.clear();
        if (ops[i].type == 1) {
            cin >> ops[i].rail;
        } else if (ops[i].type == 2) {
            cin >> ops[i].key;
        }
    }

    for (int i = n - 1; i >= 0; i--) {
        if (ops[i].type == 1) {
            s = decode_rail_bruteforce(s, ops[i].rail);
        } else if (ops[i].type == 2) {
            s = decode_vigenere(s, ops[i].key);
        } else {
            s = decode_qwe(s);
        }
    }

    cout << s << '\n';
    return 0;
}

这题的主框架其实很直接：

正向是按 1 -> 2 -> ... -> N 层加密
逆向解密就必须按 N -> N-1 -> ... -> 1 的顺序逐层撤销

所以关键只剩三种密码的逆操作怎么写。

QWE 键盘码最简单，本质只是 26 个字母的一一映射。预处理一个“密文字母到原文字母”的逆表，逐字符替换即可。

维吉尼亚密码也不难。加密相当于把当前字母按密钥字母的值向后平移，解密时就向前平移同样的位数，并且密钥长度不足时循环使用。

真正稍微绕一点的是栅栏密码。

它的加密方式是：

先把原文按长度 L 分组
再按列依次把字符取出来

因此解密时要反过来：

先根据字符串长度和 L，算出每一列应该有多少字符
按这些长度把密文切成若干列
再按“每组从左到右”的顺序重新拼回原文

把这三个逆函数都写好后，从后往前套一遍就行。

代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149#include <bits/stdc++.h>
using namespace std;

struct Operation {
    int type;     // 1=栅栏密码，2=维吉尼亚密码，3=QWE 键盘码
    int rail;     // 栅栏密码分组长度
    string key;   // 维吉尼亚密码密钥
};

int n;
string s;
vector<Operation> ops;

char qwe_inv_upper[26];

// 建立 QWE 键盘码的逆映射：密文字母 -> 原文字母。
void build_qwe_inverse() {
    string keyboard = "QWERTYUIOPASDFGHJKLZXCVBNM";
    for (int i = 0; i < 26; i++) {
        qwe_inv_upper[keyboard[i] - 'A'] = char('A' + i);
    }
}

int letter_value(char ch) {
    if ('A' <= ch && ch <= 'Z') {
        return ch - 'A';
    }
    if ('a' <= ch && ch <= 'z') {
        return ch - 'a';
    }
    return 0;
}

char decode_vigenere_char(char ch, int shift) {
    if ('A' <= ch && ch <= 'Z') {
        int x = ch - 'A';
        x = (x - shift + 26) % 26;
        return char('A' + x);
    }
    if ('a' <= ch && ch <= 'z') {
        int x = ch - 'a';
        x = (x - shift + 26) % 26;
        return char('a' + x);
    }
    return ch;
}

char decode_qwe_char(char ch) {
    if ('A' <= ch && ch <= 'Z') {
        return qwe_inv_upper[ch - 'A'];
    }
    if ('a' <= ch && ch <= 'z') {
        char up = char(ch - 'a' + 'A');
        char plain = qwe_inv_upper[up - 'A'];
        return char(plain - 'A' + 'a');
    }
    return ch;
}

// 逆向还原维吉尼亚密码。
string decode_vigenere(const string &cipher, const string &key) {
    string plain = cipher;
    int key_len = (int) key.size();
    for (int i = 0; i < (int) plain.size(); i++) {
        int shift = letter_value(key[i % key_len]);
        plain[i] = decode_vigenere_char(plain[i], shift);
    }
    return plain;
}

// 逆向还原 QWE 键盘码。
string decode_qwe(const string &cipher) {
    string plain = cipher;
    for (int i = 0; i < (int) plain.size(); i++) {
        plain[i] = decode_qwe_char(plain[i]);
    }
    return plain;
}

// 栅栏密码逆变换：
// 已知加密结果是“按列依次取出”，这里按每一列的长度把字符串切开，再按行拼回去。
string decode_rail(const string &cipher, int width) {
    int len = (int) cipher.size();
    int groups = (len + width - 1) / width;
    int rem = len % width;

    vector<int> column_len(width, groups);
    if (rem != 0) {
        for (int col = rem; col < width; col++) {
            column_len[col]--;
        }
    }

    vector<int> start(width, 0);
    int pos = 0;
    for (int col = 0; col < width; col++) {
        start[col] = pos;
        pos += column_len[col];
    }

    string plain;
    plain.reserve(len);

    for (int row = 0; row < groups; row++) {
        for (int col = 0; col < width; col++) {
            if (row < column_len[col]) {
                plain.push_back(cipher[start[col] + row]);
            }
        }
    }

    return plain;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    build_qwe_inverse();

    cin >> n;
    cin >> s;

    ops.resize(n);
    for (int i = 0; i < n; i++) {
        cin >> ops[i].type;
        ops[i].rail = 0;
        ops[i].key.clear();
        if (ops[i].type == 1) {
            cin >> ops[i].rail;
        } else if (ops[i].type == 2) {
            cin >> ops[i].key;
        }
    }

    // 输入给出的是正向加密顺序，所以解密时要倒着撤销。
    for (int i = n - 1; i >= 0; i--) {
        if (ops[i].type == 1) {
            s = decode_rail(s, ops[i].rail);
        } else if (ops[i].type == 2) {
            s = decode_vigenere(s, ops[i].key);
        } else {
            s = decode_qwe(s);
        }
    }

    cout << s << '\n';
    return 0;
}

复杂度

设字符串长度为 m，加密层数为 N。

每次逆变换都只线性扫描字符串一次，所以总时间复杂度是：

$O(N * m)$

空间复杂度是：

$O(m + N)$

总结

这题没有难在复杂算法，而是难在“把题目描述准确翻译成逆操作”。

做法的核心就一句话：

所有操作倒着做
分别把三种密码的逆变换写正确

P2636 密码破解者

题目背景

1941 年 12 月 7 日凌晨，珍珠港驻守美军通信员截获了一份日军电报。早上 8 时日军的正式进攻就会展开，为了减少太平洋战场伤亡，你被指派去协助破解密文。情报部门已得知了密文加密的层数和每层加密的方法。由于时间紧急，你只剩 1 秒的时间来破解日军的密文。

题目描述

据情报得知日军共有 $3$ 种加密方式：

一、栅栏密码：

所谓栅栏密码，就是把要加密的明文分成 $L$ 个一组，然后把每组的第 $1$ 个字连起来，形成一段无规律的话。一般比较常见的是 $2$ 栏的栅栏密码。

比如明文：THERE IS A CIPHER
去掉空格后变为：THEREISACIPHER
两个一组，得到：TH ER EI SA CI PH ER
先取出第一个字母：TEESCPE
再取出第二个字母：HRIAIHR
连在一起就是：TEESCPEHRIAIHR

这样就得到我们需要的密码了。

但也可能有更多的栏数。

注：若明文长度不能整除栏数，则分组后剩下的单独为一组，如：

THERE IS A CIPHER， $3$ 栏加密分组为：THE REI SAC IPH ER

先后取出第一二三个字母(最后一组只能取前两个)，加密后为: TRSIE HEAPR EICH（去掉空格）。

二、维吉尼亚(Vigenère)密码：

维吉尼亚密码首先应用了“密钥”的思想，其在密码界具有十分重要的意义。

在密码学中，我们称需要加密的信息为明文，用 $M$ 表示；称加密后的信息为密文，用 $C$ 表示；而密钥是一种参数，是将明文转换为密文或将密文转换为明文的算法中输入的数据，记为 $k$ 。在 Vigenère 密码中，密钥 $k$ 是一个字母串， $k=k_1k_2\cdots k_n$ 。当明文 $M=m_1m_2\cdots m_n$ 时，得到的密文 $C=c_1c_2\cdots c_n$ ，其中 $c_i=m_i\oplus k_i$ ，运算 $\oplus$ 的规则如下表所示：

A B C D E F G H I J K L M N O P Q R S T U V W X Y Z

A -A B C D E F G H I J K L M N O P Q R S T U V W X Y Z

B -B C D E F G H I J K L M N O P Q R S T U V W X Y Z A

C -C D E F G H I J K L M N O P Q R S T U V W X Y Z A B

D -D E F G H I J K L M N O P Q R S T U V W X Y Z A B C

E -E F G H I J K L M N O P Q R S T U V W X Y Z A B C D

F -F G H I J K L M N O P Q R S T U V W X Y Z A B C D E

G -G H I J K L M N O P Q R S T U V W X Y Z A B C D E F

H -H I J K L M N O P Q R S T U V W X Y Z A B C D E F G

I -I J K L M N O P Q R S T U V W X Y Z A B C D E F G H

J -J K L M N O P Q R S T U V W X Y Z A B C D E F G H I

K -K L M N O P Q R S T U V W X Y Z A B C D E F G H I J

L -L M N O P Q R S T U V W X Y Z A B C D E F G H I J K

M -M N O P Q R S T U V W X Y Z A B C D E F G H I J K L

N -N O P Q R S T U V W X Y Z A B C D E F G H I J K L M

O -O P Q R S T U V W X Y Z A B C D E F G H I J K L M N

P -P Q R S T U V W X Y Z A B C D E F G H I J K L M N O

Q -Q R S T U V W X Y Z A B C D E F G H I J K L M N O P

R -R S T U V W X Y Z A B C D E F G H I J K L M N O P Q

S -S T U V W X Y Z A B C D E F G H I J K L M N O P Q R

T -T U V W X Y Z A B C D E F G H I J K L M N O P Q R S

U -U V W X Y Z A B C D E F G H I J K L M N O P Q R S T

V -V W X Y Z A B C D E F G H I J K L M N O P Q R S T U

W -W X Y Z A B C D E F G H I J K L M N O P Q R S T U V

X -X Y Z A B C D E F G H I J K L M N O P Q R S T U V W

Y -Y Z A B C D E F G H I J K L M N O P Q R S T U V W X

Z -Z A B C D E F G H I J K L M N O P Q R S T U V W X Y

Vigenère 加密在操作时需要注意：

当明文 M 的长度大于密钥 k 的长度时，将密钥 k 重复使用。

例如，明文 M=Helloworld，密钥 k=abc 时，密文 C=Hfnlpyosnd。

三、QWE键盘码：

随着键盘普及，也出现了相应的键盘码。

这是一个常见的键盘,在左边字母区有三行字母分别为：

QWERTYUIOP

ASDFGHJKL

ZXCVBNM

从第一排第一列开始分别用Q替代A，W替代B……M替代Z以此类推。

如 CODING 加密后即为 EGROFU.

这对于现在来说算是简单的加密方法，但对于键盘不普及的二战时期却是一大难题。

输入格式

输入第一行为一个正整数 $N$ 表示截获的密文共用了 $N$ 重密码加密。

第二行为一个字符串 $S$ 表示加密后的密文。

以下 $3-N+2$ 行,共 $N$ 行每行开头一个正整数K( $1 \le K \le 3$ )表示对应的加密方式。

给出的加密方式按顺序给出，即给出的第I重加密为实际加密过程的第 $I$ 重( $1\le I \le N$ )。

若 $K=1$ 则表示用栅栏密码加密，之后一个正整数 $L$ 表示加密所用栏数。

若 $K=2$ 则表示用维吉尼亚码加密，之后一个字符串 $T$ 表示密钥。

若 $K=3$ 则表示用QWE键盘码加密。

输出格式

共一行。一个字符串，表示破解 $N$ 重加密后的明文。

输入输出样例 #1

输入 #1

text

1
2
3
42
YSLTRIQXSHTQTR
1 2
3

输出 #1

text

1FULLSPEEDAHEAD

说明/提示

$n\le1000$

密码破解者

目录

题意

思路

代码

复杂度

总结