poj1733 Parity game(离散化+并查集)

水深无声 2021-09-15 17:08 193阅读 0赞

题目链接：[http://poj.org/problem?id=1733][http_poj.org_problem_id_1733]  
用sum数组表示序列的前缀和  
1. s\[l~r\]有偶数个1 -> sum\[l-r\]和sum\[r\]奇偶性相同  
2. s\[l~r\]有奇数个1 -> sum\[l-r\]和sum\[r\]奇偶性不同

有3种传递关系  
1. x1与x2奇偶性相同，x2与x3奇偶性相同，则x1与x3奇偶性相同  
2. x1与x2奇偶性相同，x2与x3奇偶性不同，则x1与x3奇偶性不同  
3. x1与x2奇偶性不同，x2与x3奇偶性不同，则x1与x3奇偶性相同

由于序列长度较大，需要用**离散化**

struct
    {
        int l, r, ans;
    } query[10010];
    int a[maxn],sett[maxn],val[maxn],n,m,t;
    
    void read_discrete()   // 读入、离散化
    {
        cin >> n >> m;
        for (int i = 1; i <= m; i++)
        {
            char str[5];
            scanf("%d%d%s", &query[i].l, &query[i].r, str);
            if(str[0] == 'o')
            query[i].ans = 1;
            else
                query[i].ans = 0;
            a[++t] = query[i].l - 1;
            a[++t] = query[i].r;
        }
        sort(a + 1, a + t + 1);
        n = unique(a + 1, a + t + 1) - a - 1;
    }

然后“边带权”和“扩展域”两种**并查集**都可以写

**边带权**  
**路径压缩**：对x到树根路径上的所有边权做异或操作，即可得到x与树根的奇偶性，边权为0，代表相同，为1，不同

#include<iostream>
    #include<cstdio>
    #include<algorithm>
    using namespace std;
    const int maxn = 20010;
    
    struct
    {
        int l, r, ans;
    } query[10010];
    int a[maxn],sett[maxn],val[maxn],n,m,t;
    
    void read_discrete()   // 读入、离散化
    {
        cin >> n >> m;
        for (int i = 1; i <= m; i++)
        {
            char str[5];
            scanf("%d%d%s", &query[i].l, &query[i].r, str);
            if(str[0] == 'o')
            query[i].ans = 1;
            else
                query[i].ans = 0;
            a[++t] = query[i].l - 1;
            a[++t] = query[i].r;
        }
        sort(a + 1, a + t + 1);
        n = unique(a + 1, a + t + 1) - a - 1;
    }
    
    int findSet(int x)
    {
         if(x==sett[x])
            return x;
         int y = findSet(sett[x]);
         val[x] ^= val[sett[x]];
         return sett[x] = y;
    }
    
    int main()
    {
        read_discrete();
        int flag = 0;
        for (int i = 1; i <= n; i++)
            sett[i] = i;
        for(int i = 1;i<=m;i++)
        {
            if(flag)
                continue;
             // 求出l-1和r离散化之后的值
            int x = lower_bound(a + 1, a + n + 1, query[i].l - 1) - a;
            int y = lower_bound(a + 1, a + n + 1, query[i].r) - a;
            int x1 = findSet(x);
            int y1 = findSet(y);
            if(x1==y1)
            {
                if((val[x]^val[y]) != query[i].ans)
                    {
                        printf("%d\n",i-1);
                        flag = 1;
                    }
            }
            else// 不在同一集合，合并
            {
                sett[x1] =y1;
                val[x1]= val[x] ^ val[y] ^ query[i].ans;
            }
        }
        if(!flag)
            cout << m << endl;
        return 0;
    }

**扩展域**

#include<iostream>
    #include<cstdio>
    #include<cstring>
    #include<algorithm>
    using namespace std;
    struct { int l, r, ans; } query[10010];
    int a[20010], sett[40010], n, m, t;
    void read_discrete() { // 读入、离散化
        cin >> n >> m;
        for (int i = 1; i <= m; i++) {
            char str[5];
            scanf("%d%d%s", &query[i].l, &query[i].r, str);
            query[i].ans = (str[0] == 'o' ? 1 : 0);
            a[++t] = query[i].l - 1;
            a[++t] = query[i].r;
        }
        sort(a + 1, a + t + 1);
        n = unique(a + 1, a + t + 1) - a - 1;
    }
    int findSet(int x) {
        if (x == sett[x]) return x;
        return sett[x] = findSet(sett[x]);
    }
    int main() {
        read_discrete();
        for (int i = 1; i <= 2 * n; i++) sett[i] = i;
        for (int i = 1; i <= m; i++) {
            // 求出l-1和r离散化之后的值
            int x = lower_bound(a + 1, a + n + 1, query[i].l - 1) - a;
            int y = lower_bound(a + 1, a + n + 1, query[i].r) - a;
            int x_odd = x, x_even = x + n;
            int y_odd = y, y_even = y + n;
            if (query[i].ans == 0) { // 奇偶性相同
                if (findSet(x_odd) == findSet(y_even)) { // 矛盾
                    cout << i - 1 << endl;
                    return 0;
                }
                sett[findSet(x_odd)] = findSet(y_odd); // 合并
                sett[findSet(x_even)] = findSet(y_even);
            }
            else { // 奇偶性不同
                if (findSet(x_odd) == findSet(y_odd)) { // 矛盾
                    cout << i - 1 << endl;
                    return 0;
                }
                sett[findSet(x_odd)] = findSet(y_even); // 合并
                sett[findSet(x_even)] = findSet(y_odd);
            }
        }
        cout << m << endl; // 没有矛盾
    }

[http_poj.org_problem_id_1733]: http://poj.org/problem?id=1733

发表评论取消回复

表情：

评论列表（有 0 条评论，193人围观）

还没有评论，来说两句吧...

相关阅读

相关 POJ并查集题目汇总

转来的：[http://hi.baidu.com/czyuan\_acm/blog/item/531c07afdc7d6fc57cd92ab1.html][http_hi.ba

墨蓝/ 2022年09月30日 00:44/ 0 赞/ 150 阅读

相关 poj 1182-食物链【并查集】

食物链 <table> <tbody> <tr> <td><strong>Time Limit:</strong> 1000MS</td>

r囧r小猫/ 2022年08月21日 06:51/ 0 赞/ 165 阅读

相关 POJ1733-离散化+带权并查集

Parity game <table> <tbody> <tr> <td><strong>Time Limit:</strong> 1000MS<

青旅半醒/ 2022年07月11日 06:57/ 0 赞/ 162 阅读

相关 POJ2524 并查集应用

import java.io.FileNotFoundException; import java.util.Scanner; public

曾经终败给现在/ 2022年06月18日 11:08/ 0 赞/ 171 阅读

相关 POJ 1185 食物链（种类并查集）

> 食物链 > Time Limit: 1000MS Memory Limit: 10000K > Total Submissions: 70377 Accepted:

曾经终败给现在/ 2022年06月17日 03:17/ 0 赞/ 192 阅读

相关 POJ-1182.食物链(并查集)

[1182.食物链][1182.] Description 动物王国中有三类动物A,B,C，这三类动物的食物链构成了有趣的环形。A吃B， B吃C，C吃A。现有

蔚落/ 2022年03月07日 01:36/ 0 赞/ 233 阅读

相关 poj3666（DP+离散化）

题目链接：http://poj.org/problem?id=3666 思路：看了讨论区说本题的数据比较弱，只需要考虑不减序列即可，比较懒，所以我也只写了这一部分的代码，

约定不等于承诺〃/ 2021年12月21日 01:05/ 0 赞/ 256 阅读

相关 POJ2524 并查集

include<iostream> using namespace std; int father[50005]; int rank[50005

曾经终败给现在/ 2021年11月29日 17:32/ 0 赞/ 298 阅读

相关扩展并查集——POJ - 1182

题目含义找出与之前的话不符的假话的数目题目分析简单的扩展并查集题目代码 include<iostream> include<stdio.h>

桃扇骨/ 2021年11月22日 09:28/ 0 赞/ 262 阅读

相关 poj1733 Parity game(离散化+并查集)

题目链接：[http://poj.org/problem?id=1733][http_poj.org_problem_id_1733] 用sum数组表示序列的前缀和 1

水深无声/ 2021年09月15日 17:08/ 0 赞/ 194 阅读