acwing 239. 奇偶游戏 并查集
等风 人气:0地址 https://www.acwing.com/problem/content/241/
小A和小B在玩一个游戏。
首先,小A写了一个由0和1组成的序列S,长度为N。
然后,小B向小A提出了M个问题。
在每个问题中,小B指定两个数 l 和 r,小A回答 S[l~r] 中有奇数个1还是偶数个1。
机智的小B发现小A有可能在撒谎。
例如,小A曾经回答过 S[1~3] 中有奇数个1, S[4~6] 中有偶数个1,现在又回答 S[1~6] 中有偶数个1,显然这是自相矛盾的。
请你帮助小B检查这M个答案,并指出在至少多少个回答之后可以确定小A一定在撒谎。
即求出一个最小的k,使得01序列S满足第1~k个回答,但不满足第1~k+1个回答。
输入格式
第一行包含一个整数N,表示01序列长度。
第二行包含一个整数M,表示问题数量。
接下来M行,每行包含一组问答:两个整数l和r,以及回答“even”或“odd”,用以描述S[l~r] 中有奇数个1还是偶数个1。
输出格式
输出一个整数k,表示01序列满足第1~k个回答,但不满足第1~k+1个回答,如果01序列满足所有回答,则输出问题总数量。
数据范围 N≤10^9,M≤10000 输入样例: 10 5 1 2 even 3 4 odd 5 6 even 1 6 even 7 10 odd 输出样例: 3
解答1:
带权并查集
本题目有两个难点
1 数据范围过大 有 10^9
2 询问的内容如何转化到并查集
问题1 的解决办法是 使用离散化 将不同的数据映射到1 2 3 4。。。,由于只有10000次 询问,每次询问提供两个数据 所以只要提供10000*2的数据范围即可
问题2 的解决办法是 前缀和 如果提供 l和r的范围内1有奇数个还是偶数个 也就是计算 前缀和 sum[r] - sum[l-1]
另由于有偶数减偶数 奇数减奇数 都是偶数 只有两者不同类型分别是奇数偶数中的一种 才会出现最后的差是奇数
那么并查集其实也就是
加载全部内容