欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

Parity

程序员文章站 2022-07-15 09:42:32
...

你的朋友写下一串包含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。

Sample Input

10 5
1 2 even
3 4 odd
5 6 even
1 6 even
7 10 odd

Sample Output

4

思路:并查集,

代码:

#include<cstdio>
#include<cstring>

int f[100010],vis[100010];

int getf(int v)
{
    if(f[v]==-1) return v;
    int u=getf(f[v]);
    vis[v]+=vis[f[v]];
    f[v]=u;
    return u;
}

int main()
{
    int n,m;
    while(~scanf("%d %d",&n,&m))
    {
        memset(f,-1,sizeof(f));
        memset(vis,0,sizeof(vis));
        int x,y,flag=-1;
        char str[25];
        for(int i=1;i<=m;i++)
        {
            scanf("%d %d %s",&x,&y,str);
            if(flag!=-1) continue;
            x--;
            int num,t1,t2;
            if(str[0]=='e') num=2;
            else num=1;   //奇数记录为1,偶数为2
            t1=getf(x);
            t2=getf(y);
            if(t1!=t2){
                f[t2]=t1;
                vis[t2]=vis[x]-vis[y]+num;
            }
            else if((vis[y]-vis[x])%2 != num%2)  //检查有没有错误
                flag=i;
        }
        printf("%d\n",flag);
    }
}

 

上一篇: Parity

下一篇: parity