自动搬运

查看原文

来自洛谷，原作者为

	wunaidedanjuan 精神状态良好

搬运于2025-08-24 21:55:44，当前版本为作者最后更新于2023-10-20 12:01:16，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

简化题意

找到一个 ? 使字符串左右元素守恒，且 ? 属于题目背景研究的物质范围内。

解题思路

• 分别统计等号两侧元素出现次数；

• 判断 ? 在等号哪侧；

• 根据两侧元素出现次数差值判断是否有解，若有解则求出 ?。

思路优化

• 考虑一个问题，可不可以直接记录等号两侧元素出现次数的差值呢？

  当然可以，我们只需要用一个数组统计元素出现的次数，若元素出现在等号左侧则加上相应的次数，否则则减去。

  但这样就可能出现下面一个问题：

  观察这一个方程：$A+?=AB$，

  若用 $a[]$ 数组记录元素出现的次数的话，$a[1]=-1$，表示方程左侧元素 $B$ 出现的次数减去方程右侧元素 $B$ 出现的次数的结果等于 $-1$；

  但当 ? 在方程右侧时，如：在 $AB=A+?$ 中，$a[1]=1$。

  该如何解决这个问题呢？

  我们只需要设置一个变量 $c$ 记录 ? 所在位置，当 ? 在等号左侧时，$c$ 值为 $-1$，在右侧时就为 $1$，这样我们查找多余元素即 ? 时，只需要将 $a[]$ 的值乘上 $c$ 即可。

  这样在上述两个方程式中，$a[1]\times c$ 的值就均为 $1$ 了。

  $a[i]\times c$ 的值就代表了 ? 中 $char(i+'A')$ 元素的个数。

• 最后，我们该如何判断无解的情况

  第一种无解的情况就是方程式本身无解。

  例如：$A+?=B$，这种情况下，我们是无法找到一个 ? 使方程中元素守恒的，这时 $a[0]\times c$ 的值为 $- 1$，也就是说，这种情况下 $a[]$ 数组中存在 $a[i]\times c$ 的值小于 $0$，所以我们只需要遍历 $a[]$ 数组就可以判断方程式是否无解了。

  值得一提的是，这里存在一种特殊情况，即：$A+？=A$，此时的方程式也是无解的，但它 $a[0]\times c$ 的值却不小于 $0$，所以要记得加个特判。

  第二种无解的情况就是 ? 所代表的物质超出了钦钦草原世界化学学科的研究范围。

  也就是说，? 中存在元素下标的数字超过了 $9$，我们也可以通过遍历 $a[]$ 数组判断方程式是否无解。

思路总结

• 遍历方程式；

  遍历到 $=$ 前，$a[]$ 数组加上元素出现的次数；遍历到 $=$ 后，$a[]$ 数组减去元素出现的次数。

• 标记 ? 出现的位置；

• 判断是否有解，然后输出；

• 重置标记变量和数组。

代码呈现

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<queue>
#include<string>
#include<bitset>
#include<cctype>
#include<cstdlib>
#include<functional>
#include<istream>
#include<sstream>
#include<streambuf>
#define ll long long 
using namespace std;
const int N=26;
int a[N];
int main()
{
	int n,m,c;
	string s;
	bool b,d,e;
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
	{
		b=false;//重置标记变量和数组 
		d=false;
		e=false;
		memset(a,0,sizeof(a));
		cin>>s;
		s[s.length()]='1';//防止越界 
		for(int j=0;j<s.length();j++)
		{
			if(s[j]=='=')//判断是否到达方程右侧 
				b=true;
			else
			{
				if(b==false)
				{
					if(s[j]=='?')// ？在方程左侧 
						c=-1;
					else if(s[j]>='A'&&s[j]<='Z')
					{
						if(s[j+1]>='0'&&s[j+1]<='9')
							a[(int)(s[j]-'A')]+=(int)(s[j+1]-'0');
						else	
							a[(int)(s[j]-'A')]++;
					}
				}
				else
				{
					if(s[j]=='?')// ？在方程右侧 
						c=1;
					else if(s[j]>='A'&&s[j]<='Z')
					{
						if(s[j+1]>='0'&&s[j+1]<='9')
							a[(int)(s[j]-'A')]-=(int)(s[j+1]-'0');
						else	
							a[(int)(s[j]-'A')]--;
					}
				}
			}
		}
		for(int j=0;j<26;j++)//是否无法配平 
			if(a[j]*c<0||a[j]*c>9)
			{
				printf("No Solution");
				d=true;//标记 
				break;
			}
		if(d==false)
		{
			for(int j=0;j<26;j++)//寻找缺失元素 
			{
				if(a[j]*c==1)
				{
					printf("%c",(char)(j+'A'));
					e=true;
				}
				else if(a[j]*c>1)
				{
					printf("%c%d",(char)(j+'A'),a[j]*c);
					e=true;
				}
			}
			if(e==false)//特判，第一种情况中的特殊情况 
				printf("No Solution");
		}
		printf("\n");
	}
    return 0;
}