P2106 機(jī)密諜報（電腦菜鳥體驗(yàn)做高手心理）
P2106 機(jī)密諜報
問題描述HY 非常喜歡和 GJQ 閑聊，而其他人等都還奮斗在 OI 的道路上，為了不打擾同學(xué)，他們交流統(tǒng)一用密文，交流信息的明文是由0和1組成的非空序列，而密文是由0、1和若干個密碼字母組成，每個 密碼字母代表不同的01串，
例如，密文 011a0bf00a01。密碼破譯的關(guān)鍵是確定每個密碼的含義。
經(jīng)過長期統(tǒng)計分析，現(xiàn)在知道了每個密碼的固定長度，如今，蛋疼的同學(xué)們又截獲了它們倆的兩段 密文S1 和S2 ，并且知道S1 =S2 ，即兩段密文代表相同的明文。你的任務(wù)是幫助同學(xué)們對給定的兩段密文進(jìn)行分析，看一看有多少種可能的明文。
輸入格式輸出格式
M（表示有 M種可能的明文）
樣例輸入100ad1
cc1
4
a 2
d 3
c 4
b 50
樣例輸出2
提示明文的長度 ≤ 10000，保證不用高精度
此題其實(shí)很水，用并查集將相同的位置合并起來，然后再把值為0的位置合并到一個集合里，值為1的位置合并到一個集合里，然后既不在0集合里也不在1集合里的集合數(shù)就是不能確定的位置數(shù)，答案就是2 n 但是注意判無解，如果最后0集合和1集合在一個集合里，即表示某位置既是0又是1，則無解。
代碼：
#include《stdio.h》
#include《iostream》
#include《algorithm》
#include《cstring》
#include《vector》
#define N 55555
#define ll unsigned long long
using namespace std;
const ll T=40000;
string s1，s2;
vector《ll》P［233］;
char A［233］;
ll n，L［233］，sum1［N］，sum2［N］，F(xiàn)［N］;
bool mark［N］;
ll GF（ll x）
{
if（F［x］！=x）F［x］=GF（F［x］）;
return F［x］;
}
void Merge（ll x，ll y）
{
ll fx=GF（x），fy=GF（y）;
if（fx！=fy）F［fx］=fy;
}
ll QM（ll a，ll b）
{
ll ans=1;
while（b）
{
if（b&1）ans=ans*a;
b》》=1;a=a*a;
}
return ans;
}
int main（）
{
ll i，j，k，ans;ans=0;
cin》》s1》》s2;
s1=“ ”+s1;s2=“ ”+s2;
scanf（“%lld”，&n）;
for（i=1;i《=n;i++）scanf（“ %c %lld”，&A［i］，&k），L［A［i］］=k;
for（i=1;i《=T;i++）F［i］=i;
for（i=1;i《s1.length（）;i++）
if（s1［i］==‘0’）sum1［i］=sum1［i-1］+1，Merge（sum1［i］，T）;
else if（s1［i］==‘1’）sum1［i］=sum1［i-1］+1，Merge（sum1［i］，T+1）;
else sum1［i］=sum1［i-1］+L［s1［i］］，P［s1［i］］.push_back（sum1［i-1］）;
for（i=1;i《s2.length（）;i++）
if（s2［i］==‘0’）sum2［i］=sum2［i-1］+1，Merge（sum2［i］，T）;
else if（s2［i］==‘1’）sum2［i］=sum2［i-1］+1，Merge（sum2［i］，T+1）;
else sum2［i］=sum2［i-1］+L［s2［i］］，P［s2［i］］.push_back（sum2［i-1］）;
for（i=1;i《=n;i++）
for（j=1;j《=L［A［i］］;j++）
for（k=1;k《P［A［i］］.size（）;k++）Merge（P［A［i］］［k-1］+j，P［A［i］］［k］+j）;
for（i=1;i《=sum1［s1.length（）-1］;i++）if（GF（i）！=GF（T）&&GF（i）！=GF（T+1）&&（！mark［GF（i）］））ans++，mark［GF（i）］=1;
if（GF（T）！=GF（T+1））printf（“%lld”，QM（2，ans））;
else printf（“0”）;
}
下載文檔
