dango

[hdu3234] Exclusive-OR

（从自己的CSDN博客转来的）

一、题目描述

http://acm.hdu.edu.cn/showproblem.php?pid=3234

存在n个正数。题目逐渐给出信息或询问。

如果中途出现冲突，输出有冲突，其余语句全部忽略。

详见原题。

二、准备知识

对于a,b,c有：a xor b == c 和 a xor c == b 和 b xor c == a 等价

三、题目分析

    首先可以想到这是比较经典的并查集模型，不过并不是赤裸裸的，有一些细节需要考虑。

    利用带路径压缩的并查集模型，同时记录节点到其父节点的xor值。

    father[i]记录父节点，offxor[i]记录节点到父节点的xor值, value[i]记录数值大小

    一些细节，很多细节可以通过画图看出，一图胜千言：

    1、在处理I p v或者I p q v时，set_value的时候处理根节点的value。因为之后很多东西都要用到根的value值，或是判断根节点的value是否存在。

    2、处理Q，即处理询问时。记录p1 p2 ... pk的根和每个根出现的次数。如果出现的次数是奇数次，那么就需要用到根的value了。这样也可以判断是不是I don't know.

四、源代码

hdu3234
#include <cstdio>
#include <cstring>
#include <sstream>
#include <algorithm>
using namespace std;
#define MAXN 20005
#define MAXK 20

int N, Q, p, q, v, k, fact;
char type;
int father[MAXN], offxor[MAXN], value[MAXN]; //offset[x]为x到其父亲节点的xor值 
int num[MAXK];

bool init(){
    scanf("%d %d", &N, &Q);
    if (N == 0 && Q == 0) return false;
    memset(offxor, 0, sizeof (int) * N);
    memset(value, 255, sizeof (int) * N);    //初始化value为-1 
    for (int i = 0; i < N; ++i)
        father[i] = i;
    return true;
}

void get_data(){
    char in_str[1000];
    do {
        scanf("%c", &type);
    } while (type != 'I' && type != 'Q');
    if (type == 'I'){
        gets(in_str);
        int t = sscanf(in_str, "%d%d%d", &p, &q, &v);
        if (t == 2) v = q;         //如果只读到两个数字，为I p v类型 
        else type = 'L';        //否则为 I p q v 类型，记为L （Long)
    }
    else
    {
        scanf("%d", &k);
        for (int i=0; i<k; i++)
            scanf("%d", &num[i]);
    }
}

int find_set(int x){
    int rx = x, xor_total = 0, t;
    while (father[rx] != rx) {
        xor_total = xor_total ^ offxor[rx];
        rx = father[rx];
    }
    while (x != rx) {                        //路径压缩 
        xor_total = xor_total ^ offxor[x];
        offxor[x] = xor_total ^ offxor[x];    //调整offxor值为节点到根的xor 
        t = father[x];
        father[x] = rx;                        //改父节点 
        x = t;
    }
    return rx;
}

void set_value(int x, int v) {
    int rx = find_set(x);
    value[x] = v;
    value[rx] = v ^ offxor[x];                //主要是要保证根节点有value值 
}

void union_set(int x, int y, int v) {
    int rx = find_set(x), ry = find_set(y);
    father[ry] = rx;
    offxor[ry] = v ^ offxor[x] ^ offxor[y];
    if ( value[ry] != -1 && value[rx] == -1 )
        set_value(ry, value[ry]);            //用set, 保险起见 
}

bool solve(){
    if (type == 'I'){
        ++fact;
        int rp = find_set(p);
        if (value[rp] == -1) set_value(p, v);
        else 
            if (value[rp] != (offxor[p] ^ v)){
                printf("The first %d facts are conflicting.\n", fact);
                return false;
            }
    }
    if (type == 'L'){
        ++fact;
        int rp = find_set(p), rq = find_set(q);
        if (rp == rq){
            if (v != (offxor[p] ^ offxor[q])){
                printf("The first %d facts are conflicting.\n", fact);
                return false;
            }
        }
        else
            union_set(p, q, v);
    }
    if (type == 'Q'){
        int root_temp[MAXK], xor_temp[MAXK], times[MAXK];
        int tot = 0, i, j;
        for (i=0; i<k; i++)
        {
            int rx = find_set(num[i]);
            for (j=0; j<tot; j++)
                if (root_temp[j] == rx) break;
            if (j == tot){
                root_temp[tot] = rx;
                xor_temp[tot] = offxor[num[i]];
                times[tot++] = 1;
            }
            else{
                xor_temp[j] = xor_temp[j] ^ offxor[num[i]];
                times[j]++;
            }
                
        }
        int ans = 0;
        for (i=0; i<tot; i++){
            ans = ans ^ xor_temp[i];
            if (times[i] % 2 == 1){
                if (value[root_temp[i]] == -1){
                    printf("I don't know.\n");
                    return true;                //返回true，因为没冲突
                }
                else
                    ans = ans ^ value[root_temp[i]];
            }
        }
        printf("%d\n", ans);
    }
    return true;
}
                     
int main(){
    int Cases = 0;
    while (init()){
        printf("Case %d:\n", ++Cases);
        int flag = true;         // !flag 表示已经产生冲突 
        fact = 0;
        while (Q--){
            get_data();
            if (flag) flag = solve();
        }
        printf("\n");
    }
    return 0;
}
            
        

五、心得

1、memset(value, 255, sizeof (int) * N); 可以利用255将数组初始化为-1，以后不用写for初始化为-1了

2、"#include <sstream>" + "gets(in_str);" + "int t = sscanf(in_str, "%d%d%d", &p, &q, &v);"

    可以很好处理这道题之类I类型不知道后面要读几个数字的问题。先把字符串读进来，然后用sscanf从字符串中读取数字，利用其返回值就知道读到几个数字了。sscanf还有其他很多功能，抛砖引玉，以后再有需要就多了一个可以寻找的方向了。

3、又PE了一次，以后一定要看清楚每组数据之间是否要输出空行，不管Sample Output里头有没有。