0%

Camp Day1

发表于 阅读次数：

Camp第一天比赛部分题解。

B.密码学

考虑一种加密方式，它需要一个任意长度的原文 m 和秘钥 key，其中要求原文和秘钥只包含大写和小写的英文字符。

首先定义字符之间的加密，用字符 a 去加密字符 b 的结果是：

  1. 首先把 a 和 b 转成数字 x 和 y。转换的规则是，小写字母 a 到 z 依次对应 0 到 25，大写字母依次对应 26 到 51。
  2. 计算 x 和 y 的和 z，对 52 取模，即计算 (x+y) mod 52。
  3. 返回数字 z 对应的字符。

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

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

那么用 PKUSAA 去加密 beijing 的结果就是：QOcbINV。

现在火山哥有 n 个字符串，s1 到 s**n，他对这些字符串做了 m 次加密操作：第 i 次加密操作用第 sxi 去加密 syi，并把 syi 替换成加密结果。

现在依次给出 m 次加密操作，以及加密操作结束后每一个字符串的模样，你可以还原出这 n 个字符串原来的模样吗？

输入格式：

第一行输入两个整数 n,m(1≤n,m≤1000)。

接下来 m 行每行输入两个整数 x**i,y**i，表示依次加密操作，保证 x**i 不等于 y**i。

接下来 n 行每行输入一个字符串，表示加密最后的结果。字符串的长度在 1 到 100 之间，只包含大小写英文字符。

输出格式

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

输入样例：

1
2
3
4
2 1
1 2
PKUSAA
QOcbINV

输出样例：

1
2
PKUSAA
beijing

题意：给你n个加密后的字符串，给出加密顺序， 求原本的n个字符串。

题解：反向解密，从最后一次加密操作开始解密，最后的字符串就是原本字符串。加密与解密一一对应，不存在冲突。

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
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e4 + 5;
char s[maxn][110];
int getnum(char c){
    if(c >= 'a') return c - 'a';
    return c - 'A' + 26;
}
void solve(int x, int y){
    int h1 = strlen(s[x]), h2 = strlen(s[y]);
    for(int i=0,j=0;j < h2; j++){
        int a = getnum(s[x][i]), b=getnum(s[y][j]);
        b = (b+52-a)%52;
        if(b>25) s[y][j] = 'A'+b;
        else s[y][j] = 'a' + b;
        i = (i+1) % h1;
    }
}
int x[maxn], y[maxn];

int main(){
    int n, m;
    scanf("%d %d", &n, &m);
    for(int i=1;i<=m;i++) scanf("%d %d", &x[i], &y[i]);
    for(int i=1;i<=n;i++) scanf("%s", s[i]);
    for(int i=m;i;i--){
        solve(x[i], y[i]);
    }
    for(int i=1;i<=n;i++) puts(s[i]);
}