#6255. 「CodePlus 2017 12 月赛」化学狂暴

内存限制:512 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: Snakes

题目描述

在那遥远的钦钦草原,住着 Yazid 和 YJQQQAQ,他们都是炼金术士。

一般而言,题目背景总是没有用的,但这道题是个例外。在这里,我们将严谨地介绍钦钦草原世界化学学科的一些基本知识。如果你对这些内容感到枯燥乏味,你也可以跳过这个部分,直接阅读「题目描述」中的简述并结合「样例」来帮助你更快地理解题目。

钦钦草原的世界里共有 2626元素,分别用大写字母 AZ 表示。

钦钦草原世界中的物质由元素构成,对于任意的物质,每种元素的出现次数都是非负整数,且至少有 11 种物质的出现次数为正整数,我们把每种元素在物质中的出现次数称作该元素在该物质中的下标。我们可以按 AZ 的顺序写下每种元素及其下标来描述一个物质。这是一个例子:A0B0C0D0E0F0G0H0I0J1K0L0M0N0O0P0Q1R0S0T0U0V0W0X0Y2Z0。这个例子描述了一种 JQ 各出现 11 次,Y 出现 22 次的物质。

然而,这种描述方法实在是太麻烦了,于是钦钦草原世界中的炼金术士们便尝试简化物质的描述。对于某种物质,我们定义“虚无元素”表示在该物质中下标为 00 的元素,“单一元素”表示在该物质中下标为 11 的元素。针对这两个定义,炼金术士们提出了两种化简方式:

  • 省略“虚无元素”:将“虚无元素”的字母和下标省略。如上面的物质可以通过该操作化简为:J1Q1Y2
  • 省略“单一元素”的下标:将“单一元素”的下标省略。如上面的物质可以通过该操作化简为:A0B0C0D0E0F0G0H0I0JK0L0M0N0O0P0QR0S0T0U0V0W0X0Y2Z0

特别地,对于同时省略了“虚无元素”和“单一元素”下标的表示,我们把它叫做该物质的“最简式”。如上面物质的“最简式”即为:JQY2

由于钦钦草原世界的化学研究仍处于起步阶段,因此对于任意的物质,所有元素下标均为不超过 99 的非负整数。

化学方程式是描述化学反应的式子。一个化学方程式包含恰好一个等号(=),等号两边是由加号(+)连接的若干物质。形象地说,它的形式是这样的:

物质+物质+…+物质=物质+物质+…+物质

除了需要满足上述格式外,元素守恒也是不可忽视的。这表示等号两边所有元素在各物质中的出现次数总和必须相等。比如,这就是一个合法的(格式正确、元素守恒的)化学方程式:

JQY2+J2=J3QY2

需要特别注意的是,在化学方程式的书写中,未被化至“最简式”的元素也是可以被接受的。例如,下面的化学方程式也是合法的:

J1Q1Y2+J2=J3Q1Y2

而下面这个化学方程式就不是合法的了,因为它并没有满足元素守恒。

JQY2+J2=JQY

钦钦草原化学学科的基本知识就介绍到这。祝各位选手武运昌隆!


所谓化学方程式,即是用加号(+)和等号(=)连接一些化学物质的式子。保证一个化学方程式中含有恰好一个等号(=)。化学物质由一些元素(用大写字母 AZ 表示)加上下标(保证下标为不超过99的非负整数)连接而成的。例如:JQY2A0J1QY2 等。书写时需要保证字典序越小的字母排在越前面。

需要注意的是,像 A0J1QY2 这样的物质书写同样是合法的,虽然事实上它和 JQY2 是等价的。我们把下标为 11 的元素称为“单一元素”,把下标为 00 的元素称为“虚无元素”。在书写一种物质时,我们既可以省去“单一元素”的下标,又可以直接省去“虚无元素”。特别地,我们把用这两种规则省略至最简的书写称为该物质的“最简式”。例如,JQY2 就是 A0J1Q1Y2 的最简式。

既然称之为“方程式”,元素守恒就是必须的了。对于一个化学方程式,元素守恒指的是指等号两边所有元素的下标之和相等。比如,这个化学方程式就是元素守恒的:

JQY2+J2=J3QY2

而这个化学方程式就是不合法的,因为它不满足元素守恒:

JQY2+J2=JQY

作为一名资深炼金术士,Yazid 自然是整日沉迷在化学狂暴中。某一天,Yazid 写下了 nn 个化学方程式,并把它们放在一边,为后续的研究做着准备。

然而,见习炼金术士 YJQQQAQ 不慎打翻了一瓶绿色的试剂,导致 Yazid 写下的所有化学方程式中,都有恰好 11 个物质被绿色液体弄得模糊不清了。

暴怒的 Yazid 狠狠地把 YJQQQAQ 批判了一番,并要求他将所有模糊不清的物质重新写出来。除此之外,作为惩罚,无论原来 Yazid 如何书写这些物质,YJQQQAQ 都必须将它们以“最简式”的形式写出

如果不能完成这些任务,Yazid 就会把他从钦钦草原放逐。面对这么多的化学方程式,弱小、无助的 YJQQQAQ 手足无措,于是他找到了钦钦草原最擅长编程的你,请你帮他完成任务。

输入格式

从标准输入读入数据。

第一行 22 个整数 n,mn,m,分别表示化学方程式的数目和 Yazid 的书写习惯。其中,书写习惯 mm0033 之间的整数,对于不同的 mm,Yazid 书写物质的方式不同(这一信息可能对你解决部分测试点有帮助):

  • 如果 m=0m=0,则 Yazid 在书写方程式时一定将所有物质化为“最简式”;
  • 如果 m=1m=1,则 Yazid 在书写方程式时一定将所有物质的“虚无元素”省略,且不会存在“单一元素”的下标被省略;
  • 如果 m=2m=2,则 Yazid 在书写方程式时一定将所有物质“单一元素”的下标省略,且不会存在“虚无元素”被省略;
  • 如果 m=3m=3,则 Yazid 在书写方程式时一定不会省略“单一元素”的下标,也一定不会省略“虚无元素”。

接下来 nn 行,每行一个字符串,描述一个被污染的化学方程式。其中,被污染的物质用 ? 表示,保证对于每一个方程式都会存在恰好 11?

数据保证化学方程式严格按照「题目背景」和「题目描述」中的格式,且不存在多余的空格或其他字符。

输出格式

输出到标准输出。

输出 nn 行,每行一个字符串,表示化为“最简式”的 ? 所表示的物质。特别地,对于无解的情况(即 ? 表示的物质超出钦钦草原世界化学学科的研究范围),请输出“No Solution”(不含引号)。

样例

样例输入 1

3 0
A=?
?=A+B
C+O2=?

样例输出 1

A
AB
CO2

样例输入 2

3 1
A1=?
A1+?=B1
C1+O2=?

样例输出 2

A
No Solution
CO2

样例输入 3

1 2
A0B0C0D0E0F0G0H0I0JK0L0M0N0O0P0QR0S0T0U0V0W0X0Y2Z0=?

样例输出 3

JQY2

样例输入 4

2 3
?=A0B0C0D0E0F0G0H0I0J1K0L0M0N0O0P0Q1R0S0T0U0V0W0X0Y2Z0
A0B0C0D0E0F0G0H0I0J1K0L0M0N0O0P0Q1R0S0T0U0V0W0X0Y2Z0+A0B0C0D0E0F0G0H0I0J1K0L0M0N0O0P0Q1R0S0T0U0V0W0X0Y2Z0=?

样例输出 4

JQY2
J2Q2Y4

数据范围与提示

测试点编号mm ? 在方程式的最左端等号左边不含 +等号右边不含 +
100 YesYesYes
211
322
433
500 YesYes
611
722
833
900 Yes Yes
1011
1122
1233
1300 Yes
1411
1522
1633
1700
1811
1922
2033

如表格中“? 在方程式的最左端”为“Yes”,则表示该测试点保证每个字符串的第一个字符均为 ?;否则无特殊保证。

如表格中“等号左边含 +”为“Yes”,则表示该测试点保证等号左边没有加号(+),即等号左边只有一种物质;否则无特殊保证。

如表格中“等号右边含 +”为“Yes”,则表示该测试点保证等号右边没有加号(+),即等号右边只有一种物质;否则无特殊保证。

对于所有的测试点,保证 n100n\leq 100,保证每个方程式中等式两边的加号 + 都不超过 55 个,这也意味着每行字符串(每个化学方程式)的长度不超过 635635


来自 CodePlus 2017 12 月赛,清华大学计算机科学与技术系学生算法与竞赛协会 荣誉出品。
Credit:idea/王聿中 命题/王聿中 验题/陈宇
Git Repo:https://git.thusaac.org/publish/CodePlus201712
感谢腾讯公司对此次比赛的支持。