[並查集]HAOI 破譯密文 encrypt 解題報告

【題目描述】  查看題目
原文鏈接：http://yeefan.tk/blog/haoi-encrypt/
資訊的明文是由0利1組成的非空序列。但在網絡通信中，為了資訊的安全性，常對明文進行加密，用密文進行傳輸。密文是由0、1和若干個密碼字母組成，每個密碼字母代表不同的01串，例如，密文二011a0bf00a01。密碼破譯的關鍵是確定每個密碼的含義。
經過長期統計分析，現在知道了每個密碼的固定長度，如今，我方又截獲了敵方的兩段密文S1和S2，並且知道S1二S2，即兩段密文代表相同的明文。你的任務是幫助情報人員對給定的兩段密文進行分析，看一看有多少種可能的明文。
【輸入文件】
第1行： S1 (第1段密文)
第2行： S2 (第2段密文)
第3行： N (密碼總數， N<=26)
第4—N+3行： 字母i 長度i (密碼用小寫英文字母表示， 密碼長度<=100)

【輸出文件】
M（表示有M種可能的明文）

【輸入輸出樣例】
encrypt.in
100ad1
cc1
4
a 2
d 3
c 4
b 50
encrypt.out
2
【約束條件】
明文的長度<=10000

【分析】
既然每個密文代表一段明文,那我們可以把密文展開
如樣例的:
100ad1
cc1
4
a 2
d 3
c 4
b 50
我們就可以展開成
1 0 0 a1 a2 d1 d2 d3 1
c1 c2 c3 c4 c1 c2 c3 c4 1
那麼問題就成了在這麼一串數中找出有多少個數不定集合.
即c1代表1 c2代表0 c3代表0
但是 c4和a1共同代表什麼呢,這是問題的關鍵,這就用到了並查集:
首先 1 0 a1 a2…d2 d3都是獨立的集合
從i=1開始向右掃描
先把1所在的集合和c1所在的集合歸成一類,
0所在的集合和c2所在的集合歸成一類
….
最後一定是
代表0的字母有一個集合
代表1的字母有一個集合
不能確定代表什麼的有x個集合
因為每個集合代表的數字要麼是1要麼是0有兩種情況
所以兩個集合有4種情況
三個集合有8種情況
x個集合有2^x種情況
所以我們只需要用並查集算出有幾個非0或1的集合,再累乘後輸出即可
注意:有一個密文既對應0也對應1,這種情況構不成任何正確的明文,所以應當輸出0。

【我的代碼】

#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <cstring>
using namespace std;
int num[30];
 
const char base='a'-1;
const int MAXN=3000;
int Letter[30];//每個密碼的密碼長度
int Num[30][102];
char S1[105];
char S2[105];
int N;//密碼總數
int T=0;//不定集合的數量
int Sum=0;//最終結果
int M=0;
int DealA[MAXN]={0};
int DealB[MAXN]={0};
int Num0;
int Num1;
int Len=0;
 
class Node
{
public:
 int parent;
 int count;
}UFS[MAXN];
 
void UFS_Init(int i)
{
 UFS[i].count=1;
 UFS[i].parent=i;
}
 
int UFS_Find(int x)
{
 int i=x;
 while(i!=UFS[i].parent)
  i=UFS[i].parent;
 
 int j=x;
 while(j!=i)
 {
  int tmp=UFS[j].parent;
  UFS[j].parent=i;
  j=tmp;
 }
 return i;
}
 
void UFS_Merge(int x,int y)
{
 x=UFS_Find(x);
 y=UFS_Find(y);
 if(x==y)
  return;
 
 if(UFS[x].count>UFS[y].count)
 {
  UFS[y].parent=x;
  UFS[x].count+=UFS[y].count;
 }
 else
 {
  UFS[x].parent=y;
  UFS[y].count+=UFS[x].count;
 }
}
 
void init()
{
 scanf("%s\n%s\n",&S1,&S2);
 scanf("%d\n",&N);
 memset(Letter,0,sizeof(Letter));
 char cTmp;
 int iTmp;
 for (int i=1;i<=N;i++)
 {
  scanf("%c %d\n",&cTmp,&iTmp);
  Letter[cTmp-base]=iTmp;
 } 
 
 for(int i=1;i<=26;i++)
 {
  for (int j=1;j<=Letter[i];j++)
  {
   M++;
   Num[i][j]=M;
   UFS_Init(M);
  }
 }
 
 M++;
 Num0=M;
 UFS_Init(M);
 
 M++;
 Num1=M;
 UFS_Init(M);
 
 int top=0;
 for (unsigned int i=0;i<strlen(S1);i++)
 {
  if(isalpha(S1[i]))
  {
   for (int j=1;j<=Letter[ S1[i]-base ]; j++)
   {
    top++;
    DealA[top]=Num[S1[i]-base][j];
   }
  }
  else
  {
   if(S1[i]=='0')
   {
    top++;
    DealA[top]=Num0;
   }
   else
   {
    top++;
    DealA[top]=Num1;
   }
  }
 }
 
 Len=top;
 top=0;
 for (unsigned int i=0;i<strlen(S2);i++)
 {
  if(isalpha(S2[i]))
  {
   for (int j=1;j<=Letter[ S2[i]-base ]; j++)
   {
    top++;
    DealB[top]=Num[S2[i]-base][j];
   }
  }
  else
  {
   if(S2[i]=='0')
   {
    top++;
    DealB[top]=Num0;
   }
   else
   {
    top++;
    DealB[top]=Num1;
   }
  }
 } 
}
 
int work()
{
 for(int i=1;i<=Len;i++)
 {
  UFS_Merge(DealA[i],DealB[i]);
 }
 
 if(UFS_Find(Num0)==UFS_Find(Num1))
 {
  return 0;
 }
 
 bool Used[MAXN];
 memset(Used,0,sizeof(Used));
 
 int Find_Num0=UFS_Find(Num0);
 int Find_Num1=UFS_Find(Num1);
 for(int i=1;i<=Len;i++)
 { 
  int tmp=UFS_Find(DealA[i]);
  if(tmp==Find_Num0 || tmp==Find_Num1 || Used[tmp])
   continue;
 
  T++;
  Used[tmp]=true;
 }
 
 for(int i=1;i<=Len;i++)
 {
  int tmp=UFS_Find(DealB[i]);
  if(tmp==Find_Num0 || tmp==Find_Num1 || Used[tmp])
   continue;
 
  T++;
  Used[tmp]=true;
 }
 
 Sum=1;
 for (int i=1;i<=T;i++)
  Sum*=2;
 return Sum;
}
 
int main()
{
 freopen("encrypt.in","r",stdin);
 freopen("encrypt.out","w",stdout);
 init();
 printf("%d\n",work());
 return 0;
}