AcWing239. 奇偶游戏
思路
小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序列满足第1k个回答，但不满足第1k+1个回答，如果01序列满足所有回答，则输出问题总数量。
数据范围
N≤109,M≤10000
代码
#include<iostream> #include<cstdio> #include<queue> #include<string> #include<cstring> #include<map> #include<vector> #include<set> #include<stack> #include<algorithm> #include<vector> #include<utility> #include<deque> #include<unordered_map> #define INF 0x3f3f3f3f #define mod 1000000007 #define endl '\n' #define eps 1e-6 inline int gcd(int a, int b) { return b ? gcd(b, a % b) : a; } inline int lowbit(int x) { return x & -x; } using namespace std; typedef long long LL; typedef unsigned long long ULL; typedef pair<int, int> PII; const int N = 20050; unordered_map<int, int>s; int n, m; int p[N], d[N]; int get(int x) { if (s.count(x) == 0)s[x] = ++n; return s[x]; } int Find(int x) { if (x != p[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 = 1;i < N;++i)p[i] = i; int res = m; for (int i = 1;i <= m;++i) { int a, b; string op; cin >> a >> b >> op; a = get(a - 1), b = get(b); int t = 0; //偶数 if (op == "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; }
![[PiKaChu靶场通关]文件包含file include](https://ucc.alicdn.com/pic/developer-ecology/6027bca0148748a788d7813fa3d14497.png?x-oss-process=image/format,webp/resize,h_160,m_lfit)
