POJ1733 Parity game POJ1733 Parity game

题目链接

POJ1733 Parity game

题目概述

给出一段长度为(n)的由(0)或(1)组成的序列串,然后给出(m)次条件,每个条件的形式是i j even(odd)表示区间([i,j])内(1)的个数是偶数个还是奇数个,如果第(k+1)个条件在前面的(k)个条件都满足的条件下无法成立,那么输出(k),如果所有的条件都能满足,那么输出(m),其中:

思路分析

输入的格式隐含着(i leq j),因为原始的输入区间是闭区间([i,j]),这里可以更改为((i-1,j])的形式,一方面便于计算从某个结点开始已知连续已知的区间(1)的个数的奇偶性;另外一方面便于区间的合并,比如样例中的((0,2],(2,4])后面一个可以较为容易的与前面一个合并.合并连续区间根据的事实是:两个奇数相加是偶数,两个偶数相加认识偶数,一个奇数一个偶数相加是奇数.

最重要的一点是,题目中的输入的数据是可以依次连接拼成一个连续区间的,假设当前拼接后的连续的区间的最右面结点是(root),对于此前任何一个区间片段的端点(x)是可以计算出([x,root])这段区间内(1)的个数的奇偶性的,这个区间任意另个合法的区间片段([i,j])((i,j)必须是此前出现过的区间片段的端点)都是可以计算出来的.

利用带权并查集可以计算出这样的某个端点(x)到末端点(根节点)(root)中间(1)的数量的奇偶性,权重是结点(x)到根节点(root)之间已知的(1)是奇数还是偶数,每次find_set查询更新结点(x)到(root)之间的(1)的个数的奇偶性,因为计算(1)的个数实际是结点(x)到(root)路径的长度再加上(1)(包括结点(x)),所以为了可以以(d[x-1])表示从结点(x)到根节点(root)之间的(1)的数量的奇偶性.读取每个约束条件,计算区间([i,j])(实际存储的是((i-1,j])上(1)出现次数的奇偶性.

代码

/*
 * @Author: Shuo Yang
 * @Date: 2020-08-02 15:22:26
 * @LastEditors: Shuo Yang
 * @LastEditTime: 2020-08-03 15:59:23
 * @FilePath: /Code/POJ/1733.cpp
 */
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N = 1e6+5;
int buf[N];
int s[N];
int d[N];
// int cnt[N];
bool flag = true;
int ans = 0;
int cnt = 0;

int find_set(int x){
    if(s[x] == x)
        return x;
    int root = find_set(s[x]);
    d[x] ^= d[s[x]];
    s[x] = root;
    return s[x];
}

void union_set(int x, int y, int value){
    int a = find_set(x);
    int b = find_set(y);
    if(a == b){
        if((d[x] ^ d[y]) != value){
            flag = false;
        }
        return;
    }
    s[a] = b;
    d[a] = d[x]^d[y]^value;
}

struct node{
    int left, right,nums;
};

node nodes[N];

int main(int argc, char** args){
    for(int i = 0; i < N; ++i)
        s[i] = i;
    ios::sync_with_stdio(false);
    cout.tie(0);
    cin.tie(0);
    int n,m;
    cin>>n>>m;
    for(int i = 0; i < m; ++i){
        int a,b,temp;
        string str;
        cin>>a>>b>>str;
        if( str == "even" ){
            temp = 0;
        }else{
            temp = 1;
        }
        nodes[i]={a-1,b,temp};
        buf[cnt++] = a-1;
        buf[cnt++] = b;
    }
    sort(buf, buf+cnt);
    cnt = unique(buf, buf+cnt)-buf;
    for(int i = 0; i < m; ++i){
        int x =  nodes[i].left;
        int y = nodes[i].right;
        int value = nodes[i].nums;
        x = lower_bound(buf, buf+cnt, x)-buf;
        y = lower_bound(buf, buf+cnt, y)-buf;
        union_set(x, y, value);
        if( !flag ){
            cout<<i<<endl;
            break;
        }
    }
    if( flag )
        cout<<m<<endl;
    return 0;
}

两个地方需要注意,一是(N)的规模比较大,可以先进行离散化处理,而是要在读入数据时进行一个简单的预处理,把原来([left,right])形式的输入改为((left-1,right])这样的格式存储两个区间端点,然后利用异或运算简单计算区间的内部(1)出现次数的奇偶性.(PS:事实上在后面检验约束项时候,我把int x = nodes[i].left;写成了int x = nodes[i].left-1;尽然也莫名其妙的过了,抑郁,而且是刚刚写这个时候才发现的┭┮﹏┭┮)

其它