POI 1998 單詞等式 Word equations
本文正體字版由OpenCC轉換
這是合併等價類問題，由於每個未知量有多位，每位對應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