P5937 [CEOI1999] Parity Game 题解

DGL__DGL_AFO · 2024-11-13 15:25:37 · 个人记录

唉唉没人用 2-sat 写的吗。

蒟蒻来水一发 2-sat 的题解。

今天模拟赛的题，赛时想到了 2-sat ，于是写篇题解。

思路：

发现要数 1 的个数的奇偶性,很容易转化为异或（奇数个 1 异或值为 1 ，偶数个 1 异或值为 0 ）。

设 s[i] 为从 1 到 i 的前缀异或和 。

于是发现性质：

• 若 l - r 中 1 的个数为奇，那么 s[r] \oplus s[l-1]=1 ，说明 s[r] 和 s[l-1] 值不同，反之则说明相同。

因为 s[i] 只有 0 或 1 两种取值，满足 2-sat 的条件。

因为只有 m 次询问，所以最多只有 2m 个位置，单次做 2-sat 的时间复杂度为 O（m） ，枚举或二分皆可。

总时间复杂度为 O(m^2) 或 O (mlogn) 。

一些小细节见代码。

代码（赛时写的丑陋代码，用的枚举）：

#include<bits/stdc++.h>
using namespace std;
int n,m;
int p[21450],cnt,op;
int l[11450],r[11450],k[11450];
int h[114514],e[214514],ne[214514],idx;
int st[21450],ask[21450];
unordered_map<int,int> un;
string gen;
int flag;
vector<int> v;

inline void add(int a,int b)
{
    idx++;
    ne[idx]=h[a];
    e[idx]=b;
    h[a]=idx;
}

inline void dfs(int x)
{
    st[x]=1;
    ask[x]=1;
    if(x<=op)
    {
        v.push_back(x);
        if(ask[x+op])
        {
            flag=1;
            return ;
        }
    }     
    if(x>op) 
    {
        v.push_back(x);
        if(ask[x-op])
        {
            flag=1;
            return ;
        }       
    } 
    for(int i=h[x];i;i=ne[i])
    {
        int y=e[i];
        if(!st[y])
          dfs(y);
    }
}

inline bool check()
{
    memset(ask,0,sizeof ask);
    memset(st,0,sizeof st);

    for(int i=1;i<=op;i++)
    {
        if(!st[i])
        {
            flag=0;
            dfs(i);
            if(flag) 
              return false;
            for(int j=v.size()-1;j>=0;j--)
            {
                //cout<<v[j]<<" ";
                ask[v[j]]--;
                v.pop_back();
            }  
            //cout<<"|| ";
        }   

    }
    //cout<<'\n';  
    return true;
}

int main()
{
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        cin>>l[i]>>r[i]>>gen;
        if(gen[0]=='o')
          k[i]=1;  
        l[i]--;
        p[++cnt]=l[i];
        p[++cnt]=r[i];
    }

    sort(p+1,p+1+cnt);
    for(int i=1;i<=cnt;i++)
      if(!un[p[i]])
        un[p[i]]=++op;

    for(int i=1;i<=m;i++)
    {
        int a=un[l[i]],b=un[r[i]];
        if(!k[i])
        {
            add(a,b);
            add(b,a);
            add(a+op,b+op);
            add(b+op,a+op);
        }
        else
        {
            add(a,b+op);
            add(b+op,a);
            add(b,a+op);
            add(a+op,b);
        }
        if(!check())
        {
            cout<<i-1<<' ';
            return 0;
        }
    }

    cout<<m;

    return 0;
} 
/*
10 
5
1 2 even
3 4 odd
5 6 even
1 6 even
7 10 odd
*/