Luogu p2456 二进制方程

这是一道我也不知道我gu了多久的题目

（然鹅还有n多任务没有完成）

反正——我太难了

好了言归正传，题目链接

是一道校内测的题目（现在应该没有人没考了吧？）

思路的话，是神仙并查集√

觉得虽然并查集很简单，但很容易想不到要用并查集解题呢

首先，考场上卡死我的就是怎么分别表示\(a_1,a_2……,a_n\)，然后其实我们可以直接按照\(a_1,a_2,……,a_n,b_1,b_2,……b_n，……\)的顺序依次编号（注意并查集时需要考虑0和1，所以需要从2开始编号）。

k=read();

num[1]=2;

for（int i=1,x;i<=k;i++){

    x=read();

    num[i+1]=num[i]+x;

    sum+=x;//记录总共编号多少个？

}

其中\(num[i]\)表示第i种字母（从a开始记做1）的第一个字符的编号是多少；

可能有点凌乱，举个例子：

样例#1：

0	1	\(a_1\)	\(a_2\)	\(a_3\)	\(a_4\)	\(b_1\)	\(b_2\)
0	1	2	3	4	5	6	7

此时，\(num[1]=2,num[2]=6;\)

编号完成后，也就是先按照编号将两个字符串展开到相同长度的数组中（应该不难写叭）

int s[mx],t[mx];

char S[mxl],T[mxl];

scanf("%s",S);

int len=strlen(S);

int j=0;

for(int i=0;i<len;i++){

    if(S[i]=='1'||S[i]=='0') s[++j]=S[i]-'0';

    else {

        int fr=S[i]-'a'+1;

        for(int l=num[fr];l<num[fr+1];l++) s[++j]=l;

	}

}

//T字符串也相同的做法，这里不再写了

然后就是神仙并查集的天下了：

我们很容易想到：

如果有一位上，两个字符串分别为1和0，那么显然是无解的，直接输出0，return 0;

如果有一位上，两个字符串的对应中是1和某个字母或者是0和某个字母，那么这样显然解的情况只有一种，我们需要利用并查集将这个字母与1或0并起来；

如果这一位上都是字母，那么我们将这两个字母对应的编号并到一个集合中去；

最后我们要求的，也就是有多少个集合（不算0和1的集合）；

最终答案就是\(2^{集合个数}\)（因为很大所以记得写高精）讲真的这道题对我来说高精是最难的（我太菜了）

然后并查集的时候，需要注意在合并的时候要注意保持单调，要不然就是全部向大的合并，要不然就全部向小的合并，总之不可以乱合并。

此外，如果合并完成后，0和1在同一个集合中，那么也是无解的，需要特殊考虑。

反正语言很混乱，将就着叭；

上代码：

#include<bits/stdc++.h>

#define ll long long

using namespace std;

inline int read(){

	int ans=0;

	char last=' ',ch=getchar();

	while(ch>'9'||ch<'0') last=ch,ch=getchar();

	while(ch>='0'&&ch<='9') ans=(ans<<1)+(ans<<3)+ch-'0',ch=getchar();

	if(last=='-') ans=-ans;

	return ans;

}

int k;

int fir[30],sum;

char S[10010],T[10010];

int s[10010],t[10010];

int fa[10010];

int find(int x){

//	cout<<x<<endl;

	if(fa[x]!=x) fa[x]=find(fa[x]);

	return fa[x];

}

void B(int x,int y){

	int a=find(x);

	int b=find(y);

	if(a!=b) {

		if(a<b) fa[b]=a;

		else fa[a]=b;

	}

}

void out(int x){

	int a[100010],len=1;

	a[0]=1;

	for(int i=1;i<=x;i++){

		a[0]*=2;

		for(int j=1;j<len;j++){

			a[j]=a[j]*2+a[j-1]/10;

			a[j-1]%=10;

		}

		while(a[len-1]>=10){

			a[len]=a[len-1]/10;

			a[len-1]%=10;

			len++;

		}

	}

	for(int i=len-1;i>=0;i--) cout<<a[i];

}

int main(){

	k=read();

	fir[1]=2;

	for(int i=1,x;i<=k;i++){

		x=read();

		fir[i+1]=fir[i]+x;

		sum+=x;

	}

	for(int i=0;i<=sum+1;i++) fa[i]=i;

	scanf("%s",S);

	int len=strlen(S);

	int j=0;

	for(int i=0;i<len;i++){

		if(S[i]=='1'||S[i]=='0') s[++j]=S[i]-'0';

		else {

			int d=S[i]-'a'+1;

			for(int l=fir[d];l<fir[d+1];l++)

				s[++j]=l;

		}

	}

	scanf("%s",T);

	len=strlen(T);

	j=0;

	for(int i=0;i<len;i++){

		if(T[i]=='1'||T[i]=='0') t[++j]=T[i]-'0';

		else {

			int d=T[i]-'a'+1;

			for(int l=fir[d];l<fir[d+1];l++)

				t[++j]=l;

		}

	}

	for(int i=1;i<=j;i++){

		if(s[i]==0){

			if(t[i]==1) {

				printf("0");

				return 0;

			}

			else B(s[i],t[i]);

		}

		else if(s[i]==1){

			if(t[i]==0) {

				printf("0");

				return 0;

			}

			else B(s[i],t[i]);

		}

		else B(s[i],t[i]);

	}

	int ans=0;

	if(fa[1]==0) {

		printf("0");

		return 0;

	}

	for(int i=2;i<=sum+1;i++){

		int d=find(i);

		if(d==i) ans++;

	}

	out(ans);

	return 0;

}

end√

巴特西

Luogu p2456 二进制方程

最新文章

热门文章