POI 1998 单词等式 Word equations
这是合并等价类问题，由于每个未知量有多位，每位对应0或1，我们先把字母串按照展开拆开。例如样例可以展开成
1,b1,b2,a1,a2,a3,a4,d1,d2,d3,d4, 1 a1,a2,a3,a4,c1,c2,c3,c4,b1,b2,e1,e2
对于上述对应关系，进一步抽象成5个集合，每个元素属于唯一的一个集合，每个集合对应0或1。
{1,a1,a4,c3,e2} {b1,a2,c1,d2} {b2,a3,c2,d3} {d1,c4} {d4,e1}
除了第一个集合一定为1以外，其余四个集合都有两种可能的解，根据乘法原理，解的总数为2^4=16。
对于这道题而言，可能会无解。无解的情况之一是两个串展开后长度不相等，这样就会有一些没有对应关系，所以无解。另一种情况就是两个已知量1和0属于同一个集合，这显然是有悖于事实的，也是无解。
求等价类集合的方法可以用并查集，也可以按照关系构图，求无向图连通分量的个数。两种方法的时间复杂度都可以近似认为是O(N)的。
下面是我的代码，用了并查集。
/*
* Problem: POI1998 row
* Author: Guo Jiabao
* Time: 2008.12.1 18:01:52
* State: Solved
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
using namespace std;
const int MAXL=10001;
const int MAXM=260003;
class tUFS
{
private:
int F[MAXM];
int findroot(int k)
{
int r=k,t;
while (F[r]>0)
r=F[r];
while (F[k]>0)
{
t=F[k];
F[k]=r;
k=t;
}
return r;
}
public:
void clear()
{
int i;
for (i=0;i<MAXM;i++)
{
F[i]=-i;
}
}
void Union(int a,int b)
{
F[findroot(a)]=findroot(b);
}
bool judge(int a,int b)
{
return F[findroot(a)]==F[findroot(b)];
}
int getroot(int k)
{
return -F[findroot(k)];
}
};
template<int LIM,int MAX> class hp
{
public:
//vars
int sect[MAX];
int scnt;
//constructors
hp()
{
scnt=1;
sect[0]=0;
}
//functions
void copy(int A)
{
scnt=0;
while (A)
{
sect[scnt++]=A % LIM;
A /=LIM;
}
}
void print()
{
int i,k;
printf("%d",sect[scnt-1]);
for (i=scnt-2;i>=0;i--)
{
k=LIM/10;
while(sect[i]<k)
{
printf("0");
k/=10;
}
if (sect[i])
printf("%d",sect[i]);
}
}
void multiply(int p)
{
if (p==0)
{
scnt=1;
sect[0]=0;
return;
}
int sc=scnt;
int i,up=0;
for (i=0;i<sc;i++)
{
if (i>=scnt) sect[i]=0;
sect[i]=sect[i] * p + up;
up=sect[i] / LIM;
sect[i]%=LIM;
}
scnt=sc;
if (up) sect[scnt++]=up;
}
};
typedef hp<100000000,1000> hpnum;
int Dcnt,N,M[2],R;
int L[30],Len[2];
char E[2][MAXL];
int Q[2][MAXM];
bool hash[MAXM];
tUFS U;
void init()
{
freopen("row.in","r",stdin);
freopen("row.out","w",stdout);
scanf("%d",&Dcnt);
}
inline int getid(char c)
{
if (c=='1') return 260001;
if (c=='0') return 260002;
return (c-'a')*10000;
}
bool readfile()
{
int i,j,k,d;
scanf("%d",&N);
for (i=1;i<=N;i++)
{
scanf("%d",&L[i]);
}
for (k=0;k<=1;k++)
{
scanf("%d",&Len[k]);
scanf("%s",E[k]);
M[k]=0;
for (i=0;i<Len[k];i++)
{
d=getid(E[k][i]);
if (E[k][i]=='0' || E[k][i]=='1')
{
Q[k][++M[k]]=d;
}
else
{
for (j=1;j<=L[E[k][i]-'a'+1];j++)
{
Q[k][++M[k]]=d+j;
}
}
}
}
return (R=M[0])==M[1];
}
int deal()
{
int i,j,d,cnt=0,l0,l1;
U.clear();
memset(hash,0,sizeof(hash));
for (i=1;i<=R;i++)
{
if (!U.judge(Q[0][i],Q[1][i]))
U.Union(Q[0][i],Q[1][i]);
}
l0=U.getroot(260002);
l1=U.getroot(260001);
if (l0==l1)
return -1;
hash[l0]=hash[l1]=true;
for (i=1;i<=N;i++)
{
for (j=1;j<=L[i];j++)
{
d=(i-1)*10000+j;
d=U.getroot(d);
if (!hash[d])
{
hash[d]=true;
cnt++;
}
}
}
return cnt;
}
void solve()
{
int i,j,A;
hpnum Ans;
for (i=1;i<=Dcnt;i++)
{
if (readfile())
{
Ans.copy(1);
A=deal();
if (A==-1)
printf("0");
else
{
for (j=1;j<=A;j++)
{
Ans.multiply(2);
}
Ans.print();
}
}
else
printf("0");
printf("n");
}
}
int main()
{
init();
solve();
return 0;
}
单词等式
所有非空的01序列被称作一个二进制单词。一组相等的单词是如下形式的等式：x1x2..xl=y1y2..yr ，这里xi 和yj 是二进制字符01或是用小写字母表示的变量。对每一个变量都有一个固定长度的两进制单词来代替这个变量，这个长度称之为这个变量的长度。为了解决单词相等的问题我们需要用某种方法分配给所有变量适当的二进制单词（这个二进制单词的长度必须为这个变量的长度），使得变量被取代后的等式成立。对一个给定的等式计算有几种解答。
例子：
让a,b,c,d,e分别为长度为4，2，4，4，2的5个变量。考虑以下等式：1bad1=acbe。这个等式有16种不同的解答方案。
任务：
写一个程序：
* 从文件中读入等式的数目以及它们的描述。
* 对每个等式找出它们的解答方案数。
* 将结果写入文件。
输入：
在文件ROW.IN的第一行有一个整数x(1<=x<=5)表示等式的数目，随后有x个等式的描述。每个描述包括6行，两个等式的描述之间没有空行。每个等式用以下方式描述：在描述的第一行有一个整数k(0<=k<=26)表示等式中不同的变量数目，我们假设变量是从a起的k个小写字母。第二行有k个由空格隔开的正整数，表示k个变量的长度（第一个数表示a的长度，第二个数表示b的长度）。第三行有一个整数l，表示等式左边的长度（有0 1及变量（单个字母）组成的单词长度）。等式左边将被写在下一行，仅包括01及小写字母而没有空格。以下两行给出了对等式左边的描述，第一行为一个正整数 r，表示等式右边的长度，等式的右边被写在第二行。等式两边所有变量的和相等且不超过10000。
输出：
对每个I (1<=I<=x)，你的程序必须在第I行给出第I个等式的不同解答方案数，并将它写入文件。
输入样例：
1
5
4 2 4 4 2
5
1bad1
4
acbe
输出样例：
16
上次修改时间 2017-02-03