这个奇偶关系太BT了

要记录每个结点是否的父结点同奇同偶

然后每次路径压缩的时候都要更新

每次合并的时候也要更新

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

Accepted 有效得分：100 有效耗时：0ms

无语了，真要感谢这道题目，打了那么多次并查集，居然第一次发现union的时候没注意到两个相等的情况.......

日，遇到vijos sunny 结果一直running。。。

同样的程序交到puppy里直接秒出。。。

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

仔细 + 离散 + 数组开大点 = AC

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案错误...　├ 标准行输出

　├ 错误行输出

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案错误...　├ 标准行输出

　├ 错误行输出

---|---|---|---|---|---|---|---|-

Unaccepted 有效得分：80 有效耗时：0ms

该死的小错误，叫人头痛...........

怎么改得赢啊.........

我是hash+并查集.........

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

离散化预处理+并查集

由于题目给出的范围有 10^9 所以直接并查集会unac(只有70-80分)，所以离散,

先全部读入 然后quicksort,

在并查集操作时用原数在排完序的编号代替原数(注意用二分查找，还要判重)，

于是AC!

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

膜拜大牛 +1

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：运行时错误...|错误号: 128

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：运行时错误...|错误号: 128

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：运行时错误...|错误号: 128

---|---|---|---|---|---|---|---|-

Unaccepted 有效得分：70 有效耗时：0ms

有了食物链的教训

一次AC。

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

膜拜大牛

如对本题有疑问可以参看我的题解：http://xujieqi.blog.hexun.com/35722312_d.html

囧。。没秒杀，9msAC

......为什这种题要离散化。。。害我敲了20分钟，不过一次AC

读入数列长度有用吗？

我直接一个readln无视掉它。

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

pascal的循环变量

并查集

Father[i] 表示i的父亲

附加一个信息 Equ[i] 表示i和i父亲 奇偶性是否相同(0同1异)

那么:

int getfather(int w)

{

if(w==Father[w])

return w;

else

{

int t=getfather(Father[w]);

Equ[w]^=Equ[Father[w]];

return Father[w]=t;

}

}

更改祖先:

Father[FB]=FA;

Equ[FB]=A3[i]^Equ[A1[i]]^Equ[A2[i]];

Accepted 有效得分：100 有效耗时：0ms

好快啊！

离散化+并查集+路经压缩

这是ural 1003.

ural的数据貌似更强悍..我的程序在这0ms AC,用ural的数据一测只有60分.

让人豁然开朗的并查集

程序很简洁,思想不简单

我们用sum[i]表示1到i之间1的个数。对于一个区间(a,b),如果1个个数是奇数，则说明sum与sum[a-1]奇偶性不同，否则相同。我们将有联系的sum[i]并到一个集合中，并记录与其代表元素的奇偶性关系。如果中途出现矛盾，则输出出现矛盾的位置减一。由于n很大，所以不能简单用数组实现并查集，我们可以建一个Hash来解决此问题。