1st

wunaidedanjuan · 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+?=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;
}