Day6
\(100+30+100+0,rk3\) ，考成这样还能 \(rk3\) ，好怪啊
虽然但是 \(T3\) 是在 \(oeis\) 上找的，虽然写了随机数但还是运气好过掉了
\(T2\) 应该是写寄了吧，感觉自己做法并没有什么问题
T1
比较典的题，并查集维护下一个没被删的点即可
复杂度 \(O((n+Q) \alpha(n))\)
T2
题目里的同构二字提醒的很明显了，要用树哈希判树同构
题目显然是 \(dp\)
设 \(dp_u\) 表示以 \(u\) 为根的答案。分析样例可以发现对于数形态相同的子树有以下两种性质：
- \(dp\) 值相同
- 对这些子树的根分配的问题等价于可重集问题：找一个长度为 \(n\) 的可重集，所有数 \(\leq m\) 的可重集方案数。问题是一个插板法，把 \(m\) 个板子插到 \(n\) 个空格里
因此我们只需要这么做就可了，复杂度 \(O(n^2)\) ，我用 \(map\) 因此多了 \(O(\log n)\)
T3
一个 \(2 \times 2\) 的矩形只能放一个棋子，我们可以把一个 \(2n \times 2n\) 的格子中每个 \(2 \times 2\) 的格子看成一个点，这样我们就可以把格子看成 \(n \times n\)
考虑当一个棋子放到了小格子的左上角，则在这个小格子左上角的所有小格子，他们都只能放到左上角。同样的，对于右下角某个小格子放了一个棋子，则在这个小格子右下角所有小格子都只能放到右下角。连接这两个小格子之间的一个阶梯，右上和左下都填成小格子填在右上和左下的方案
考虑暴力的计算这个贡献，我们暴力枚举左上角 \((a,b)\) 和右下角 \((c,d)\) ，用组合数填阶梯
一些细节：当 \(a=0, b=0\) 是会算到 \(a=0,b>0\) 的情况，要去重
T4
- 如果我们有一个数不想要，比如说 \(9\) ，我们可以 \(\sqrt{ \sqrt{9} }\) ，然后再乘起来
- 如果有一些数不想要，比如 \(1,2,3,4,5\) ，我们可以把他们加在一起后开根
根据小学数学知识拉格朗日差值，考虑当 \(m=1\) 时，我们可以这么构造，假如 \(x_1 = 2\) ，我们可以让 \(f(x) = \sqrt{ \sqrt{ \sqrt{ \sqrt{ \sqrt{ \sqrt{(x-1)(x-3)(x-4)...(x-9)} } } } } } \times y_1\) 来得到答案
当 \(m \neq 1\) 时，我们可以构造多个 \(f_1(x), f_2(x)\) ，然后把他们加起来即可
然后我们没有考虑完，因为 \(y_1\) 从何而来？我们发现 \(y_1\) 可以二进制分解，而二进制分解我们只需要多个 \(2\) 乘起来。而 \(2 = 1 + 1\) ，因此我们可以凑出 \(y_1\) ，完结
贪心、二分、模拟
-
\(n\) 个线段选最多不相交
右端点排序
但有个神奇的东西，我们把两个相交的线段连边，这个问题就变成了最大独立集，而且图也不是二分图
这个图有一个性质：所有环都是三元环，比如：1 2 1 3 2 4 3 4这个样子是不可能出现的
因此如果给你一个这样的图，我们可以把他转换成原问题。我们没必要把线段构造出来，但对于一个三元环，里面肯定选的一个点是度数最小的 -
\(n\) 个任务，第 \(i\) 个结束时间 \(d_i\) ，完成需要 \(t_i\) 的时间，如果超出时限产生超出部分的贡献。让贡献最大值最小
- 按 \(t_i\) 排序？
1 100 10 10- 按 \(d_i - t_i\) 排序？
1 2 10 10- 二分答案+线段树？
确实可以，但老师要除排序线性贪心
其实这题只要按照 \(d_i\) 排序就行了，但看起来完全不符合直觉，因为你排序甚至和 \(t_i\) 没有关系。我们证明一下：
显然我们的贪心策略一定不存在空隙和逆序对
考虑任意一个没有空隙的策略 \(O\) ，都可以通过交换一个逆序对让答案变得不劣
假设 \(d_j < d_i\) ，则先做 \(i\) 后做 \(j\) 的延迟是： \(\max(f_i - d_i, f_j - d_j)\) ，先做 \(j\) 后做 \(i\) 的延迟是： \(\max(f_j - d_i, f_i - d_j)\) 。显然 \(f_i - d_j \leq f_j - d_j, f_j - d_i \leq f_j - d_j\) ，因此交换会更优 -
设 \(f_i\) 表示前 \(i\) 轮大的赢赢得最多，显然贪心选 \(>a_i\) 的最小的数。设 \(g_i\) 表示后 \(i\) 轮小的赢赢得最多，显然贪心。合并求最大
合并会出现重复选的情况，但因为如果重复，不如交换，因为一个最大一个最小，交换后不劣 -
模拟费用流
如果只有两种币，我们可以假设全选 \(B\) ，然后我们可以按 \(a_i - b_i\) 排序，然后把一些 \(B\) 币换成 \(A\) 币，换言之前 \(X\) 个选 \(A\) ，后 \(Y\) 个选 \(B\)
而有了 \(C\) ，我们可以枚举 \(A/C\) 和 \(B/C\) 的分界点，然后就变成了两个二元问题，直接用上面那个方法做就行 -
从 \(1\) 走到 \(n\) ,每次可以向右走一步，或 \(p_i\) 的概率梭哈到 \(n\) ，或 \(1-p_i\) 的概率落到 \(a_i\) ，问最优策略下期望时间
\(n \leq 10^5, 1 \leq a_i \leq i\)通常看到期望题，第一反应是 \(dp\)
记 \(dp_i\) 表示 \(i \rightarrow n\) 期望时间
\(dp_i = \min\{ 1 + dp_{i+1}, p_i + (1 - p_i)(1 + dp_{a_i})\}\)
显然 \(dp\) 有后效性，而且因为有 \(\min\) 高斯消元也做不了
我们发现假如 \(i\) 是我们最优的梭哈点，我们从 \(1\) 一步一步走到 \(i\) ，然后梭哈一把，如果失败了，他跳到了 \(a_i\) ，作为一个有贪心思想的人，我们肯定会走到 \(i\) 再梭哈，因为他是我们的最优梭哈点，否则我们不如第一次就在 \(a_i\) 梭哈 -
非常典的一道题的魔改，因为有负数
判一下就行了，复杂度 \(O(n \log A)\) -
01背包
\(n \leq 40, V,v_i,w_i \leq 10^9\)数据范围想让 \(O(2^{\frac{n}{2}})\)
\(Meet\ In\ The\ Middle\) -
tip1：中位数是一个非常抽象的东西，他的难度其实是和求排名不相上下的。而求排名我们要怎么做？二分答案。我们可以二分答案，然后把原问题转化为只有 \(01\) 的情况，这个问题就会相对好做一些
我们发现如果我们遇到两个连续的1 1，那他会一直往上走，直到遇到边边角；0 0的情况也同理
所以原问题就变成了找到距离对称轴最近的1 1和0 0，不会出现1 1和0 0距离对称轴距离相等的情况，因为中间的部分必须是0 1交替的。所以我们每次取最近的就可以成为答案；如果没有0 0和1 1，说明序列一定 \(01\) 交替，直接看对称轴左右的数即可 -
老师曰：期望问题，要么组合计数要么 \(dp\)
设 \(dp_{i,j}\) 当前在 \(i, HP = j\) 的期望到 \(n\) 点时间
\[\]\[\]从 \(1\) 走到 \(n\) ,每次可以向右走一步，或 \(p_i\) 的概率梭哈到 \(n\) ，或 \(1-p_i\) 的概率落到 \(a_i\) ，问最优策略下期望时间
\(n \leq 10^5, 1 \leq a_i \leq i\)这题我们解决时用了贪心来避免了 \(dp\) 的后效性，我们能否把结论同时用在这题上呢？实际上是不行的
我们是不是还在讲二分？我们为什么不二分 \(dp_{1,H}\) 的值呢，因为答案显然具有单调性，所以我们就判断即可
其实这个思路在之前的 qoj 的某常比赛里见过，虽然但是我看代码也没看懂为什么要二分 -
是否还记得我们讲的AGC006D这题？
先考虑一个链会怎么样？会发现对于一个1 1，他会不断往外扩展，因此在他变成一半 \(0\) 一半 \(1\) 时，操作次数不会超过 \(O(n)\) -
方法1：因为是竞赛图，有环一定有三元环，缩点
方法2：考虑一个点 \(x\) ，一定能找到两个点 \(y,z\) 满足：x -> y x -> z y -> z那 \(x \rightarrow z\) 这条边一定是没有用的，因为如果我们能找到一点 \(a\) 使 \(x, z, a\) 成为三元环，那 \(y \leftrightarrow a\) 中一定有一边，如果 \(y \rightarrow a\) ，那 \(x, y, a\) 成为三元环；否则 \(y,z,a\) 成三元环。因此我们可以把边 \(x \rightarrow z\) 删掉
于是在图中把若干条边忽略掉后，每个点最多一个出边，因此我们只要枚举两个点，再看和他相连的点是否成环即可。复杂度 \(O(n^2)\)