博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
【HDOJ】3234 Exclusive-OR
阅读量:6678 次
发布时间:2019-06-25

本文共 3498 字,大约阅读时间需要 11 分钟。

并查集。对于对元素赋值操作,更改为I p n v。令val[n]=0(任何数与0异或仍为原值)。

考虑fa[x] = fx, fa[y] = fy。
如果使得fa[fx] = fy, 那么val[fx] = TrueVal[fx] ^ TrueVal[fy] = (val[x] ^ TrueVal[x]) ^ (val[y] ^ TrueVal[y]) = (val[x] ^ val[y]) ^ (TrueVal[x] ^ TrueVal[y]) = val[x] ^ val[y] ^ z。
同时每次find时,也需要更新val(因为fa不同了)。
对于Query操作,有效的Query为cnt为偶数或者root为n。
输出样例有问题,每个case后有空行。

1 /* 3234 */  2 #include 
3 #include
4 #include
5 #include
6 #include
7 #include
8 #include
9 #include
10 #include
11 #include
12 #include
13 #include
14 #include
15 #include
16 #include
17 #include
18 #include
19 #include
20 #include
21 using namespace std; 22 //#pragma comment(linker,"/STACK:102400000,1024000") 23 24 #define sti set
25 #define stpii set
> 26 #define mpii map
27 #define vi vector
28 #define pii pair
29 #define vpii vector
> 30 #define rep(i, a, n) for (int i=a;i
=a;--i) 32 #define clr clear 33 #define pb push_back 34 #define mp make_pair 35 #define fir first 36 #define sec second 37 #define all(x) (x).begin(),(x).end() 38 #define SZ(x) ((int)(x).size()) 39 #define lson l, mid, rt<<1 40 #define rson mid+1, r, rt<<1|1 41 42 const int maxn = 2e4+5; 43 const int maxk = 20; 44 int fa[maxn], val[maxn]; 45 int P[maxk], K; 46 bool visit[maxk]; 47 int n; 48 49 int find(int x) { 50 if (fa[x] == x) 51 return x; 52 int tmp = fa[x]; 53 fa[x] = find(fa[x]); 54 val[x] ^= val[tmp]; 55 return fa[x]; 56 } 57 58 void init() { 59 rep(i, 0, n+1) { 60 val[i] = 0; 61 fa[i] = i; 62 } 63 } 64 65 bool merge(int u, int v, int x) { 66 int fu = find(u); 67 int fv = find(v); 68 69 if (fu == fv) { 70 return (val[u]^val[v]) == x; 71 } 72 73 if (fu == n) swap(fu, fv); 74 fa[fu] = fv; 75 val[fu] = val[u]^val[v]^x; 76 return true; 77 } 78 79 int Query() { 80 int f, c; 81 int ret = 0; 82 83 memset(visit, false, sizeof(visit)); 84 rep(i, 0, K) 85 find(P[i]); 86 rep(i, 0, K) { 87 if (visit[i]) 88 continue; 89 f = fa[P[i]]; 90 c = 0; 91 rep(j, i, K) { 92 if (!visit[j] && fa[P[j]]==f) { 93 ++c; 94 visit[j] = true; 95 ret ^= val[P[j]]; 96 } 97 } 98 if (f!=n && (c&1)) 99 return -1;100 }101 102 return ret;103 }104 105 int main() {106 ios::sync_with_stdio(false);107 #ifndef ONLINE_JUDGE108 freopen("data.in", "r", stdin);109 freopen("data.out", "w", stdout);110 #endif111 112 int q;113 int isn;114 int a[5], c;115 int u, v, x;116 int ans;117 char cmd[3], line[105];118 bool flag;119 int t = 0;120 121 while (scanf("%d %d", &n, &q)!=EOF && (n||q)) {122 printf("Case %d:\n", ++t);123 init();124 flag = true;125 isn = 0;126 while (q--) {127 scanf("%s%*c", cmd);128 if (cmd[0] == 'I') {129 gets(line);130 } else {131 scanf("%d", &K);132 rep(i, 0, K)133 scanf("%d", &P[i]);134 }135 if (!flag)136 continue;137 138 if (cmd[0] == 'I') {139 int len = strlen(line);140 141 ++isn;142 c = 0;143 a[c] = 0;144 rep(i, 0, len) {145 if (line[i] == ' ') {146 ++c;147 a[c] = 0;148 } else {149 a[c] = 10*a[c] + line[i]-'0';150 }151 }152 153 if (c == 1) {154 u = a[0];155 v = n;156 x = a[1];157 } else {158 u = a[0];159 v = a[1];160 x = a[2];161 }162 163 flag = merge(u, v, x);164 165 if (!flag) {166 printf("The first %d facts are conflicting.\n", isn);167 }168 } else {169 ans = Query();170 if (ans == -1) {171 puts("I don't know.");172 } else {173 printf("%d\n", ans);174 }175 }176 }177 178 putchar('\n');179 }180 181 #ifndef ONLINE_JUDGE182 printf("time = %d.\n", (int)clock());183 #endif184 185 return 0;186 }

 

转载于:https://www.cnblogs.com/bombe1013/p/4912782.html

你可能感兴趣的文章
window.open打开新页面,并将本页数据用过url传递到打开的页面;需要两个页面;...
查看>>
查看本机IP分为两种情况:
查看>>
Scala进阶之路-Scala特征类与unapply反向抽取
查看>>
洛谷P3057 [USACO12NOV]远处的牧场Distant Pastures
查看>>
hdu3415 Max Sum of Max-K-sub-sequence 单调队列
查看>>
6421B Lab2 DHCP的配置及故障排除
查看>>
[C# 基础知识梳理系列]专题一:深入解析委托——C#中为什么要引入委托
查看>>
FOSCommentBundle功能包:其它添加评论到页面的方法
查看>>
Exchange 2016共享邮箱不保存已发送邮件的问题
查看>>
[C#基础知识系列]全面解析C#中静态与非静态
查看>>
SQL Server 2012笔记分享-40:自动维护索引
查看>>
C/C++各种系统开发环境搭建
查看>>
Linq技术四:动态Linq技术 -- Linq.Expressions
查看>>
ARC __bridge modifiers demystified
查看>>
[转]HTML字符实体(Character Entities),转义字符串(Escape Sequence)
查看>>
真正的干货是什么?
查看>>
SharedPreference.Editor的apply和commit方法异同
查看>>
linux shell “(())” 双括号运算符使用
查看>>
http://code.662p.com/view/5141.html
查看>>
C C++ OC指针常量和常量指针区别
查看>>