设为首页 加入收藏

TOP

hdu 3234 异或（加权并查集）
2015-11-21 01:01:15 来源: 作者: 【大 中 小】 浏览:1次
Tags：hdu 3234 异或 加权 查集
??

有n(n<=20000)个未知的整数X0,X1,X2Xn-1，有以下Q个(Q<=40000)操作：

I p v :告诉你Xp=v

I p q v :告诉你Xp Xor Xq=v

Q k p1 p2 … pk : 询问 Xp1 Xor Xp2 .. Xor Xpk， k不大于15。

如果当前的I跟之前的有冲突的话，跳出

思路就是并查集的扩展，每个节点表示他与根结点的异或值 。。。。思路略

ps：忘打了个.导致wa了好长时间............跪了

?

#include
  
     
#include
   
     #include
    
      #include
     
       #include
      
        #include
       
         #include
        
          #include
          #include
          
            #include
           
             #include
            
              #include
              #include
              
                using namespace std; #define LL long long const LL maxn = 20000 + 5; const LL INF = 1000000000; LL x[maxn]; LL pa[maxn], num[maxn], n;//num数组记录每个集合中的元素个数 void init() { //增加了一个xn，即零结点 for(LL i = 0; i <= n; i++) { pa[i] = i; x[i] = 0;} } LL find(LL id) { if(id != pa[id]) { LL tmp = pa[id]; LL root = find(pa[id]); x[id] ^= x[tmp]; return pa[id] = root; } else return id; } bool unio(LL p, LL q, LL v) { LL pap = find(p), paq = find(q); if(pap == paq) { return (x[p] ^ x[q]) == v; //注意运算符的顺序，如果不加括号会错，位运算一定要小心优先级 } if(pap == n) swap(pap, paq); pa[pap] = paq; x[pap] = x[p] ^ x[q] ^ v; // 最重要的一步，将两颗树连接在一起，很巧妙； return true; } int main() { //freopen("input.txt", "r", stdin); LL Q, kase = 1; while(scanf("%lld%lld", &n, &Q) && n) { init(); printf("Case %lld:\n", kase++); char cmd[2], str[20]; LL facts = 0; bool flag = true; for(LL i = 1; i <= Q; i++) { if(!flag){ gets(str); continue;} scanf("%s", cmd); if(cmd[0] == 'I') { facts++; gets(str); LL p, q, v; if(sscanf(str, "%lld%lld%lld", &p, &q, &v) == 2) { v = q; q = n; } if(!unio(p, q, v)) { printf("The first %lld facts are conflicting.\n", facts); flag = false; continue; } } else { LL k, idp[20], tag = 1; LL ans = 0; scanf("%lld", &k); for(LL i = 0; i < k; i++) { scanf("%lld", &idp[i]); num[find(idp[i])] = 0; } for(LL i = 0; i < k; i++) { num[find(idp[i])]++; ans ^= x[idp[i]]; } for(LL i = 0; i < k; i++) { if(num[find(idp[i])] % 2 == 1 && find(idp[i]) != n) { tag = 0; break; } } if(!tag) printf("I don't know.\n"); else printf("%lld\n", ans); } } printf("\n"); } return 0; }

?

?

?
【大 中 小】【打印】 【繁体】【投稿】【收藏】 【推荐】【举报】【评论】 【关闭】 【返回顶部】
分享到: 
上一篇：C++线索二叉树求最矮公共父亲节点 下一篇：C++插入排序之二路插入(环与非环..

评论

帐　　号: 密码: (新用户注册)
验 证 码:
表　　情:
内　　容: