企业应如何进行网站建设,零基础学wordpress pdf下载,软件app开发培训,受欢迎的邢台做网站题目
小 A 和小 B 在玩一个游戏。
首先#xff0c;小 A 写了一个由 0 和 1 组成的序列 S#xff0c;长度为 N。
然后#xff0c;小 B 向小 A 提出了 M 个问题。
在每个问题中#xff0c;小 B 指定两个数 l 和 r#xff0c;小 A 回答 S[l∼r] 中有奇数个 1 还是偶数个 …题目
小 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] 中有奇数个 1S[4∼6] 中有偶数个 1现在又回答 S[1∼6] 中有偶数个 1显然这是自相矛盾的。
请你帮助小 B 检查这 M 个答案并指出在至少多少个回答之后可以确定小 A 一定在撒谎。
即求出一个最小的 k使得 01 序列 S 满足第 1∼k 个回答但不满足第 1∼k1 个回答。
输入格式
第一行包含一个整数 N表示 0101 序列长度。
第二行包含一个整数 M表示问题数量。
接下来 M 行每行包含一组问答两个整数 l 和 r以及回答 even 或 odd用以描述 S[l∼r] 中有偶数个 1 还是奇数个 1。
输出格式
输出一个整数 k表示 01 序列满足第 1∼k 个回答但不满足第 1∼k1 个回答如果 01 序列满足所有回答则输出问题总数量。
数据范围
N≤10^9,M≤5000
思路
这道题与银河英雄传说思路是相似的。
我们可以想象为L到R的距离是奇数还是偶数R为根节点。
两个集合合并的时候使得其中一个集合S1的祖先节点排到另一个集合S2的末尾S1中所有的点到根节点的距离加上S1祖先节点到S2祖先节点的距离%2。
代码
#includebits/stdc.h
using namespace std;
const int N 20010;
int n,m;
int p[N],d[N];
unordered_mapint,int S;int get(int x)
{if(S.count(x) 0) S[x] n;return S[x];
}int find(int x)
{if(p[x] ! x){int root find(p[x]);d[x] ^ d[p[x]];p[x] root;}return p[x];
}int main()
{cin n m;n 0;for(int i 0; i N; i ) p[i] i;int res m;for(int i 1; i m; i ){int a,b;string type;cin a b type;a get(a - 1), b get(b);int t 0;if(type odd) t 1;int pa find(a),pb find(b);if(pa pb){if((d[a] ^ d[b] ! t)){res i - 1;break;}}else{p[pa] pb;d[pa] d[a] ^ d[b] ^ t;}}cout res endl;return 0;
}
