2026 Codeforces Round 1091 (Div. 2)

A - The Equalizer

解题思路

Shaunak先手，当总操作数为奇数时，不需要特殊操作就可以获胜
使用特殊操作后，切换为Yash先手，当总操作数为偶数时Shaunak获胜

B - Flip the Bit (Easy Version)

解题思路

由于简单版本的K值只有一个，把整个数组分为两部分
在某一侧的操作按照01的连续段处理，由于[L,R]的选择可以两边一起处理
所以最终答案为左右两边操作数的最大值

C - Grid Covering

解题思路

首先如果gcd(n,a)!=1 或者 gcd(m,b)!=1,就会形成周期性的跳跃，有的点始终被跳过去

在满足上述条件的情况下，横坐标 x 和纵坐标 y 实际上可以简化为步数 k 次的函数。所有到达的格子 ( x , y ) 必须满足
x = ka (mod n) && y = kb (mod m)
或者
x = ka (mod n) && y = (k+1) b (mod m)
根据中国剩余定理得出结论，gcd(n,m)>2 时无解
综上：本题只需要三个条件:gcd(n,a)==1 && gcd(m,b)==1 && gcd(n,m)<=2

D - Flip the Bit (HARD Version)

解题思路

困难版本 K >= 1 , 存在多个特殊下标
0...p1...p2...p3...pk...n+1
我们根据特殊下标，把数组分为 k + 1 个 区间
需要把每一个区间中 不等于 a[pk] 的 连续段全部翻转为 a[pk]
每一个区间 中 相邻位置不相等的位置 的数量为 ci ， 总数sum = c1+c2+..c k+1, 区间最大值为maxx = max(ci)

如果maxx < sum/2 ，可以 两两 进行相互抵消 最终的结果为sum/2
如果maxx > sum/2 ，最大区间匹配了sum-maxx 个连续段 , 最大区间还剩 maxx-(sum-maxx) 个连续段 , 总共 有 maxx 操作
最后的结果为 max(sum/2,maxx)

E - Definitely Larger

解题思路

i 的可支配数 j 有三个限制条件：
1.下标 j > i
2. Pj > Pi
3. Qj > Qi

P排列是给出的，我们可以知道对于每一个下标 i，j > i 且 在排列 P 中 满足 Pj > Pi 的 下标 j 的数量 sum
给出了D数组
如果 sum < D i , 表明 对于 下标 i , 所有合法的 j 都打不到Di的要求，只能输出 -1
如果 sum >= Di , 令 cnt = Di - sum , 也就是 当前 下标 i 需要在 第 cnt 个 下标 j (j > i && Pj > Pi) 后面 插入 ,使用链表即可