scau 1138 代码等式

SCAU-gogocj 2019-12-02 原文

代码借鉴大佬：https://www.cnblogs.com/DOLFAMINGO/p/7538771.html

 1 #include<cstdio>//scau 1138 代码等式
 2 #include<cstring>
 3 #include<cstdlib>
 4 #include<cmath>
 5 
 6 int fa[10010],length[30],beg[30];//fa是用来放爸爸的，length是用来放每一个字母的长度，beg是用来放字母代表的一串数字的第一个数的值
 7 
 8 int find(int x)
 9 {
10     return (x==fa[x]?x:find(fa[x]));
11 }
12 
13 void Union(int m, int n)
14 {
15     m = find(m);
16     n = find(n);
17     if(m!=n)
18         fa[m] = n;
19 }
20 
21 int main()
22 {
23     int n, s1[10010],s2[10010],len1 = 0,len2 = 0;//n伟字母的个数，然后是s1和s2分别是左边和右边的转化完之后的串存放的数组，len1和len2分别是左边式子和右边式子转化后数字的个数
24     scanf("%d",&n);
25     scanf("%d",&length[0]);
26     beg[0] = 2;
27     for(int i = 1; i<n; i++)
28     {
29         scanf("%d",&length[i]);
30         beg[i] = beg[i-1] + length[i-1];
31     }
32 
33     char ch;
34     getchar();
35     while((ch= getchar())!='=')
36     {
37         if(ch=='0' || ch=='1')
38             s1[len1++] = ch-'0';
39 
40         else
41         {
42             for(int i = 0; i<length[ch-'a']; i++)
43                 s1[len1++] = beg[ch-'a'] + i;
44         }
45     }
46 
47     while((ch= getchar())!='\n')
48     {
49         if(ch=='0' || ch=='1')
50             s2[len2++] = ch-'0';
51 
52         else
53         {
54             for(int i = 0; i<length[ch-'a']; i++)
55                 s2[len2++] = beg[ch-'a'] + i;
56         }
57     }
58 
59     if(len1!=len2)
60     {
61         printf("0\n");
62         return 0;
63     }
64     
65     for(int i = 0; i<beg[n-1]+length[n-1]; i++) //初始化每个单位变量的集合为自己
66         fa[i] = i;
67 
68     for(int i = 0; i<len1; i++)//并查集
69     {
70         if(s1[i]+s2[i]==1)
71         {
72             printf("0\n");
73             return 0;
74         }
75 
76         Union(s1[i],s2[i]);
77     }
78 
79     int ans = 0;
80     for(int i = 0; i<beg[n-1]+length[n-1]; i++)//遍历每个单位变量，统计集合个数
81         if(fa[i]==i) ans++;
82 
83     printf("%.0lf\n",pow(2,ans-2));
84     return 0;
85 }