202611 杂题选做

CF1693D

感觉是 tricky 的题目。

首先考虑一个序列的判定怎么做。

可以考虑 dp。可以记录一下下降的最小值和上升的最大值。

然后你发现最后一个元素一定是上升或者下降,因此一个维度可以优化成一个 变量。

然后你发现,固定上一个元素是下降,那么上升的最后一个元素是越小越好。因此我们记录这个即可。

然后此时想了半天如何双指针维护这个区间,在不合法的情况下如何判断要删掉哪些元素并且得到最后的状态。

然后发现,好像你直接维护就可以了?

具体的,考虑扫描线维护从每个左端点开始的状态,转移分成两种,不妨假设 。

  • 对于上一个元素是上升的情况。
    • 状态可以保留。
    • 同时考虑从上一个是下降的情况转移过来,此时下降的最小元素就是上一个元素。对这个 chkmin 即可。
  • 对于上一个元素是下降的情况。
    • 状态必须要清空,因为此时不能加入作为下降。
    • 考虑从上一个是上升的情况转移过来。此时上升的最大元素就是上一个元素。chkmin 即可。

可以线段树维护,不过没必要。

实际上似乎单调栈就行了。

CF2284D The Theorem of Two Cans

到底是谁在会通信啊。

首先操作不考虑连通性,我们考虑一种最简单的连通图,考虑树的情况。

你发现树的情况必然会连上一条边。

相当于你加入一条边,形成了一个环,然后断开环上的一条边。

你会发现,由于路径长度一定是奇数,因此环肯定是偶环。

因此根节点到一个点的路径如果经过了断开的那个边,那么可以从环上另一侧绕过去。

由于环是偶环,因此从两侧绕的路径奇偶性相同。

而我们发现其余点的个数恰好是 个,因此我们可以考虑用根节点到其他点路径的奇偶性来编码这个字符串。

不过有一个问题。如果有一个点的深度是偶数,那么至少要有一个深度是奇数的点。

如果全是 就爆炸了。

考虑 的树,通过这个操作划分出的等价类一共只有 个,不够编码所有字符串。

因此一定存在一张图无法通过此操作到达树。

我们考虑继续延展我们树上的结论。

考虑一张图上的情况。假设有一条 到 的路径经过了另一条边,那么从另一侧绕也不会改变奇偶性。

换句话说,假设 到 同时又奇数和偶数路径,那么无论怎么操作,都永远会有奇数和偶数路径。

因此你编码一个奇环进去即可。

T488126 悲伤记忆树

性质题。

首先你观察一些性质。首先考虑 是什么情况。

有两种情况。如果整个子树和已经是 了,那么操作一次 就做完了。

否则如果子树大小是偶数,那么操作两次 也做完了。

如果子树大小是奇数,我们希望根节点为 。

继续观察,发现操作奇数大小的点是没有意义的。

我们发现一个性质,就是如果一个点的祖先被操作了,那么之后操作这个点是没有意义的。

因为如果是偶数,那么子树和已经是 了,并不会造成改变。

因此你的操作一定是自底向上的。

考虑值域并不是很大,因此我们可以直接 表示节点 子树和是 的最小代价,枚举是否操作做转移。

但是不足以通过最后一个 sub。

我们考虑继续优化。我们发现,如果一个点的祖先被操作了,那么操作这个点本身就是没有意义的。

因为最后的结果都是祖先节点异或和变成 了,不操作,直接操作祖先,最后对根节点的贡献是一样的。

因此,我们选出的节点一定没有祖先后代关系。

换言之,子树是不交的。此时我们可以考虑转 DFS 序然后做序列 dp。

每个点要么选择转移到 ,要么不选转移到 。

复杂度就是 ,就对了。

此 trick 在 QOJ10922 亦有记载。

简单来说,只关心祖先信息的情况可以考虑转 DFN,代价可能是要记录所有祖先的状态。不过这个题目要求祖先全不选,而 QOJ10922 本身就要状压祖先信息。所以这样可以得到一个更加优秀的复杂度。

TopCoder 10902

考察暴力。

对于 Subtask 1,枚举所有情况直接模拟即可。

Sub2 不知道有啥用。

Sub3 的实际要求是不存在一个电影其处理时间大于另一个队列里初始的所有时间,然后显然只需要关心最大值即可。

考虑这个题目怎么做。实际上数据范围有些暧昧,看上去 可以折半,或者是一个比较大的多项之做法。

考虑什么分配是合法的。

假设分成了 和 两组。

那么对于每个 必须要满足在处理完这个电影之前,另一个队列没有处理完所有自己的电影和 之前的电影。

也就是

对于另一个队列同理。

这个式子看上去不太友好。

我们继续推一下。令 ,那么右侧是 。

整理一下。

这个式子。两侧都只和 有关,看上去很有用。

可是本质上你发现其实没啥用。因为你需要 和 都满足才可以。

你可以暴力 DP 记录这四个状态,应该是可以得到一个 或者可能更高复杂度的做法。然后什么都过不了。

值得一提的是,如果你折半的话,最后可以转化成一个四维偏序,然后值域不大,做一个四维前缀和也可以达到这个复杂度。

不过对正解没什么帮助。

我们考虑下面这件事情。首先一定存在一个队列先完成自己的所有任务。此时这个队列不可能出现不合法的位置。

考虑把我们的两个判定写下来。

和

我们做一个我们把左侧扩展到整个集合,如果此时可以满足那么原式子肯定可以满足。

和

然后你发现,

和反过来的情况至少有一个会出现。因此你就可以在大脑宕机的情况下发现这个性质了。

因此,如果不合法,最多只有一个队列不合法。

因此只需要对两个队列都做一遍 dp 即可。

SGU 385

这我想不到?????

在所有错排中均匀随机,计算最大置换环乘上最大置换环个数的期望。

首先我们考虑直接枚举最大置换环,枚举个数。

这部分是 的。但是难点在于同时维护长度为 且所有置换环长度不超过 的排列。

你发现你无法避免枚举环的个数,因而难以避免带个 的复杂度。

我们考虑换个角度。

考虑期望的线性性。我们拆到每个元素上。

我们考虑把一个错排的 和 抽出来在交换就可以得到一个 在最大环上的情况和 在最大环上情况的双射,因此每个元素的期望是相同的。

我们考虑算一下 即可。

首先考虑如何计数。直接代表元,枚举 所在环的大小即可。

简单的推式子。

后面是容易的。不过你发现这样不好处理精度问题。我们考虑换个角度。

考虑计算概率,也就是满足条件的排列除以总排列个数的情况。

实际上在所有错排中均匀随机性质有点差。因为错排没有很好的封闭形式。不过错排的概率是容易计算的。可以直接递推。

首先错排个数递推有

解释是如果考虑 放在 ,如果 放在 那么剩下的是一个长度是 的错排。如果不是 ,那么我们让 变成新的 ,后面往前挪,然后就可以递推了。

不过这个递推没啥用。

我们考虑 所在的环长度为 的概率。

答案是

然后上面剩下 然后约掉就是 。

居然无关吗。

那么这个就好办了。你直接枚举环大小,然后让剩下的形成错排即可。

然后枚举长度,求出 所在环长度是 的概率。这里是 。然后乘上剩下环长度小于等于 的概率。

我们还需要维护长度为 且所有环长度小于等于 的概率。

这个也是容易的,枚举环长度,让剩下的也小于等于 ,乘上 。然后前缀和优化即可。

以上。

G100078F Formula

牛逼。

首先考虑真值表。

然后考虑 formalize 一下,我们用 De Morgan 把所有的取反都拆进去。首先拆掉之后还是满足条件的公式。

然后你发现取反就只可能出现在单个变量之前,并且每个变量只会出现一次。

然后考察这棵树的性质。

其实本质上就只有这一个性质:

考虑一颗子树,固定子树外所有变量的取值,假设子树内的表达式是 ,考虑最后整个表达式的取值,只有如下四种情况:

  • 恒定为 。
  • 恒定为 。
  • 值是 。
  • 值是 。

其中第三种只有在高层有取反都情况下才有可能出现。由于我们把所有取反已经推到叶子了,此类情况一定不会出现。

证明是容易的。 都是恒同变换, 会变成常值函数,然后一层层带上去化简即可。

考虑检验一个表达式是否合法。

首先我们对叶子应用这个结论。

固定除了 外的所有变量。找到所有改变 之后表达式值变化的位置,

  • 如果 从 变成 之后整个表达式值从 变成了 ,那么 前面就没有取反符号。
  • 如果 从 变成 之后整个表达式值从 变成了 ,那么 前面就有取反符号。
  • 如果上面两种同时出现,那么根据我们上面的推论,就无解。

我们处理完单个变量之后,对真值表做对应操作。这样固定一些元素,真值表的值是单调的。

接下来我们考虑对某个子树应用这个结论。

首先,一定存在一个子树,他的两个儿子都是叶子。

我们考虑如何找出来这样的两个节点。

我们发现,枚举两个节点,然后判断是否可行。

AT_arc160_f Count Sorted Arrays

超级牛逼题目。

首先考虑一个转化。

考虑把一个序列转化成 个 字符串,第 个串中所有小于 的位置都置 。那么一个排列被排序当且仅当他对应的所有字符串都被排好序了(值域为 是一个非常有用的性质,因为满足条件的字符串只有 个,而排列有 个)。

我们对每一个字符串建点,一个排列唯一对应了 到 的一条路径,连边就是把一个位置的 改成 。

QOJ 3307. 树上查询 17

口胡了一个比较大的做法。

P4223 期望逆序对

牛大了。

首先你考虑期望的线性性转化成每对数做的贡献。考虑枚举逆序对里较小的那个,然后每个位置有大于等于小于三种状态。我们期望的状态是前面大于后面等于。

和上一题一样,矩阵快速幂即可。

此时复杂度是 。

这里 ,似乎爆炸了。

然后发现没什么前途。

我们考虑追踪一对元素。

假设一开始元素的位置是 。其余位置集合为 。

假设最后 到达了 ,其中 。

我们将要证明,对于所有可能到达的 ,出现的概率都是均等的。

假设一条路径是 。我们考虑选择一个置换 ,满足这个置换固定 ,交换 。

把这一条路径替换成 。

显然替换后的路径 最后到达了 。另一方面,这种变换显然可逆(考虑 )。

因此我们建立了一个到达 的路径到到达 路径是双射。这两种路径个数相等。

实际上对应一个更厉害的性质。如果一个随机过程在一个群作用下保持不变,那么轨道上的所有事件发生概率都是相同的。

那么接下来考虑一对元素 最后的位置。

有以下几种可能。


202611 杂题选做
https://blogs.sving1024.top/posts/57010/
发布于
2026年11月7日
许可协议