程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> hdu 3234 Exclusive-OR （並查集+異或性質）

hdu 3234 Exclusive-OR （並查集+異或性質）

編輯：C++入門知識

hdu 3234 Exclusive-OR （並查集+異或性質）

Exclusive-OR

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 2177 Accepted Submission(s): 603

Problem Description You are not given n non-negative integers X₀, X₁, ..., X_n-1 less than 2²⁰ , but they do exist, and their values never change.

I'll gradually provide you some facts about them, and ask you some questions.

There are two kinds of facts, plus one kind of question:

Input There will be at most 10 test cases. Each case begins with two integers n and Q (1 <= n <= 20,000, 2 <= Q <= 40,000). Each of the following lines contains either a fact or a question, fZ喎?http://www.Bkjia.com/kf/ware/vc/" target="_blank" class="keylink">vcm1hdHRlZCBhcyBzdGF0ZWQgYWJvdmUuIFRoZQo8ZW0+azwvZW0+IHBhcmFtZXRlciBpbiB0aGUgcXVlc3Rpb25zIHdpbGwgYmUgYSBwb3NpdGl2ZSBpbnRlZ2VyIG5vdCBncmVhdGVyIHRoYW4gMTUsIGFuZCB0aGUKPGVtPnY8L2VtPiBwYXJhbWV0ZXIgaW4gdGhlIGZhY3RzIHdpbGwgYmUgYSBub24tbmVnYXRpdmUgaW50ZWdlciBsZXNzIHRoYW4gMjxzdXA+MjA8L3N1cD4uIFRoZSBsYXN0IGNhc2UgaXMgZm9sbG93ZWQgYnkKPGVtPm49UT0wPC9lbT4sIHdoaWNoIHNob3VsZCBub3QgYmUgcHJvY2Vzc2VkLgogCjxicj4KT3V0cHV0CkZvciBlYWNoIHRlc3QgY2FzZSwgcHJpbnQgdGhlIGNhc2UgbnVtYmVyIG9uIGl0cyBvd24gbGluZSwgdGhlbiB0aGUgYW5zd2Vycywgb25lIG9uIGVhY2ggb25lLiBJZiB5b3UgY2Fu"t deduce the answer for a particular question, from the facts I provide you before that question, print "I don't know.", without quotes. If the i-th fact (don't count questions) cannot be consistent with all the facts before that, print "The first i facts are conflicting.", then keep silence for everything after that (including facts and questions). Print a blank line after the output of each test case.

Sample Input

Sample Output

Case 1:
I don't know.
3
1
2
Case 2:
4
Case 3:
7
The first 2 facts are conflicting.

Source 2009 Asia Wuhan Regional Contest Hosted by Wuhan University

題意：

有n(n<=20000)個未知的整數X0,X1,X2Xn-1，有以下Q個(Q<=40000)操作：
I p v :告訴你Xp=v
I p q v :告訴你Xp ^ Xq=v
Q k p1 p2 … pk : 詢問 Xp1 Xor Xp2 .. Xor Xpk， k不大於15。
如果當前的I跟之前的有沖突的話，跳出

思路：

並查集，每個節點記錄與根節點的異或偏移量，一個集合內如果有一個知道值了的話，這個集合裡面都能知道值，（可以標記根是否已經得到值，或者像網上大部分人的做法，虛擬出一個節點n，值為0，將I操作統一）查詢時，如果一個未知集合出現了偶數個，那麼可以得到其值，u^root^v^root=u^v，如果出現奇數次，那麼不能得到。Merge的時候有個小坑，見代碼。

代碼：

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include
#define maxn 20005
#define MAXN 100005
#define mod 100000000
#define INF 0x3f3f3f3f
#define pi acos(-1.0)
#define eps 1e-8
typedef long long ll;
using namespace std;

int n,m,ans,cnt,tot,flag;
int pre[maxn],px[maxn],val[maxn],vis[maxn];
vectorroot,q[16];
char s[5],buff[100];

int Find(int x)
{
    if(x==pre[x]) return x;
    int r=pre[x];
    pre[x]=Find(pre[x]);
    px[x]=px[r]^px[x];
    return pre[x];
}
bool Merge(int u,int v,int w)
{
    int x=Find(u),y=Find(v);
    if(x!=y)
    {
        if(vis[x]||vis[y])// 如果有集合知道值 必須以知道值集合的根為根
        {
            if(!vis[y]) swap(x,y);
        }
        pre[x]=y;
        px[x]=w^px[u]^px[v];
    }
    else
    {
        if((px[u]^px[v])!=w) return false ;
    }
    return true ;
}
void update()
{
    int u,v,w;
    cnt++;
    gets(buff);
    stringstream si;
    si.clear(); si.str(buff);
    si>>u; si>>v;
    if(si>>w)
    {
        u++,v++;
        if(flag) return ;
        if(!Merge(u,v,w))
        {
            flag=1;
            printf("The first %d facts are conflicting.\n",cnt);
        }
    }
    else
    {
        if(flag) return ;
        u++;
        int r=Find(u);
        if(vis[r])
        {
            if(val[r]!=(v^px[u]))
            {
                flag=1;
                printf("The first %d facts are conflicting.\n",cnt);
            }
        }
        else
        {
            vis[r]=1;
            val[r]=v^px[u];
        }
    }
}
void query()
{
    int i,j,u,v,k,r,flg;
    scanf("%d",&k);
    root.clear();
    for(i=0;i