SCAU 1138 代码等式并查集

1138 代码等式[附加题]

该题有题解

时间限制:500MS 内存限制:65536K
提交次数:59 通过次数:21

题型: 编程题语言: G++;GCC

Description

一个代码等式就是形如x1x2...xi=y1y2...yj，这里xi和yj是二进制的数字（0或1）或者是一个变量（如英语中的小写字母）。
每一个变量都是一个有固定长度的二进制代码。例如：
a,b,c,d,e是变且它们的长度分别是4,2,4,4,2。考虑等式：1bad1=acbe，这个等式共有16组解。现要求任给一个等式，计算一共有多少组解。
（变量最多26个，长度和不超过10000）

输入格式

第一行数N为变量个数；
第二行N个数，为每个变量的位数
第三行为一个等式

输出格式

输出解的个数，无解输出0

输入样例

5
4 2 4 4 2
1bad1=acbe

输出样例

题解：

可知每个字母变量分为相应长度的01变量，假设这种单位长度的01变量为单位变量。

总思路:将值必须是一样的单位变量放进同一个集合。（在等式的牵连下，某些单位变量的值要对应变化）

具体做法：

1.为每个单位变量分配一个空间（从2开始），存放其所属集合（由于等式中有0和1作为常量，所以也要为0和1分配空间，看其所属集合）。

2.首先是判断等式两边长度是否相等，若相等，则继续。

3.通过并查集，逐步为每个单位变量找到所属的集合，（期间如果发现常量1和常量0被要求在同一个集合，则不可能实现，直接退出）

4.遍历每一个单位变量（从0开始），统计集合数sum，则 ans = pow（2，sum-2）减去2是因为常量0和常量1所在的集合的值已经确定了。

注意：代码等式可能只出现01的其中一个或不出现，那又减去2是否合法呢？不是应该出现几种常量才减去几吗？其实在遍历单位变量找集合时，从0开始，已经假设两个变量都出现了，再减去它，不管有没有真的出现，都不影响答案。类似的好像叫做虚拟变量。

学习之处：将变量放到格子当中，通过下标与变量形成映射。

代码如下：

 1 #include<cstdio>//scau 1138 代码等式
 2 #include<cstring>
 3 #include<cstdlib>
 4 #include<cmath>
 5 
 6 int fa[10010],length[30],beg[30];
 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;
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())!='
')
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
");
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
");
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
",pow(2,ans-2));
84     return 0;
85 }

View Code