【NOIP2017提高A组模拟9.17】信仰是为了虚无之人

Description

Input

Output

Sample Input

3 3 0

1 1 7

1 1 6

1 3 2

Sample Output

1

0

1

7

0

5

Data Constraint

题解

判断真假考虑并查集，设\(g[i]\)表示从当前这棵树的根到\(i\)的前缀异或值，那么对于当前这个区间，\(l-1\)和\(r\)讨论

设\(f1\)是\(l-1\)的根，\(f2\)是\(r\)的根

如果\(f1=f2\)，说明是同一棵树，那么只有\(k=g[r]\ xor\ g[l-1]\)成立的时候才是真
如果\(f1!=f2\)，肯定是真，然后考虑合两棵树并，把\(f1\)和\(f2\)里较大的接到较小的，然后\(g[f2]=g[f2]\ xor\ g[l-1]\ xor\ g[r]\ xor\ k\)，因为要使接上去之后异或值是\(k\)

在并查集\(find\)的时候同时更新\(g[i]\)

设\(s[i]\)表示\(1\)~\(i-1\)的最小异或值

求最小值时，如果当前这个点是祖先，说明这个点的取值没有限制，自然取0最优：\(s[i]=s[i-1]\)。如果不是祖先，那么这个点要填的就是\(g[i]\)，\(s[i]=s[find(i)]^\ xor\ g[i]\)

输出\(s[i]\ xor\ s[i-1]\)

Code

#include<cstdio>

#include<algorithm>

using namespace std;

int n,m,pd,l,r,k,last,f1,f2,x,f[200001],g[200001],sum[200001];

int read()

{

	int res=0,fh=1;char ch=getchar();

	while ((ch<'0'||ch>'9')&&ch!='-') ch=getchar();

	if (ch=='-') fh=-1,ch=getchar();

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

	return res*fh;

}

int find(int x)

{

	if (f[x]==x) return x;

	int xx=find(f[x]);

	g[x]^=g[f[x]];

	return f[x]=xx;

}

int main()

{

	freopen("sanae.in","r",stdin);

	freopen("sanae.out","w",stdout);

	n=read();m=read();pd=read();

	for (int i=1;i<=n;++i)

		f[i]=i;

	while (m--)

	{

		l=read();r=read();k=read();

		if (pd) l^=last,r^=last,k^=last;

		f1=find(l-1);f2=find(r);

		if (f1==f2)

		{

			if ((g[l-1]^g[r])==k) last=1;

			else last=0;

			printf("%d\n",last);

		}

		else

		{

			if (f1>f2) swap(f1,f2);

			f[f2]=f1;

			g[f2]^=g[l-1]^g[r]^k;

			last=1;

			printf("%d\n",last);

		}

	}

	for (int i=1;i<=n;++i)

	{

		x=find(i);

		if (i==x) sum[i]=sum[i-1];

		else sum[i]=sum[x]^g[i];

		printf("%d\n",sum[i]^sum[i-1]);

	}

	fclose(stdin);

	fclose(stdout);

	return 0;

}

巴特西

【NOIP2017提高A组模拟9.17】信仰是为了虚无之人

【NOIP2017提高A组模拟9.17】信仰是为了虚无之人

Description

Input

Output

Sample Input

Sample Output

Data Constraint

题解

Code

最新文章

热门文章