题意:

一个代码等式就是形如x1x2…xi=y1y2…yj,这里xi和yj是二进制的数字(0或1)或者是一个变量(如英语中的小写字母)。每一个变量都是一个有固定长度的二进制代码。例如:
a,b,c,d,e是变且它们的长度分别是4,2,4,4,2。考虑等式:1bad1=acbe,这个等式共有16组解。现要求任给一个等式,计算一共有多少组解。(变量最多26个,长度和不超过10000)

思路:

利用并查集维护每个变量相同的位的集合,再根据已知的数字判断是否无解.
我们可以利用两个指针从左向右同时访问两个字符串.
第一次访问:将两个指针对应的并查集合并.遇到已知数字两个指针同时直接跳过这一位.
第二次访问:考虑已知数字对解的影响.遇到已知数字修改或访问并查集根节点,判断是否有两个不同已知数字在这个并查集中.
然后利用高精度乘法(+快速幂)求出答案.


(本代码已在本地cy下发数据评测下AC)


#include <iostream>
#include <cstring>
#include <cstdio>

#define MX 200020

using namespace std;

typedef struct agDGdw
{
    int x[100000];
    int len;
}BI;

int fa[MX];
int n;
int len[MX];
int sum[MX];
char str[MX];
int l1,l2;
int p1[MX],p2[MX];
int must[MX];
int vis[MX];
int have[MX];
char s1[MX],s2[MX];

void mul(BI *a)
{
    for(int i=1;i<=a->len;i++)a->x[i]*=2;
    for(int i=1;i<=a->len;i++)a->x[i+1]+=a->x[i]/10,a->x[i]%=10;
    if(a->x[a->len+1])a->len++;
}

int findfa(int x)
{
    return x==fa[x]?x:fa[x]=findfa(fa[x]);
}

int comb(int a,int b)
{
    int f1,f2;
    f1=findfa(a);
    f2=findfa(b);
    if(f1==f2)return 0;
    fa[f1]=f2;
    return 1;
}

void input()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%d",&len[i]);
}

void work()
{
    int now1,now2,t1,t2;
    memset(vis,0,sizeof(vis));
    memset(have,0,sizeof(have));
    for(int i=1;i<=n;i++)sum[i]=sum[i-1]+len[i];
    for(int i=1;i<MX;i++)fa[i]=i;
    scanf("%d%s",&l1,s1+1);
    scanf("%d%s",&l2,s2+1);
    for(int i=1;i<=l1;i++)
    {
        if(s1[i]=='0'||s1[i]=='1')p1[i]=p1[i-1]+1;
        else p1[i]=p1[i-1]+len[s1[i]-'a'+1];
    }
    for(int i=1;i<=l2;i++)
    {
        if(s2[i]=='0'||s2[i]=='1')p2[i]=p2[i-1]+1;
        else p2[i]=p2[i-1]+len[s2[i]-'a'+1];
    }
    if(p2[l2]!=p1[l1]){cout<<0<<endl;return;}
    now1=1,now2=1;
    for(int i=1;i<=p2[l2];i++)
    {
        if(i>p1[now1])now1++;
        if(i>p2[now2])now2++;
        if(isdigit(s1[now1])&&isdigit(s2[now2])&&s1[now1]!=s2[now2]){cout<<0<<endl;return;}
        if(isdigit(s1[now1])||isdigit(s2[now2]))continue;
        comb(sum[s1[now1]-'a']+i-p1[now1-1],sum[s2[now2]-'a']+i-p2[now2-1]);
    }

    now1=1,now2=1;
    for(int i=1;i<=p2[l2];i++)
    {
        if(i>p1[now1])now1++;
        if(i>p2[now2])now2++;
        if(isdigit(s1[now1])&&isdigit(s2[now2]))continue;
        if(!isdigit(s1[now1])&&!isdigit(s2[now2]))continue;
        t1=sum[s1[now1]-'a']+i-p1[now1-1];
        t2=sum[s2[now2]-'a']+i-p2[now2-1];
        if(isdigit(s2[now2]))
        {
            if(vis[findfa(t1)])
            {
                if(must[findfa(t1)]!=s2[now2]-'0'){cout<<0<<endl;return;}
            }
            else vis[findfa(t1)]=1,must[findfa(t1)]=s2[now2]-'0';
        }
        if(isdigit(s1[now1]))
        {
            if(vis[findfa(t2)])
            {
                if(must[findfa(t2)]!=s1[now1]-'0'){cout<<0<<endl;return;}
            }
            else vis[findfa(t2)]=1,must[findfa(t2)]=s1[now1]-'0';
        }
    }
    int mtm=0;
    for(int i=1;i<=sum[n];i++)
        if(!have[findfa(i)]&&!vis[findfa(i)])have[fa[i]]=1,mtm++;
    BI tmp;
    tmp.len=1;
    tmp.x[1]=1;
    for(int i=1;i<=mtm;i++)mul(&tmp);
    for(int i=tmp.len;i>=1;i--)cout<<tmp.x[i];cout<<endl;
}

int main()
{
    int t;
    scanf("%d",&t);
    for(int w=1;w<=t;w++)
    {
        input();
        work();
    }
    return 0;
}
分类: 所有

发表评论

电子邮件地址不会被公开。 必填项已用*标注

你是机器人吗? =。= *