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

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

首先把 a 和 b 转成数字 x 和 y。转换的规则是,小写字母 a 到 z 依次对应 0 到 25,大写字母依次对应 26 到 51。

计算 x 和 y 的和 z,对 52 取模,即计算 (x+y) mod 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​y​i​​ ​​ 替换成加密结果。

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

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

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

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

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

输入样例:
2 1
1 2
PKUSAA
QOcbINV

输出样例:
PKUSAA
beijing

题解:简单模拟即可。

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<string>
#include<cmath>
#include<queue>
#include<cstdlib>
#include<map>
#include<set>
#define ll long long
#define llu unsigned ll
#define ld long double
#define pr make_pair
#define pb push_back
#define x first
#define y second
//#define int ll
using namespace std;
const int inf=0x3f3f3f3f;
const ll lnf=0x3f3f3f3f3f3f3f3f;
const int mod=1e9+7;
const int maxn=1100;
char str[maxn][110];
int l[maxn],r[maxn];
int a[maxn],b[maxn],c[maxn];

int get(char ch)
{
    if(ch>='a'&&ch<='z') return ch-'a';
    else return ch-'A'+26;
}

char rget(int a)
{
    if(a<=25) return a+'a';
    else return a-26+'A';
}

void change(char *s1,char *s2)
{
    int len1=strlen(s1);
    int len2=strlen(s2);
    //cout<<len1<<" "<<len2<<endl;
    for(int i=0;i<len2;i++)
        c[i]=get(s2[i]);
    for(int i=0;i<len1;i++)
        b[i]=get(s1[i]);
    for(int i=0;i<len2;i++)
        a[i]=(c[i]-b[i%len1]+52)%52;
    for(int i=0;i<len2;i++)
        s2[i]=rget(a[i]);
}

signed main(void)
{
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)
        scanf("%d%d",&l[i],&r[i]);
    for(int i=1;i<=n;i++)
        scanf("%s",str[i]);
    for(int i=m;i>=1;i--)
        change(str[l[i]],str[r[i]]);
    for(int i=1;i<=n;i++)
        printf("%s\n",str[i]);
    return 0;
}