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 期望逆序对
牛大了。
首先你考虑期望的线性性转化成每对数做的贡献。考虑枚举逆序对里较小的那个,然后每个位置有大于等于小于三种状态。我们期望的状态是前面大于后面等于。
和上一题一样,矩阵快速幂即可。
此时复杂度是
这里
然后发现没什么前途。
我们考虑追踪一对元素。
假设一开始元素的位置是
假设最后
我们将要证明,对于所有可能到达的
假设一条路径是
把这一条路径替换成
显然替换后的路径
因此我们建立了一个到达
实际上对应一个更厉害的性质。如果一个随机过程在一个群作用下保持不变,那么轨道上的所有事件发生概率都是相同的。
那么接下来考虑一对元素
有以下几种可能。