POJ1733Parity game


这道题给出区间奇偶性判断对错,可以维护l-1与r这样一个前缀和,假如两前缀和奇偶相同,那区间就为偶,假如奇偶不同,那区间就为奇,由于区间范围过大,可以考虑离散化,之后通过扩展域解决

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn=40010;
int n,m,a[maxn],tot=0;
int fa[maxn];
int get(int x)
{
    if(fa[x]==x) return x;
    return fa[x]=get(fa[x]);
}
struct node
{
    int l,r,ans;
}query[maxn];
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)
    {
        char s[5];
        scanf("%d%d%s",&query[i].l,&query[i].r,s);
        query[i].ans=(s[0]=='o'?1:0);
        a[++tot]=query[i].l-1;
        a[++tot]=query[i].r;
    }
    sort(a+1,a+1+tot);
    n=unique(a+1,a+1+tot)-(a+1);
    for(int i=1;i<=n*2;i++) fa[i]=i;
    for(int i=1;i<=m;i++)
    {
        int x=lower_bound(a+1,a+1+n,query[i].l-1)-a;
        int y=lower_bound(a+1,a+1+n,query[i].r)-a;
        int x_o=x,x_e=x+n;
        int y_o=y,y_e=y+n;
        if(query[i].ans==0)
        {
            if(get(x_o)==get(y_e))
            {
                printf("%d\n",i-1);
                return 0;
            }
                fa[get(x_o)]=get(y_o);
                fa[get(x_e)]=get(y_e);

        }
        else
        {
            if(get(x_o)==get(y_o))
            {
                printf("%d\n",i-1);
                return 0;
            }
                fa[get(x_o)]=get(y_e);
                fa[get(x_e)]=get(y_o);
        }
    }
    printf("%d\n",m);
    return 0;
}

文章作者: songhn
版权声明: 本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 songhn !
评论
 上一篇
SP1716 GSS3 - Can you answer these queries III SP1716 GSS3 - Can you answer these queries III
这是一道比较复杂的线段树维护题目,由于最大字段和是满足区间可加性的,所以可以通过线段树来维护 void update(int id) { t[id].sum=t[id<<1].sum+t[id<<1|1].s
2019-07-05
下一篇 
P1196 NOI2002银河英雄传说 P1196 NOI2002银河英雄传说
通过带权并查集维护距离 #include<bits/stdc++.h> using namespace std; const int maxn=30010; inline int read() { int x=0,t=1;c
2019-07-05
  目录