AcWing:239. 奇偶游戏(前缀和 + 离散化 + 带权并查集 + 异或性质)

小A和小B在玩一个游戏。

首先,小A写了一个由0和1组成的序列S,长度为N。

然后,小B向小A提出了M个问题。

在每个问题中,小B指定两个数 l 和 r,小A回答 S[l~r] 中有奇数个1还是偶数个1。

机智的小B发现小A有可能在撒谎。

例如,小A曾经回答过 S[1~3] 中有奇数个1, S[4~6] 中有偶数个1,现在又回答 S[1~6] 中有偶数个1,显然这是自相矛盾的。

请你帮助小B检查这M个答案,并指出在至少多少个回答之后可以确定小A一定在撒谎。

即求出一个最小的k,使得01序列S满足第1~k个回答,但不满足第1~k+1个回答。

输入格式

第一行包含一个整数N,表示01序列长度。

第二行包含一个整数M,表示问题数量。

接下来M行,每行包含一组问答:两个整数l和r,以及回答“even”或“odd”,用以描述S[l~r] 中有奇数个1还是偶数个1。

输出格式

输出一个整数k,表示01序列满足第1~k个回答,但不满足第1~k+1个回答,如果01序列满足所有回答,则输出问题总数量。

数据范围

N109,M10000N≤109,M≤10000

输入样例:

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

输出样例:

3

 

题解:如果我们用sum数组表示序列S的前缀和,那么在每个回答中:

  1、S[l ~ r] 有偶数个1,等价于 sum[l - 1] 与 sum[r] 奇偶性相同。

  2、S[l ~ r] 有奇数个1,等价于 sum[l - 1] 与 sum[r] 奇偶性不同。

注意,我们在本题中不需要求sum数组,只要把它看成一个变量。

 

例如:1、x1 与 x2 的奇偶性相同,x2 与 x3 的奇偶性也相同,那么 x1 与 x3 的奇偶性相同。

      2、x1 与 x2 的奇偶性相同,x2 与 x3 的奇偶性不同,那么 x1 与 x3 的奇偶性不同。

      3、x1 与 x2 的奇偶性不同,x2 与 x3 的奇偶性不同,那么 x1 与 x3 的奇偶性相同。

假设 d[x] 是 x ~ p 的奇偶性, d[y] 是 y ~ q 的奇偶性, d[p] 是 p ~ q 是奇偶性(其中x ~ p 和 y ~ q是两个不同的集合,p ~ q是两个集合的路径)。那么,ans = d[x] ^ d[y] ^ d[p],可以推出d[p] = d[x] ^ d[y] ^ ans(读者可以自己证明)。

 

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>

using namespace std;

const int maxn = 1e4+7;

struct node {
    int l, r, ans;
}arr[maxn];

vector<int> v;
int f[maxn];
int d[maxn];
int n, m;

int find(int x) {
    return lower_bound(v.begin(), v.end(), x) - v.begin() + 1;
}

void init() {
    v.clear();
    for(int i = 1; i <= m; i++) {
        char str[5];
        scanf("%d %d %s", &arr[i].l, &arr[i].r, str);
        arr[i].ans = (str[0] == o) ? 1 : 0;    //奇数为1,偶数为0
        v.push_back(arr[i].l - 1);
        v.push_back(arr[i].r);
    }
    sort(v.begin(), v.end());
    v.erase(unique(v.begin(), v.end()), v.end());    //离散化
    n = v.size();
    for(int i = 0; i <= n; i++) {
        f[i] = i;
        d[i] = 0;
    }
}

int get(int x) {
    if(x == f[x]) {
        return f[x];
    }
    int root = get(f[x]);
    d[x] ^= d[f[x]];
    return f[x] = root;
}

int main() {
    scanf("%d %d", &n, &m);
    init();
    for(int i = 1; i <= m; i++) {
        int x = find(arr[i].l - 1);
        int y = find(arr[i].r);
        int fx = get(x);
        int fy = get(y);
        if(fx == fy) {
            if((d[x] ^ d[y]) != arr[i].ans) {    //与前面的回答相矛盾
                printf("%d\n", i - 1);
                return 0;
            }
        } else {
            f[fx] = fy;
            d[fx] = d[x] ^ d[y] ^ arr[i].ans;
        }
    }
    printf("%d\n", m);
    return 0;
}

 

AcWing:239. 奇偶游戏(前缀和 + 离散化 + 带权并查集 + 异或性质)

上一篇:laravel使用Dingo\Api通过response()->json()返回空对象


下一篇:关于C#中Convert.ToInt32()是干什么用的