一道特别玄学的题
Description 你偶尔和朋友玩如下的游戏。你的朋友写下一个由01组成的序列。你选择连续的一段子序列（例如，从第3到第5个数的子序列），问他这一段中1的个数是偶数还是奇数。你的朋友会回答你的问题，然后你可以问他另外一段子序列，等等。你的任务是猜出整个序列。 你怀疑你朋友的一些回答可能是错误的，并且你希望证明他说了假话。因此你决定写一个程序来帮助你。这个程序将会收到你的一系列问题以及你朋友给出的答案。程序的目标是找到第一个被证明是错误的回答，即，存在一个序列能满足之前所有回答，但加上这个回答后就不存在相应的序列。 Input 第一行有一个整数，代表01序列的长度。长度不超过1000000000。 第二行有一个正整数，代表询问和回答的数量。数量不超过5000. 接下来的若干行描述了所有的了询问和回答。每一行包含了一个询问和对此询问的回答：两个整数（所选择的子序列的起止点），一个单词“even”或“odd”（答案，即该子序列中1的个数的奇偶性），其中“even”代表有偶数个，“odd”代表有奇数个。 Output 输出一个整数X。它意味着：存在一个01序列满足前X个奇偶性询问，但不存在满足前X+1个奇偶性询问的序列。如果存在满足所有询问的序列，X就应该是询问的总数。 Sample Input 输入样例1： 10 5 1 2 even 3 4 odd 5 6 even 1 6 even 7 10 odd 输入样例2： 10 5 1 2 even 1 4 even 2 4 odd 1 10 even 3 10 even 1 2 even Sample Output 输出样例1： 3 输出样例2： 5
首先离散化一下（把没有出现过的点全看做偶数，于是可以直接X掉）
然后连边
对于每个询问Q（a,b,c）(c为even或odd)
在a,b间连一条权值为c的边(even==0,odd==1)
但这时发现，如果1,2为even,3,4为even,那么1,4就已经知道是even了
然而程序里得不到体现，
于是将“在a,b间连一条权值为c的边”改成“在a-1,b间连一条权值为c的边”
然后惊喜的发现0,4联通了！！！
需要注意的是，如果图上有环，就说明朋友的话可能会起冲突了，
打表证明：如果环上边权值和为even，则不起冲突，反之起冲突
用并查集维护两点是否联通，如果两点联通时要连边，则取消，判断这两点之间的路径权值之和
与这条要加的边权值相加再判断即可
这样保证了图是一棵树，因为数据水，判断环上权值和可以直接暴力！！！
水过！！！！！！
#include<cstdio> #include<algorithm> #include<map> #include<cmath> using namespace std; typedef long long ll; const int maxn=10002,maxm=10002; int fir[maxn],dis[maxn],nxt[maxn],id=1,w[maxn]; #define il inline #define vd void #define t (dis[i]) il int gi(int x=0){ char ch=getchar(); while(ch<'0'||ch>'9')ch=getchar(); while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar(); return x; } il vd add(int a,int b,int c){ nxt[++id]=fir[a],fir[a]=id,dis[id]=b,w[id]=c; } int Qa[5111],Qb[5111],Qc[5111],nums[11111],k=0; char str[10]; map<int,int>m; int fa[maxn]; il int hd(int now){ if(fa[now]^now)fa[now]=hd(fa[now]); return fa[now]; } il int dfs(int now,int final,int fa,int num){ if(now==final)return num&1; for(int i=fir[now];i;i=nxt[i]) if(t!=fa){ int kk=dfs(t,final,now,num^w[i]); if(kk!=-1)return kk; } return -1; } int main(){ int n=gi(),q=gi(); for(int i=1;i<=q;i++){ Qa[i]=gi()-1,Qb[i]=gi(),scanf("%s",str); if(str[0]=='o')Qc[i]=1; else Qc[i]=0; nums[++k]=Qa[i],nums[++k]=Qb[i]; } sort(nums+1,nums+q+q+1); int s=0; for(int i=1;i<=q<<1;i++)if(nums[i]!=nums[i-1])m[nums[i]]=++s; for(int i=1;i<=s;i++)fa[i]=i; for(int hehehe=1;hehehe<=q;hehehe++){ int a=m[Qa[hehehe]],b=m[Qb[hehehe]],c=Qc[hehehe]; if(hd(a)!=hd(b))fa[hd(a)]=hd(b),add(a,b,c),add(b,a,c); else if(dfs(a,b,-1,0)!=c){printf("%d\n",hehehe-1);return 0;} }printf("%d\n",q); return 0; }
