题解：AcWing 239 奇偶游戏

本文分享的必刷题目是从蓝桥云课、洛谷、AcWing等知名刷题平台精心挑选而来并结合各平台提供的算法标签和难度等级进行了系统分类。题目涵盖了从基础到进阶的多种算法和数据结构旨在为不同阶段的编程学习者提供一条清晰、平稳的学习提升路径。欢迎大家订阅我的专栏算法题解C与Python实现附上汇总贴算法竞赛备考冲刺必刷题C | 汇总【题目来源】AcWing239. 奇偶游戏 - AcWing题库【题目描述】小A AA和小B BB在玩一个游戏。首先小A AA写了一个由0 00和1 11组成的序列S SS长度为N NN。然后小B BB向小A AA提出了M MM个问题。在每个问题中小B BB指定两个数l ll和r rr小A AA回答S [ l ∼ r ] S[l∼r]S[l∼r]中有奇数个1 11还是偶数个1 11。机智的小B BB发现小A AA有可能在撒谎。例如小A AA曾经回答过S [ 1 ∼ 3 ] S[1∼3]S[1∼3]中有奇数个1 11S [ 4 ∼ 6 ] S[4∼6]S[4∼6]中有偶数个1 11现在又回答S [ 1 ∼ 6 ] S[1∼6]S[1∼6]中有偶数个1 11显然这是自相矛盾的。请你帮助小B BB检查这M MM个答案并指出在至少多少个回答之后可以确定小A AA一定在撒谎。即求出一个最小的k kk使得01 0101序列S SS满足第1 ∼ k 1∼k1∼k个回答但不满足第1 ∼ k 1 1∼k11∼k1个回答。【输入】第一行包含一个整数N NN表示01 0101序列长度。第二行包含一个整数M MM表示问题数量。接下来M MM行每行包含一组问答两个整数l ll和r rr以及回答even或odd用以描述S [ l ∼ r ] S[l∼r]S[l∼r]中有偶数个1 11还是奇数个1 11。【输出】输出一个整数k kk表示01 0101序列满足第1 ∼ k 1∼k1∼k个回答但不满足第1 ∼ k 1 1∼k11∼k1个回答如果01 0101序列满足所有回答则输出问题总数量。【输入样例】10 5 1 2 even 3 4 odd 5 6 even 1 6 even 7 10 odd【输出样例】3【核心思想】问题分析给定长度为N NN的 01 序列和M MM个区间奇偶性回答区间[ l , r ] [l, r][l,r]中 1 的个数为偶数或奇数求前多少个回答自洽第几个回答开始出现矛盾。这是一个带权并查集问题关键在于将区间奇偶性约束转化为前缀和节点之间的异或关系。算法选择带权并查集Extended Union-Find维护每个节点到根节点的异或值奇偶性支持O ( α ( n ) ) O(\alpha(n))O(α(n))的合并与查询前缀和转化区间[ l , r ] [l, r][l,r]中 1 的个数的奇偶性等价于前缀和s u m [ r ] sum[r]sum[r]与s u m [ l − 1 ] sum[l-1]sum[l−1]的奇偶性差异即s u m [ r ] ⊕ s u m [ l − 1 ] t sum[r] \oplus sum[l-1] tsum[r]⊕sum[l−1]t离散化Hash/Map下标范围大需要映射为连续编号关键步骤前缀和建模设s u m [ i ] sum[i]sum[i]为前i ii项中 1 的个数的前缀和则区间[ l , r ] [l, r][l,r]中 1 的个数的奇偶性为s u m [ r ] ⊕ s u m [ l − 1 ] sum[r] \oplus sum[l-1]sum[r]⊕sum[l−1]离散化使用unordered_map将l − 1 l-1l−1和r rr映射为连续编号因为l − 1 l-1l−1和r rr的范围可能达到10 9 10^9109初始化带权并查集p[i] id[i] 0$每个节点独立到自身的异或值为 0带权查找路径压缩递归查找根节点u find(p[x])更新d[x] ^ d[p[x]]使d[x]表示x xx到根节点的异或值p[x] u路径压缩处理每个回答( a , b , t ) (a, b, t)(a,b,t)其中a l − 1 , b r a l-1, b ral−1,br若a aa和b bb在同一集合检查d[a] ^ d[b] t若不等则前i − 1 i-1i−1个回答自洽第i ii个矛盾记录答案并退出若不在同一集合合并p[pa] pb设置权值d[pa] d[a] ^ d[b] ^ t保证合并后a aa到b bb的异或值为t tt时间/空间复杂度时间复杂度O ( M ⋅ α ( N ) ) O(M \cdot \alpha(N))O(M⋅α(N))其中α \alphaα为阿克曼函数反函数近似常数。每次查找或合并操作均摊O ( α ( N ) ) O(\alpha(N))O(α(N))空间复杂度O ( N ) O(N)O(N)并查集父节点数组、权值数组和离散化映射表带权并查集的核心思想异或关系传递通过维护每个节点到根节点的异或值快速查询任意两节点间的奇偶性关系路径压缩更新权值在路径压缩时利用异或的传递性d[x] ^ d[p[x]]更新到根的距离合并时设置权值合并两个集合时通过d[pa] d[a] ^ d[b] ^ t保证新集合内所有异或关系一致前缀和降维将区间问题转化为两个端点的前缀和关系是处理区间奇偶性/异或约束的经典技巧适用于带奇偶性约束的连通性判断、异或方程组、博弈公平性问题【算法标签】#并查集【代码详解】#includebits/stdc.husingnamespacestd;constintN200005;// 最大节点数离散化后最多 2*M5 个节点intn,m;// n: 序列长度输入值但随后被重置用于离散化计数, m: 问题数量intp[N],d[N];// p: 并查集父节点数组; d[x]: 节点 x 到父节点路径上的奇偶性异或值unordered_mapint,intS;// 离散化映射原始下标 - 连续编号// 离散化将原始下标映射为连续编号从1开始intget(intx){if(S.count(x)0)S[x]n;// 若该值未出现过分配新编号n 从0递增returnS[x];// 返回该下标对应的编号}// 带权并查集查找路径压缩同时维护到根节点的奇偶性关系intfind(intx){if(p[x]!x){intufind(p[x]);// 递归查找根节点d[x]^d[p[x]];// 更新 x 到根节点的奇偶性d[x] d[x] ^ d[父节点]p[x]u;// 路径压缩将 x 直接指向根节点}returnp[x];// 返回根节点}intmain(){cinnm;// 读入序列长度 N 和问题数量 Mfor(inti1;iN;i)p[i]i;// 初始化并查集每个节点自成一个集合注意用输入的N而非nn0;// 重置 n用于离散化计数intresm;// 默认答案若所有回答都自洽则输出 mfor(inti1;im;i){inta,b;string type;cinabtype;// 读入区间 [a, b] 和回答类型aget(a-1),bget(b);// 离散化将前缀和节点 (a-1) 和 b 映射为编号intt0;// t 0 表示 even偶数个1t 1 表示 odd奇数个1if(typeodd)t1;intpafind(a),pbfind(b);// 查找 a 和 b 的根节点if(papb)// 若 a 和 b 已在同一集合{// 检查奇偶性是否矛盾d[a]^d[b] 表示区间 [a,b] 中1的个数的奇偶性if((d[a]^d[b])!t){resi-1;// 前 i-1 个回答自洽第 i 个回答导致矛盾break;// 找到矛盾提前退出}}else// 若 a 和 b 不在同一集合合并{p[pa]pb;// 将 pa 的根指向 pb 的根// 设置 pa 到 pb 的奇偶性关系d[pa] d[a] ^ d[b] ^ t// 保证合并后d[a] ^ d[b] t即区间 [a,b] 中1的个数奇偶性为 td[pa]d[a]^d[b]^t;}}coutresendl;// 输出最多自洽的回答数量return0;}【运行结果】10 5 1 2 even 3 4 odd 5 6 even 1 6 even 7 10 odd 3