Inftress

做题首先应该发掘性质，这里的性质很显然，对于正确答案而言肯定是按照右端点排序。 然后我就走偏了。 考虑正难则反，算相同的方案数。 注意到当相同的时候，正确答案和错误答案一定是一一对应的。 这个题看起来就很像 DP，那我们就要找子结构，找阶段。 好的我们现在想要做的是找其充要条件，这要求我们手玩。 我们通过手玩发现对于正确答案（红），错误答案（蓝），其他区间（黑）而言，所有的区间的左端点必须在蓝内。然后在两个红的右端点之间的右端点的左端点必须比较小的那个红的右端点小。 然后我们发现其实这个限制更有排序需求的是右端点，然后我们按照右端点排序，于是很自然想到以红色的右端点为阶段。 这个一个很好的性质是在一个阶段内，黑色的线段的左端点是一个排列，右端点在一定范围内完全无限制。 那从左到右还是从右到左？这个其实不一定，我们试了一下发现从右到左更好做。 然后这里是一个不平凡的观察，我们可以把蓝线段拆开来，右端点在上个阶段里确定，左端点在这个阶段里确定。 此时我们就对红色的左端点与两个蓝色的分界线的相对位置进行分类讨论。我们每次枚举这个阶段里的黑色左端点有多少个。然后把右端点任意插入。 不过我们还要考虑红蓝是同一个线段的情况，我们开两个数组即可。 直接转移并卡点常即可获得 100。时间复杂度 $O(n^2)$。

最后一年不能摆了，必须全力冲刺了。 之前一直在上文化课，现开始复健。 另一方面也应该调整好状态了。 从 6.25 晚上七点四十开始。 6.25

这个题目还是相当简单的吧。 你直接考虑用平衡树维护段长。 然后直接区间取最大即可。 糖丸了。

一个经典的想法是考虑让 Alice 和 Bob 都进行同一个过程。如果填不出来了就给提示。（显然 Alice 知道的信息严格多于 Bob，因此可以直接假装自己是 Bob 然后看自己需要哪些提示） 其实我们应该想想不同的染色方案之间有哪些联系。 感觉最困难的还是因为他是一个全局的问题，并不是很局部。我们得试着把这个问题拆的局部一些。 卡住了，看了一眼这个 AC 代码。 得到信息：考虑节点度数。 然后我们好像发现，你如果度数很少的话你根本不需要记录，你知道了旁边的一定有一个合法的。 所以一个想法是把度数 $\ge 8$ 的点的颜色传过去。 然后你发现你还是要传 3.75e5 个过去，太多啦！ 一个 creative 的想法是你根本不用传整个数过去，你也许只要传 3 位中的 2 位，剩下一位直接二分图染色。 然后就过了。

简单题。 我们可以枚举哪一个颜色没出现过，于是一种可能的区间就是你选择两个在该颜色中相邻（即中间没有相同颜色的）的点把他们的区间长度减一贡献到答案里。我们可以对 pair 做计数，离线下来二维数点即可。 也有可能是答案的右端点与询问的右端点重合，这个情况下我们可以通过提前双指针预处理每个左端点和右端点的答案。然后计算进去即可。

嗯首先我们先思考如何通过模和乘法凑出任意一个数。 我们很容易想到我们可以用两步操作，我们指定一个大质模数（比如 1e9+7），然后我们找 $\cfrac{b}{a} (\mod 10^9+7)$ 作为乘法即可。 然后我们想到把操作的一个点用来做乘和模，然后剩下一个放到最后一个点。 然后我们就可以在 $2n-2$ 次操作内把前 $n-1$ 个都归到任意我们想要的值。 然后我们想把最后一个也归位，但显然只有一个数不行的，我们想想两个数。不妨考虑 $n=2$ 的情况。 我们首先想到，我们如果目的是给一个数乘上一个数且后面一定要取模的话，那实际上我们可以把这个数调得很大（因为你后面肯定要取模，可以加后面那个模数的整数倍）然后这样对另一个数就没有影响了。 然后显然取模你是没有什么办法能避免的。 然后我们还发现最后一次一定会把某个位置的值乘上某个数，这提示我们不妨倒序考虑。 我们相当于说找 $a$ 的一个因子 $x$，使得其 $> b$，然后可以使 $a$ 除以 $x$，$b$ 加上 $x$ 的任意倍。 然后懒了，开始打表。 结果打出来一坨几百个边的图，在 graph editor 里抽搐。 只能推结论了。

牛牛题。 首先你把答案 reverse 一下，就是指定一个根，然后每次扩展一个相邻于当前连通块的点。 先考虑如何 check。 首先一个 native 的想法是考虑两种方向相反的 DFS 序。 然后你发现一个菊花图就把你 hack 了。 然后另一个 native 的想法是用两个根这样做。 但实际上你通过跑一下你发现还是会出问题，然后你看一下相同的两棵树，你发现他们一般动一两条边，然后他们分别连的都是同一连通块。 这启示我们从一个点连到哪个点进行考虑。 我们注意到我们根据一个拓扑序来构造一棵树的话，本质上你是把每个点选择一个前面的点挂上去。其实跟整个树的结构无关。你只关心每一步了连到了哪个点。 然后我们就想，如果对于两个拓扑序来讲一个点都能挂到前面的两个点上，那是不是就不唯一了呢？这个感觉是非常对的。 形式化的来讲，你对每个 $i$ 都找出 $i$ 在每个拓扑序中的位置，然后把前面的所有数的集合交起来。如果存在一个 $i$ 使得该集合大小超过 $1$ 则不合法。 然后你趁洗澡的时候对拍，然后回来发现拍了四万多组了都没出问题，就把他当对的了。 然后接下来的思路，你灵光一现，想到我们其实不怎么关心是怎么遍历的，我们关心的是从哪个点开始遍历的。 然后我们就想一条边他是怎么被经过的。然后你发现除了连接叶子的边其他边都要被正反经过一遍。 我们把叶子剥了，把每个里叶子都作为起点扫一遍就能做到。（这个显然是下界） 然后我们发现这个图的性质很优雅。我们发现这样一并把原来的性质满足了。 但我们还要考虑叶子怎么放置。我们发现我们直接紧贴着放在里叶子的后面即可。因为你发现这样一定不会重。 然后就做完了。 啊？ 等等，然后怎么做答案呢。 直接做即可。 我好厉害。 你发现你输出解会有点问题。 但不慌，你扰动一下，你每次把 $G$ 翻转一下。 然后就过了！！！

首先“三元环”触发关键词。 在竞赛图中若有环则一定有三元环。 然后我们再套路地把竞赛图进行 SCC 缩点是一条链。 很容易知道如果一个 SCC 不是链的最后一个他只能是一个点，因为若不是，则有三元环，而他们都指向后面，因此不合法。 显然我们要重点考虑最后一个 SCC。 然后呢就不会了，看一眼题解。 我们现在考虑找 SCC 中的一个点 $u$，并把他的前驱后继分开来。 显然前驱必须是一条链。 后继呢可以手玩。假设不是一条链，则一定有一个三元环，如果这个三元环都指向了一个点，那不合法，如果没有的话，则一定指到了 $u$ 的前驱，然后我们拿 $u$，那个前驱，指向前驱的点作为三元环，如果满足一定条件他们一定都指向三元环下一个点。反正啰里啰唆的，分讨即可。懒得写。于是后继也必须是一条链。 然后怎么做呢？ 然后我们通过手玩发现其实这个条件是充要的。具体来讲你反证法然后一定能推出一个矛盾。 然后他就像一个厚厚的甜甜圈一样，基于一个环。 主要是怎么 DP 的问题。 这个不愧是2000pts的题目完全做不出来。 严肃研读题解。 大哥我错了，这个题怎么这么难。 你主要是你对这个甜甜圈计数，

有趣题。 首先答案相当于要求三个矩阵里枚举三个点，然后求 AB 的路径数乘上 BC 之间的路径数加起来。 然后这个东西呢，我们先考虑假如 A 和 B 都固定的情况，我们发现是一个矩形。 然后我们根据一个叫曲棍球棒恒等式的东西我们很容易写出其为： $$ f(x_r + 1, y_r + 1) + f(x_l, y_l) - f(x_r + 1, y_l) - f(x_l, y_r + 1); $$ 然后我们就有平方做法了。 然后我们怎么继续优化？ 我们首先发现这个式子是可以拆的，拆成十六个问题，每个问题相当于给起点和终点要求午饭点。 然后我们还是想着差分对吧，然后我们就把他差分成：午饭区域是一个以起点为左下角的长方形。 然后我们惊奇的发现我们可以枚举我们从哪个边界出这个矩形的，因为我们知道了这个之后我们可以方便算出有多少种方案，更重要的是——在经过固定边界的一条路径上的午饭点的数量是相同的，我们直接乘起来就可以了。 然后就大概是超大常数 $O(n)$。

简单题。 首先看到这个题目第一眼就要想到结论：$n$ 个在 $[0,1]$ 间均匀随机的数的第 $k$ 小期望是 $\cfrac{k}{n + 1}$。 这个范围相当宽裕，我们只要给出一个 $O(\text{poly } n)$ 的即可 然后我们考虑枚举答案所在区间，我们现在枚举到了 $[t - 1, t]$。 然后我们想知道有多少个随机数落在这个区间里，多少个落在区间左，多少个落在区间右。我们如果知道这些我们可以直接通过那个结论算出对应的期望。 然后我们就是想要知道在钦定了左中右的数量后有多大概率。 我们可以使用二维背包，直接做即可。时间复杂度四次方。