#D. 加密通信

    传统题 1000ms 256MiB

加密通信

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

在一次军事演习中,小凯担任通信兵,负责解密传来的信息。他会收到一份 n×nn \times n 的数字表(仅包含 090-91010 种数码),和一份 m×mm \times m 的字母表(仅包含 AZazA-Z、a-z5252 种字符)。 数字表被称为解密卡,字母表被称为加密卡。规定如下名词:

  1. 覆盖区域:将数字表和字母表对齐,使得数字表在上,字母表在下,数字与字母一一对应,如果数字表的 1111 列对应字母表的 xxyy 列,那么数字表的 kk1+k1+k 列对应字母 表的 x+kx+ky+ky+k 列,此时覆盖区域为字母表以 xxyy 列为左上角、x+n1x+n-1y+n1y+n-1 列为右下角的正方形范围。简单来说,根据图片显示,若数字表的左上角盖在了 2222 列的位置,则数字表会覆盖 (2,2)(2,2)(3,3)(3,3) 这片区域。
  2. 有效区域:称某字母和其在字母表的顺序数字为互相对应,字母 AAaa 是第 11 个字母、字母 IIii 是第 99 个字母,那么 AaA、a11 对应,IiI、i99 对应,以此类推。如果覆盖区域的 四个顶点字母恰好和原始数字表的四个顶点数字互相对应,那么这个覆盖区域称之为有效区域。 image
  3. 数字关联00 和任何字母关联,11不能和任何字母关联,292-9 中的质数和大写字母关联,292-9 中的合数和小写字母关联。若关联成功,则提取出来作为密码的一部分,如上图中 22 是质数,需关联大写字母,22 对应的是 BB,关联成功;33 是质数,需关联大写字母,33 对应的 cc关联失败;44 是合数,需关联小写字母,而 44 对应的是 DD,关联失败。因此上述图中,本次覆盖只关联成功一次,提取出一个密码 B\text{B}
  4. 解密数字表:大小为 n×nn \times n,可以由原始数字表顺时针旋转若干次 90°90° 得到 image
  5. 区域解密:有效区域和解密数字表对齐,从左到右从上到下,将和解密数字表中对应位置数字恰好关联的字母提取出来,构成字符串。

一次解密操作包含以下步骤:

  • 首先从左到右从上到下找出所有有效区域,依次进行解密。
  • 对于每个有效区域首先用原始数字表进行 11 次区域解密,然后根据当前有效区域的 顶点大写字母数量 xx,额外进行 xx 次区域解密(如图示中四个顶点有两个大写字母,因此需旋转两次),第 ii 次解密时将原始数字表顺时针旋转 i×90°i \times 90° 后作为解密数字表再进行区域解密。
  • 最后将所有区域解密的字符串按序连接,构成最终的解密字符串。

你需要帮助小凯完成解密工作。

输入描述

输入共 n+m+1n+m+1 行,

11 行两个正整数 nnmm,分别代表数字表和字母表的大小;

22n+1n+1 行分别有连续的 nn 个数码字符,代表数字表的内容;

n+2n+2n+m+1n+m+1 行分别有连续的 mm 个字母字符,代表字母表的内容。

输出描述

输出仅一行一个字符串,代表解密后的答案。如果答案为空串,你需要输出“No solution”(不包含引号)。

输入样例1

2 3
11
13
AAB
ACB
BzB

输出样例1

CAAAC

输入样例2

3 4
101
245
313
DABa
AFab
Fcdc
cdcD

输出样例2

BFaABabFFcAFcd

样例解释

输入样例 11, 仅有 (1,1)(2,2)(1,1) \sim (2,2)这一个有效区域,此区域的四个顶点共有 44 个大写字母需要 额外 进行 44 次区域解密,此区域第 11 次解密为 CC(仅在(2,2)(2,2) 位置有质数 33 与大写字母 CC 关联),第 242-4 次为 AA,第 55 次为 CC,最终答案为 CAAAC\text{CAAAC}

输入样例 22,有(1,2)(3,4)(1,2) \sim (3,4) 以及(2,1)(4,3)(2,1) \sim (4,3) 这两个有效区域,第一个 (1,2)(3,4)(1,2) \sim (3,4) 区域为

FcdFabCdc\begin{array}{c} \text{Fcd}\\ \text{Fab}\\ \text{Cdc}\\ \end{array}

此区域的四个顶点共有 11 个大写字母需要 额外 进行 11 次区域解密。此区域的第一次解密得到的密码为 BFa\text{BFa},旋转一次密码卡,进行第二次解密,得到的密码为 ABab\text{ABab};第二个区域为

AFaFcdcdc\begin{array}{c} \text{AFa}\\ \text{Fcd}\\ \text{cdc}\\ \end{array}

此区域的四个顶点共有 11 个大写字母需要额外进行 11 次区域解密。此区域的第一次解密得到的密码为 FFc\text{FFc},旋转一次密码卡,进行第二次解密,得到的密码为 AFcd\text{AFcd};因此总密码为四块密码从前往后拼在一起:BFaABabFFcAFcd\text{BFaABabFFcAFcd}

数据范围

测试点编号 mm\leq 特殊性质
11 1010 B\text{B}
22 A\text{A}
33
44 5050
55 B\text{B}
66
77
88 300300
99
1010

特殊性质一栏种,两个字母的含义为:

  • AA : 数字表中仅含有 0011
  • BB : 字母表中仅含有小写字母。

对于所有测试点:1nm3001 \leq n \leq m \leq 300

卉图编程奥赛部CSP-J 第二轮模拟赛

未参加
状态
已结束
规则
OI
题目
5
开始于
2024-7-29 14:00
结束于
2024-7-29 17:30
持续时间
3.5 小时
主持人
参赛人数
35