列表

详情

NC14755. 化学狂暴

描述

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

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

钦钦草原的世界里共有26种元素，分别用大写字母A至Z表示。

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

然而，这种描述方法实在是太麻烦了，于是钦钦草原世界中的炼金术士们便尝试简化物质的描述。对于某种物质，我们定义“虚无元素”表示在该物质中下标为0的元素，“单一元素”表示在该物质中下标为1的元素。针对这两个定义，炼金术士们提出了两种化简方式：
1.省略“虚无元素”：将“虚无元素”的字母和下标省略。如上面的物质可以通过该操作化简为：J1Q1Y2。
2.省略“单一元素”的下标：将“单一元素”的下标省略。如上面的物质可以通过该操作化简为：A0B0C0D0E0F0G0H0I0JK0L0M0N0O0P0QR0S0T0U0V0W0X0Y2Z0。
特别地，对于同时省略了“虚无元素”和“单一元素”下标的表示，我们把它叫做该物质的“最简式”。如上面物质的“最简式”即为：JQY2。

由于钦钦草原世界的化学研究仍处于起步阶段，因此对于任意的物质，所有元素下标均为不超过9的非负整数。
化学方程式是描述化学反应的式子。一个化学方程式包含恰好一个等号（=），等号两边是由加号（+）连接的若干物质。形象地说，它的形式是这样的：
物质+物质+…+物质=物质+物质+…+物质
除了需要满足上述格式外，元素守恒也是不可忽视的。这表示等号两边所有元素在各物质中的出现次数总和必须相等。比如，这就是一个合法的（格式正确、元素守恒的）化学方程式：
 JQY2+J2=J3QY2
需要特别注意的是，在化学方程式的书写中，未被化至“最简式”的元素也是可以被接受的。例如，下面的化学方程式也是合法的：
J1Q1Y2+J2=J3Q1Y2
而下面这个化学方程式就不是合法的了，因为它并没有满足元素守恒。
JQY2+J2=JQY
钦钦草原化学学科的基本知识就介绍到这。祝各位选手武运昌隆！
所谓化学方程式，即是用加号（+）和等号（=）连接一些化学物质的式子。保证一个化学方程式中含有恰好一个等号（=）。化学物质由一些元素（用大写字母A至Z表示）加上下标（保证下标为不超过9的非负整数）连接而成的。例如：JQY2、A0J1QY2等。书写时需要保证字典序越小的字母排在越前面。

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

既然称之为“方程式”，元素守恒就是必须的了。对于一个化学方程式，元素守恒指的是指等号两边所有元素的下标之和相等。比如，这个化学方程式就是元素守恒的：
JQY2+J2=J3QY2
而这个化学方程式就是不合法的，因为它不满足元素守恒：
JQY2+J2=JQY
作为一名资深炼金术士，Yazid自然是整日沉迷在化学狂暴中。某一天，Yazid写下了n个化学方程式，并把它们放在一边，为后续的研究做着准备。
然而，见习炼金术士YJQQQAQ不慎打翻了一瓶绿色的试剂，导致Yazid写下的所有化学方程式中，都有恰好1个物质被绿色液体弄得模糊不清了。

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

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

输入描述

第一行2个整数n,m，分别表示化学方程式的数目和Yazid的书写习惯。其中，书写习惯m是0到3之间的整数，对于不同的m，Yazid书写物质的方式不同（这一信息可能对你解决部分测试点有帮助）：
如果m=0，则Yazid在书写方程式时一定会将所有物质化为“最简式”；
如果m=1，则Yazid在书写方程式时一定会将所有物质的“虚无元素”省略，且不会存在“单一元素”的下标被省略；
如果m=2，则Yazid在书写方程式时一定会将所有物质“单一元素”的下标省略，且不会存在“虚无元素”被省略；
如果m=3，则Yazid在书写方程式时一定不会省略“单一元素”的下标，也一定不会省略“虚无元素”。
接下来n行，每行一个字符串，描述一个被污染的化学方程式。其中，被污染的物质用?表示，保证对于每一个方程式都会存在恰好1个?。
数据保证化学方程式严格按照题目背景和题目描述中的格式，且不存在多余的空格或其他字符。

输出描述

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

示例1

输入: 

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

输出: 

A
AB
CO2

说明:

对于所有的测试点，保证n≤100，保证每个方程式中等式两边的加号+都不超过5个，这也意味着每行字符串（每个化学方程式）的长度不超过635。

原站题解

上次编辑到这里，代码来自缓存 点击恢复默认模板

C++14(g++5.4) 解法, 执行用时: 5ms, 内存消耗: 520K, 提交时间: 2019-05-18 16:57:16 

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
int n, m, nums[26];
char temp[700];
void doit01(){
    memset(nums, 0, sizeof(nums));
    memset(temp, 0, sizeof(temp));
    scanf("%s", temp);
    char now;
    int flag = -1, f2;
    for(int i = 0; i < strlen(temp); i++){
        if(temp[i] >= 'A' && temp[i] <= 'Z'){
            now = temp[i];
            if(temp[i+1] >= '0' && temp[i+1] <= '9') nums[(int)(now-'A')] += flag * (int)(temp[i+1]-'0');
            else nums[(int)(now-'A')] += 1 * flag;
        }
        if(temp[i] == '=') flag *= -1;
        if(temp[i] == '?'){
            f2 = flag*-1;
        }
    }
    int u = 0;
    for(int i = 0; i < 26; i++){
        if(nums[i] != 0) u = 1;
        if(nums[i]*f2 < 0 || nums[i]*f2 > 9 || (i == 25 && u == 0)){
            cout << "No Solution" << endl;
            return ;
        }
    }
    for(int i = 0; i < 26; i++){
        if(nums[i] == 0) continue;
        printf("%c", (char)('A'+i));
        if(nums[i]*f2 == 1) continue;
        printf("%d", nums[i]*f2);
    }
    printf("\n");
}
int main(){
    scanf("%d %d", &n, &m);
    for(int i = 1; i <= n; i++){
        doit01();
    }
    return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 7ms, 内存消耗: 608K, 提交时间: 2020-03-12 13:27:38 

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
int n,m,nums[26];
char temp[700];
void doit01()
{
	memset(nums,0,sizeof(nums));
	memset(temp,0,sizeof(temp));
	cin>>temp;
	char now;
	int flag=-1,f2;
	for(int i=0;i<strlen(temp);i++)
	{
		if(temp[i]>='A'&&temp[i]<='Z')
		{
			now=temp[i];
			if(temp[i+1]>='0'&&temp[i+1]<='9')
			{
				nums[(int)(now-'A')]+=flag*(int)(temp[i+1]-'0');
				
			}
			else
			{
				nums[(int)(now-'A')]+=1*flag;
			}
		}
		if(temp[i]=='=')
		{
			flag*=-1;
		}
		if(temp[i]=='?')
		{
			f2=flag*-1;
		}
	}
	int u=0;
	for(int i=0;i<26;i++)
	{
		if(nums[i]!=0)
		{
			u=1;
		}
		if(nums[i]*f2<0||nums[i]*f2>9||(i==25&&u==0))
		{
			cout<<"No Solution"<<endl;
			return;
		}
	}
	for(int i=0;i<26;i++)
	{
		if(nums[i]==0)
		{
			continue;
		}
		cout<<(char)('A'+i);
		if(nums[i]*f2==1)
		{
			continue;
		}
		cout<<nums[i]*f2;
	}
	printf("\n");
}
int main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		doit01();
	 } 
	 return 0;
}

上一题

© 2024 nowcoder.com