题目链接:uva 12232 - Exclusive-OR
题目大意:有n个数,一开始并不知道具体的值,现在进行Q次操作。
- I u k:au的值为k
- I u v k:au⨁av=k
- Q kq1q2…qk:求q1⨁q2…⨁qk
对于Q操作不能确定的话输出"I don't know."
对于I操作矛盾的话则输出是第几条I操作出现矛盾的,并且停止后面所有的操作。
解题思路:加权并查集,f[x]表示x节点父亲节点,d[x]表示x节点与其父节点的亦或值,对于确定的节点值,可以将父亲节点设为0,这样的话在合并操作的时候就要注意,如果有一段0是父亲节点的话,就要将令一个节点指向0节点(也就是说0节点是固定不能有父亲节点的),一是在指向0节点的联通集合是确定值的,在查询是需要特判,二是进行第一种操作的时候方便处理。
在查询时,需要将所有的数分成各个联通集合,如果存在联通集合的个数为奇数,并且根节点不为0的话就是不能确定值的,否则取所有节点与父亲节点的亦或值的亦或和即可。
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn = 20005;
const int maxm = 105;
bool flag;
int N, Q, f[maxn], d[maxn];
int getfar (int x) {
if (x == f[x])
return x;
int tmp = f[x];
f[x] = getfar(f[x]);
d[x] ^= d[tmp];
return f[x];
}
void query () {
int n, ret = 0, num[maxm], vis[maxm];
memset(vis, 0, sizeof(vis));
scanf("%d", &n);
for (int i = 0; i < n; i++) {
scanf("%d", &num[i]);
num[i]++;
}
if (flag)
return;
for (int i = 0; i < n; i++) {
int root = getfar(num[i]), cnt = 1;
if (root == 0 || vis[i])
continue;
for (int j = i+1; j < n; j++) {
if (getfar(num[j]) == root) {
cnt++;
vis[j] = 1;
}
}
if (cnt&1) {
printf("I don't know.\n");
return ;
}
}
for (int i = 0; i < n; i++)
ret ^= d[num[i]];
printf("%d\n", ret);
}
bool link () {
char s[maxm];
gets(s);
int u, v, k;
int type = sscanf(s, "%d%d%d", &u, &v, &k);
u++;
if (type == 2) {
k = v;
v = 0;
} else
v++;
int p = getfar(u);
int q = getfar(v);
if (p == 0)
swap(p, q);
if (p != q) {
f[p] = q;
d[p] = d[u]^d[v]^k;
} else
return (d[u]^d[v]) != k;
return false;
}
int main () {
int cas = 1;
while (~scanf("%d%d", &N, &Q) && N) {
printf("Case %d:\n", cas++);
flag = false;
memset(d, 0, sizeof(d));
for (int i = 0; i <= N; i++)
f[i] = i;
int ti = 0, u, v;
char s[maxm];
for (int i = 0; i < Q; i++) {
scanf("%s", s);
if (s[0] == 'I') {
ti++;
if (link()) {
flag = true;
printf("The first %d facts are conflicting.\n", ti);
}
} else if (s[0] == 'Q')
query();
}
printf("\n");
}
return 0;
}
分享到:
相关推荐
使用 RabbitMQ 和 Spring Integration(Java DSL) 串行处理消息如果您需要使用 RabbitMQ 串行处理消息,并使用一组侦听器处理消息,我见过的最好方法是在每个侦听器上使用 1 个线程处理消息的侦听器上使用标志。...
range-exclusive 生成步长为d的数字[a, b)的封闭范围安装npm install range-exclusive用法var rangeExclusive = require ( 'range-exclusive' )rangeExclusive ( 10 ) // [1, 2, 3, 4, 5, 6, 7, 8, 9]rangeExclusive...
npm install exclusive-or --save 用 var xor = require ( 'exclusive-or' ) ; xor ( false , false ) // -> false xor ( false , true ) // -> true xor ( true , false ) // -> true xor ( true , true ) // -> ...
Activiti 学习笔记八:排他网关(ExclusiveGateWay)
一个进程可以从 zookeeper 获取锁,并立即进入 GC 暂停/从网络分区。 如果另一个进程接管了这个锁,当原来的进程被唤醒时,它仍然会认为它有锁并且可以写表。 它最终会被通知它不再拥有锁,但到那时它可能已经写入...
吉诺独家登陆页面 按照以下URL来查看该网站
火花专用套装在此阶段,我们正在演示如何在本地运行。 此版本的程序计数带有a的行和带有b的行。 此应用程序需要一个参数,该参数是要处理的文件的路径。
The TIS Committe grants you a non-exclusive, worldwide, royalty-free license to use the information disclosed in the Specification to make your software TIS-compliant; no other license, express or ...
Legal Lines and Disclaimers Intel technologies’ features and benefits depend on system configuration and may require enabled hardware, software or service activation. Learn more at Intel.com, or from...
This EULA is a non-exclusive and non-transferable license and grants you the following rights: Systems Software - You may install and use one copy of the SOFTWARE PRODUCT on a single Computer at a ...
OpenWrt18.06-X86-64最新版云编译项目固件来源: P3TERX云编译脚本地址: : lean固件源码地址: : project-openwrt固件源码地址: : 由衷感谢所有为openwrt无私奉献的大佬们。... 稳定版云编译项目: :
KHI hereby offers you a non-exclusive license on the terms set out in this Agreement. You should carefully read these terms and conditions BEFORE opening the case that contains the Software or ...
#系统独家 安装服务器端依赖项: npm install 安装前端库/框架: bower install 运行服务器以进行本地开发: gulp serve或gulp 网站网址: : ##笔记 ###### Sysex系统独占 ###数据库结构 ...
contractual disputes or claims) shall be governed by and construed in accordance with English law and submitted to the non-exclusive jurisdiction of the English courts. 7. GENERAL - If any part of ...
1. Subject to the provisions set out below, ARM hereby grants to you a perpetual, non-exclusive, nontransferable, royalty free, worldwide licence to use this ARM Architecture Reference Manual for the ...
ACALL - Absolute Call ADD, ADDC - Add Accumulator (With Carry) AJMP - Absolute Jump ANL - Bitwise AND CJNE - Compare and Jump if Not Equal ...XRL - Bitwise Exclusive OR Undefined - Undefined Instruction
一款低功耗 的2输入4异或门 5486/DM5486/DM7486 Quad 2-Input Exclusive-OR Gates
exclusive, non- transferable, revocable, non-sublicensable, fully-paid-up copyright license to reproduce, copy and redistribute the MTConnect® Specification, provided that you may only copy or ...
Siemens grants you the non-exclusive, non-sublicensable and non-transferable right to have the application examples used by technically trained personnel. Any change to the application examples is ...
Siemens grants you the non-exclusive, non-sublicensable and non-transferable right to have the application examples used by technically trained personnel. Any change to the application examples is ...