51nod-1204 并查集

你的朋友写下一串包含1和0的串让你猜，你可以从中选择一个连续的子串（例如其中的第3到第5个数字）问他，该子串中包含了奇数个还是偶数个1，他会回答你的问题，然后你可以继续提问......你怀疑朋友的答案可能有错，或说同他之前的答案相互矛盾，例如：1 - 2 奇数，3 - 4 奇数，那么可以确定1 - 4 一定是偶数，如果你的朋友回答是奇数，就产生了矛盾。给出所有你朋友的答案，请你找出第一个出现矛盾的答案。

Input

第1行：2个数N, Q，N为串的长度，Q为询问的数量。（2 <= N <= 100000, 2 <= Q <= 50000)

第2 - Q + 1行：每行包括两个数以及一个字符串来描述朋友的回答，2个数中间用空格分隔，分别表示区间的起点和终点，后面的字符为"even"或"odd"，表示朋友的答案。

Output

输出1个数，表示朋友的答案中第一个错误答案的位置，如果所有答案均不矛盾，则输出-1。

Input示例

10 5

1 2 even

3 4 odd

5 6 even

1 6 even

7 10 odd

Output示例

4

思路就是，用数组1到n的空间表示这个序列有偶数个1，比如f[20]就表示序列1到20有偶数个1，也就是说都是从1开始的，数组1到n的空间向右偏移n个位置表示这个序列有奇数个1.
然后当输入（l,r）的时候，如果（l,r）有奇数个1，那么表示（1，r）与（1，l-1）奇偶性相反；如果（l,r）有偶数个1，那么表示（1，r）与（1，l-1）奇偶性相同；
第一种情况分为前奇后偶和前偶后奇，前奇后偶则将（1，r）与（1，l-1+n）打上相同标记，也就是并查集一个分类的过程，后者如图。
第二种情况分为同奇同偶，同样打标记如图。。。。字丑勿喷

#include <iostream>

#include <math.h>

#include <algorithm>

#include <stdio.h>

#define maxn 100005

using namespace std;

int f[maxn*];

int find(int x)

{

    return x==f[x]?x:f[x]=find(f[x]);

}

void merge(int x,int y)

{

    x=find(x),y=find(y);

    if(x!=y) f[x]=y;

}

int main()

{

    for(int i=;i<maxn*;i++) f[i]=i;

    int n,q,l,r,flag=-;

    char s[];

    cin>>n>>q;

    for(int i=;i<=q;i++)

    {

        cin>>l>>r>>s;

        if(flag==-)

        if(s[]=='e')

        {

            if(find(r)==find(l-+n)&&find(r+n)==find(l-))

            {

                flag=i;

            }

            else

            {

                merge(r,l-);

                merge(r+n,l-+n);

            }

        }

        else

        {

            if(find(r)==find(l-)&&find(r+n)==find(l-+n))

            {

                flag=i;

            }

            else

            {

                merge(r,l-+n);

                merge(r+n,l-);

            }

        }

    }

    cout<<flag<<endl;

 }

巴特西

51nod-1204 并查集

最新文章

热门文章