[SDOI2006] 二进制方程

2019/01/02 10:58
阅读数 18

~~并查集水题。~~维护变量的对应位的相关关系,判断不确定点(自由元)的个数即可。 代码中的p数组:p[1] 值的id, p[2~k+1]每个变量的第一位的id。

#include <bits/stdc++.h>
using namespace std;
const int N=1e4+7;

int n,m,k,tot;
int p[N],fa[N],x[N],y[N];

int get(int x) {return fa[x]==x? x: fa[x]=get(fa[x]);}

int main() {
	p[1]=2; 
	scanf("%d",&k);
	for(int i=2,x; i<=k+1; ++i) {
		scanf("%d",&x);
		p[i]=p[i-1]+x;
		tot+=x;
	}
	
	static char str[N];
	scanf("%s",str);
	for(int i=0; str[i]; ++i) {
		if(isalpha(str[i])) {
			int c=str[i]-'a'+1;
			for(int j=p[c]; j<p[c+1]; ++j) x[++n]=j;
		} else x[++n]=str[i]-'0';
	}
	scanf("%s",str);
	for(int i=0; str[i]; ++i) {
		if(isalpha(str[i])) {
			int c=str[i]-'a'+1;
			for(int j=p[c]; j<p[c+1]; ++j) y[++m]=j;
		} else y[++m]=str[i]-'0';
	}
	
	if(n!=m) {
		puts("0");
		return 0;
	}
	for(int i=1; i<N; ++i) fa[i]=i;
	for(int i=1; i<=n; ++i) {
		int dx=get(x[i]), dy=get(y[i]);
		if(dx+dy==1) {
			puts("0");
			return 0;
		}
		if(dx!=dy) {
			fa[max(dx,dy)]=min(dx,dy);
			tot--;
		}
	}
	
	static int dig[N]={1},top=1;
	while(tot--) {
		for(int i=0; i<top; ++i) dig[i]<<=1;
		for(int i=0; i<top; ++i) if(dig[i]>=10) {
			dig[i+1]+=dig[i]/10, dig[i]%=10;
		}
		for(; dig[top]; ++top) {
			dig[top+1]+=dig[top]/10, dig[top]%=10;
		}
	}
	for(int i=top-1; ~i; --i) printf("%d",dig[i]);
	return 0;
}

以下为输入格式:

第一行:k(k<=26,变量的个数,规定使用小写英文字母中的前k个字母作为变量,如k=5,则变量a,b,c,d,e)。 第二行:k个正整数,中间用一个空格隔开,依次代表k个变量的长度。 第三行:等式左边的表达式。 第四行:等式右边的表达式。

展开阅读全文
打赏
0
0 收藏
分享
加载中
更多评论
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部