题解：P2456 [SDOI2006] 二进制方程

SnowyIris · 2025-04-18 17:09:47 · 题解

一个奇怪的隧道

感觉这题像并查集模板

大致思路：先将左右两侧的字符串对齐，每一位用并查集合并，最后寻找有 ans 位的数不受其他数影响，答案即为 2^{ans}。

对齐

首先将题目第二行所给长度记作 var_i，每个变量拉伸为 var_i 长度。

eg. 以样例一为例，可拉伸为如下形式

合并

由题意我们可以知道，等号两边对印位置的数字相等，因此我们可以用并查集 f_i 将它们关联起来。

eg. 同样以样例一为例， f_i 对印关系如下。

然后，我们按位让等号两边对应位相等（合并并查集，最好将根节点较大的合并到较小的，这样比较方便 [doge]），可得到如下的 f_i 。

答案

当我们把等号两侧的信息合并为一个并查集 f_i 后，显然只有 f_i=i 的位才不会受到其他位的影响，并且与其他有相同性质的位相互独立。 f_i 中除 f_0 和 f_1 以外，共 ans 位符合 f_i=i 的性质。

通过乘法原理，答案即为 2^{ans}。

Code

#include<iostream>
#include<cstring>
#include<cmath>
using namespace std;
#define f(n) for(int i=1;i<=n;i++)
int var[27],n,f[270010],ans;
string l,r;
string cl(string x)//拉伸等号两侧 
{
    string ls;
    ls.clear();
    f(x.length())
        if(x[i-1]=='1'||x[i-1]=='0')ls+=x[i-1];
        else for(int j=1;j<=var[x[i-1]-'a'];j++)ls+=x[i-1];
    return ls;
}
int fd(int now)//合并并查集 
{
    if(f[now]==now)return now;
    return f[now]=fd(f[now]);
}
void d(int now,int nw)//将每个var转为记录对应变量在f中第一位的位置 
{
    if(now==n+1)
    {
        n=nw-1;//end
        return;
    }
    d(now+1,var[now]+nw);
    var[now]=nw;
}
int v(char c)//统一处理字符到f的转换 
{
    if(c=='1'||c=='0')return c-'0';
    return var[c-'a'];
}
int high[1000001]={0,1},hl=1;//高精度 
int main()
{
    f(270009)f[i]=i;
    ios::sync_with_stdio(0);
    cin>>n;
    f(n)cin>>var[i-1];
    cin>>l>>r;
    l=cl(l);
    r=cl(r);
    d(0,2);
    //下方为 
    int ls=0,rs=0,lf,rf;
    //ls记录当前位是对应变量中的第几位，rs同理但是记录等号右侧 
    f(l.length())
    {
        if(i>1)
        {
            if(l[i-1]==l[i-2])ls++;
            else ls=0;
            if(r[i-1]==r[i-2])rs++;
            else rs=0;
        }
        lf=fd(v(l[i-1])+ls);
        rf=fd(v(r[i-1])+rs);
        //lf，rf为两方所在并查集根节点 
        if(lf+rf==1)//以防万一存在无解情况 
        {
            cout<<0;
            return 0;
        }
        if(lf<rf)f[rf]=f[lf];
        else f[lf]=f[rf];
    }
    //计算独立位的数量 
    f(n-1)if(f[i+1]==i+1)ans++;
    //高精度 
    int jc;
    f(ans)
    {
        jc=0;
        for(int j=1;j<=hl;j++)
        {
            high[j]=high[j]*2+jc;
            jc=high[j]/10;
            high[j]%=10;
        }
        if(jc!=0)high[++hl]=jc;
    }
    f(hl)cout<<high[hl-i+1];
    return 0;
}