2026 Codeforces Round 1093 (Div. 2)

A - Blocked

解题思路

如果有两个相同的数，怎么放都可以凑出相同子集
没有相同的数字，把数字从大到小排序，前缀中一定无法凑出答案

B - OIE Excursion

解题思路

如果有一段相同数字的区间，长度为，那么在这个区间上前进，经过的数字也会至少遍历一段连续的长度为的区间
所以当这个连续区间的长度为时，一定会被发现

C - Grid L

解题思路

的矩阵所用到的长度为
的总长度为
合法的需要满足：
注意力惊人：
即：
令 ，我们可以在 的复杂度内枚举 和 ，对每一对和中最多能容纳的型的数量进行合法性判断即可

D2 - Unique Values (Hard version)

解题思路

两个版本只有查询次数的不同，简单版本次，困难版本次。
每一次查询，会返回 询问下标集合中 只出现一次的数值的个数
设 出现了三次的数值为 ，当前查询的下标数量为，询问值为
如果 包含了一个 ,那么 为偶数 , 把奇数个数全部减去，只剩出现两次的偶数数值 。
如果 包含了两个 , 那么 为偶数 , 依旧把奇数个数全部减去，只剩出现两次的偶数数值 。
如果 包含了三个 ,那么 为奇数 , 依旧把出现一次的个数全部减去，只剩出现两次的偶数数值次的 。

使用二分 ，先找 右边位置 ，再找 左边位置 ，再在中查找中间的位置。

复杂度为 , 可以通过简单版本和复杂版本

E - Coloring a Red Black Tree

解题思路

答案的形成是一个特殊的黑点的选择顺序，不同的顺序对于同一个黑点涂红期望是不一样的
假设 总共有 个邻居（度数），其中有 个是红色的。
那么一次操作让 变红的概率
那么 变红的期望为

表示点 比 父亲先变红
表示点 比 父亲后变红

假设我们要计算点 的 。它有若干个孩子 。 每个孩子 也有两种选择：

• 孩子比 先红：贡献代价 。此时，这个孩子可以作为红色邻居帮 。
• 孩子比 后红：贡献代价 。此时，这个孩子帮不了 。

假设 选了 个孩子先变红：

• 情形 0 ( 先于父亲)： 的红色邻居数量 。 节点的代价 = 。
• 情形 1 ( 后于父亲)： 的红色邻居数量 （多了一个父亲）。 节点的代价 = 。

贪心策略： 为了总和最小，我们不仅要考虑 本身的代价 ，还要考虑孩子的代价。 每一个孩子如果是“先于 ”，代价是 ；如果是“后于 ”，代价是 。 两者的差值 代表了“让这个孩子先变红”能省下多少钱。

将孩子按照 的值从大到小进行排序，前缀和找到代价最小的一个边界，使前个孩子先变红