题目描述

解题思路

这个题目使用到前缀和的思想，我们l-r中有奇数个一，就说明，s[r] - s[l-1]是奇数，同样说明s[r]和s[l-1]奇偶性不同。如果是偶数的话那就说明相同。在这里我们的奇偶性判断是双向传递性质的，我们可以使用并查集来维护每个节点是不是相对于同一个点奇偶性相同（需要在同一集合）。
异或操作就是没有进位的加法

  1. l r even :
    • l 和 r在同一集合 ，如果((d[l] + d[r]) % 2 == 1) => d[l] ^ d[r] == 1那么就出错;
    • l 和 r不在同一集合，需要满足(d[l] + d[r] + ? ) % 2 == 0) =>(d[l] ^ ? ^ d[r]) % 2 == 0。? = d[l] ^ d[r]。
  2. l r odd :
    • l 和 r在同一集合 ，如果((d[l] + d[r]) % 2 == 0) => d[l] ^ d[r] == 0那么就出错;
    • l 和 r不在同一集合，需要满足(d[l] + d[r] + ? ) % 2 == 1) =>(d[l] ^ ? ^ d[r]) % 2 == 1。? = d[l] ^ d[r] + 1。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
import java.util.*;
import java.io.*;
class Main{
    public static int N = 5010,P = 10007;
    public static int[] hash = new int[P],find = new int[P],d = new int[P];
    public static Scanner sc = new Scanner(System.in);

    public static int find(int x){
        if(find[x] != x){
            int parent = find[x];
            find[x] = find(parent);
            d[x] += d[parent];
        }
        return find[x];
    }

    public static int get(int x){
        int k = x % P;
        for(int i = k;;i = (i + 1) % 2*N)
            if(hash[i] == -1 || hash[i] == x) return i;
    }

    public static void main(String[] args){
        int n = sc.nextInt();
        int m = sc.nextInt();
        Arrays.fill(hash,-1);
        for(int i = 1;i < P;i++) find[i] = i;
        for(int i = 1;i <= m;i++){
            int ha = sc.nextInt(),hb = sc.nextInt();
            int a = get(ha-1),b = get(hb);
            hash[a] = ha - 1;hash[b] = hb;
            String os = sc.next();
            int fa = find(a),fb = find(b);
            if(fa == fb){
                if((d[a] ^ d[b]) % 2 == 1 && os.equals("odd") || (d[a] ^ d[b]) % 2 == 0 && os.equals("even"))
                    continue;
                System.out.println(i-1);
                return;
            }else{
                find[fa] = fb;
                d[fa] = d[a] ^ d[b];
                if(os.equals("odd")) d[fa] ^= 1;
            }
        }
        System.out.println(m);
    }
}