异或和大小比较类问题——抓住最高位：CF1863F
异或和大小比较类问题——抓住最高位：CF1863F
本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132629186
https://codeforces.com/contest/1863/problem/F
-
因为有等于，所以考虑异或和为0的合法区间，它可以随意切
-
现在考虑切开后左边大于右边，可以发现左右边最高位可以互相抵消，似乎不太可做？
-
此时可以换个考虑，考虑大区间的异或和的最高位，这一位在左右两个区间 恰好 有一位为1，而为1的那个区间就是转移到的区间
-
然后考虑下图，对于 ，可以转移到的要么以 开头，要么以 结尾。所以其实只需要判断 开头和 结尾的更大区间是否存在一个合法区间满足最高位恰好存在于当前这个区间里面。代码就是：
if((l[i]|r[j])&nx)
相似套路题目：
- GYM104420D
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来源 zhangxixi的博客！
相关推荐
2023-10-17
本质不同01序列DP方法
本质不同01序列dp方法 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/133885358 设 ggg 为本质不同方案， f0/1f_{0/1}f0/1 为以0/1结尾本质不同子序列的方案。假设遇到数字 iii fi′=gg′=2g−fif'_i=g\\g'=2g-f_i fi′=gg′=2g−fi 第一条式子： 对于原先每种情况都可以接或不接 iii ，不会重复，因为我们钦定必须加（ ggg 中包含空集， fff 中不含） 第二条...
2021-12-01
【Loj #10104. 「一本通 3.6 练习 5」Blockade】题解
本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15629936.html 题目链接 首先这个点删去之后必然与剩下 n−1n-1n−1 个点失去相连。 如果这个点能使其它点失去相连，说明这个点为割点。 然后统计一下每个儿子与父亲的影响即可。 Code 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666...
2023-09-27
博弈论（奇偶考虑法）+计数+DP（判定转DP）：CF838C
博弈论（奇偶考虑法）+计数+DP（判定转dp）：CF838C 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/133362167 首先题目有博弈，先分析一波最优策略（步骤：分析性质）。 两个人，所以显然考虑奇偶考虑法+递归考虑。 首先删就是使子问题-1，重新排列是在当前子问题里的。 一个串的排列是有限的，所以这里就可以上奇偶考虑法。如果有偶数种串，则必然是后手先“被迫“进入子问题（要算上初始情况） 考虑假设法：我们可以先假设进入子问题： 必赢。先手进！ ...
2021-12-24
【CF4D Mysterious Present】题解
本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15728574.html 题目链接 题目 Peter decided to wish happy birthday to his friend from Australia and send him a card. To make his present more mysterious, he decided to make a chain. Chain here is such a sequence of envelopes A A A = {...
2024-09-11
[SCOI2014] 方伯伯的玉米田（DP+树状数组维护行列）
[SCOI2014] 方伯伯的玉米田（dp+树状数组维护行列） 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/142137107 https://www.luogu.com.cn/problem/P3287 显然每次操作的区间一定是一个后缀 我们直接令 dp(x,i)dp(x,i)dp(x,i) 表示最后一个数是 xxx （加之后），加了 iii 次的最长长度，转移显然 maxdp(y≤x,j≤i)\max dp(y\le x, j\le i)maxdp(...
2023-10-17
本质子序列个数
本质子序列个数 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/133885848 fif_ifi 设为 iii 结尾的方案数 假设每次遇到 kkk fk=∑fi+1f_k=\sum f_i+1fk=∑fi+1 之前的所有情况和空集都可以接 kkk 可以结合矩阵进行一些奇奇怪怪的操作