题解 P2456 【[SDOI2006]二进制方程】

· · 题解

安利蒟蒻的博客园：（https://www.cnblogs.com/lbssxz/）

正解开始：

首先读懂题意我们知道，每一个字母都代表一个式子，且把每一个字母替换成数字后可以使得左右两个式子相等。

本人思路来源：先进行 过样例式的枚举：

考虑这种情况：假如左边式子第1位是a，右边式子第一位是1，一个数字，一个字母，因为题意要满足对应位相等，所以我们可以确定字母a的第一位为1。但是，因为整个字符串中可能有多个a，那么我们找到字符串中的其他的a，把它们第一位对应的位数赋值为1.

然而a的第一位的对应位确定，那么等号另一边的对应位也能确定了，而它又是一个字母，于是我们把这个字母的对应位也找出来进行赋值。。。。。。这么下去，解法逐渐明朗：并查集。

具体来说，我们可以按照这种方法，把所有的能遍历到的位置按照并查集处理，并看做一种情况。最后，看还剩几种情况，我们把答案高精度乘为2的几次方就OK了（因为每一位有0，1两种方法）

qwq。

code:

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int maxn=10003;

int n,m,k,sum;
int num[maxn],fa[maxn],x[maxn],y[maxn];

inline int find(int x)
{
    if(x==fa[x])return x;
    fa[x]=find(fa[x]);
    return fa[x];
}

int main() {
    num[1]=2; 
    scanf("%d",&k);
    for(int i=2,x;i<=k+1;++i)
    {
        scanf("%d",&x);
        num[i]=num[i-1]+x;
        sum+=x;//记录总不同的个数 
    }
    char zfc[maxn];
    scanf("%s",zfc);
    for(int i=0;zfc[i];++i)
    {
        if(zfc[i]>='a'&&zfc[i]<='z')
        {
            int c=zfc[i]-'a'+1;//获取他是num数组第几个 
            for(int j=num[c];j<num[c+1];++j)x[++n]=j;//按位置赋值 
        }
        else x[++n]=zfc[i]-'0';//数字的话 
    }
    scanf("%s",zfc);
    for(int i=0;zfc[i];++i)
    {
        if(zfc[i]>='a'&&zfc[i]<='z')
        {
            int c=zfc[i]-'a'+1;
            for(int j=num[c];j<num[c+1];++j)y[++m]=j;//字母 
        } else y[++m]=zfc[i]-'0';//数字 
    }
    if(n!=m)//连左右长度都不相等 
    {
        printf("0");return 0;//直接输出零 
    }
    for(int i=1;i<maxn;++i)fa[i]=i;//初始化并查集找父亲 
    for(int i=1;i<=n;++i)
    {
        int dx=find(x[i]),dy=find(y[i]);
        if(dx+dy==1)
        {
            printf("0");
            return 0;
        }
        if(dx!=dy)
        {
            fa[max(dx,dy)]=min(dx,dy);
            sum--;
        }
    }
    int big[maxn]={1},top=1;
    for(int i=sum;i>=1;i--)
    {
        for(int i=0;i<top;++i)big[i]<<=1;
        for(int i=0;i<top;++i)if(big[i]>=10) {
            big[i+1]+=big[i]/10,big[i]%=10;
        }
        for(;big[top];++top) {
            big[top+1]+=big[top]/10,big[top]%=10;
        }
    }
    for(int i=top-1;i>=0;--i) printf("%d",big[i]);
    return 0;
}

完结。