2020 CCPC Wannafly Winter Camp Day1 Div.12——密码学【构造 模拟】

题目传送门

题目描述

考虑一种加密方式，它需要一个任意长度的原文 {m}m 和秘钥 {key}key，其中要求原文和秘钥只包含大写和小写的英文字符。
首先定义字符之间的加密，用字符 $a$ 去加密字符 $b$ 的结果是：

• 首先把 $a$ 和 $b$ 转成数字 $x$ 和 $y$。转换的规则是，小写字母 $a$ 到 $z$ 依次对应 $0$ 到 $25$，大写字母依次对应 $26$ 到 $51$。
• 计算 $x$ 和 $y$ 的和 $z$，对 $52$ 取模，即计算 $(x+y)\mathrm{m}\mathrm{o}\mathrm{d}52$。
• 返回数字 $z$ 对应的字符。

现在来讲如何用秘钥 $key$ 来加密原文 $m$：

• 如果秘钥的 $key$ 的长度小于 $m$，那么不停重复 $key$ 直到长度不小于 $m$ 为止。举例来说，如果原文是 $beijing$，秘钥是 $PKUSAA$，那么秘钥需要被重复称 $PKUSAAPKUSAA$。
• 假设原文的长度是 $n$，那么对于每一个 $[1,n]$ 的数字 $i$，都用 $key$ 的第 $i$ 个字符去加密 $m$ 的第 $i$ 个字符。
• 返回结果。

那么用 $PKUSAA$ 去加密 $beijing$ 的结果就是：$QOcbINV$。
现在火山哥有 $n$ 个字符串，$s_1$ 到 $s_n$，他对这些字符串做了$m$ 次加密操作：第 $i$ 次加密操作用第 $s_{?x_i}$ 去加密 $s_{?y_i}$，并把 $s_{?yi}$ 替换成加密结果。
现在依次给出 $m$ 次加密操作，以及加密操作结束后每一个字符串的模样，你可以还原出这 $n$ 个字符串原来的模样吗？

输入描述:

第一行输入两个整数 $n,m$ $(1\le n,m\le 1000)(1\le n,m\le 1000)$。
接下来 $m$ 行每行输入两个整数 $x_i,y_i$，表示依次加密操作，保证 $x_i$ 不等于 $y_i$ 。
接下来 $n$ 行每行输入一个字符串，表示加密最后的结果。字符串的长度在 $1$ 到 $100$ 之间，只包含大小写英文字符。

输出描述:

输出 $n$ 行，每行一个字符串，表示原本的字符串。

输入

2 1
1 2
PKUSAA
QOcbINV

输出

PKUSAA
beijing

题解

• easy
• 题面中给出了已知原文和秘钥，加密得到密文的方法。其实已知密文和秘钥，就可以轻松的解密出原文：只要用密文对应的数字减去秘钥对应的数字就可以了。
  因此，我们可以从后往前“撤销”所有加密操作带来的影响。假设最后一次加密操作是用 $s_x$ 去加密 $s_y$，那么在结果中，$s_x$ 是没有发生变化的，即秘钥已知；$s_y$，存储的是结果，即密文已知。从而用上面的方法可以直接从两者之中推出 $s_y$，原来的值。
• 所以从后往前考虑每一次加密操作，依次进行撤销，最后得到的就是最开始的 nn 个字符串。

AC-Code

#include <bits/stdc++.h>
using namespace std;int xi[1005], yi[1005];
string str[1005];
int f1(char c) {
     return c > 'Z' ? c - 'a' : c - 'A' + 26; }
char f2(int x) {
     return x >= 26 ? 'A' + x - 26 : 'a' + x; }
void sub(char& s1, char& s2) {
    s2 = f2((f1(s2) - f1(s1) + 52) % 52);
}
void solve(int a, int b) {
    for (int i = 0, j = 0; str[b][j]; ++i, ++j) {
    if (!str[a][i])i = 0;sub(str[a][i], str[b][j]);}
}
int main() {
    int n, m;while (cin >> n >> m) {
    for (int i = 0; i < m; ++i) cin >> xi[i] >> yi[i];for (int i = 1; i <= n; ++i) cin >> str[i];for (int i = m - 1; i >= 0; --i) solve(xi[i], yi[i]);for (int i = 1; i <= n; ++i) cout << str[i] << endl;}return 0;
}