mygr main()

T1 什么寄吧 这个Y有什么存在的意义吗 T2 ？真的是我想的那样吗 反正最短路都唯一了，那就先跑一遍dij 然后对终点的所有出边判断一遍？ 手玩样例也没问题啊？ 难道是我想假了？ T3 容易想到枚举开头元素，二分其长度 问题就变成了“我如何判断能不能取到这些数” 变成狗构造了（ 首先当数的个数大于 $n+1$ 时一定无解，当不包含起始位置时当大于 $n$ 一定无解 容易发现它的逻辑其实是这样的：牺牲一边的数从而取到另一边的数 所以从中间开始拓展一定最优 草了好像没什么变化 check咋弄都是 $O(n)$ 的 其实就是说每个黑格子都得匹配一个上方的白格子嘛 欸那是不是就是说对于每个黑格子，都满足他顶上的黑格子数小于另一侧的白格子数 设每个格子当前值为其顶上的白-黑，那么应时刻保持其大于等于0 我们发现其实把一个格子从白变成黑的过程其实就会将其下方所有位置减去1 而我们又知道初始时这是一个排列 所以双指针+线段树维护即可 牛皮

T1 送的 T2 T3 完了，今天咋都这么难 不妨这样子，先建出两棵树，然后编号相同的点之间连一条边权为 0 的边 然后就变成了两点之间的最长路 更本质一点的问题：二分图和最小生成树有什么关系 如果我把边权改为负的，那这样不就把符号变成min了吗 从左到右求一遍 再从右到左求一遍 根据brufk算法，这样应该是正确的 而且最多进行log次 等下，距离某点最远的点 那不就是重心吗 所以先求出两棵树的重心，然后就得到了每个点作为x时的dis 然后就有了两点的边权 选择最小那个，然后两个重心就被连接上了

T1 感觉和最长上升子序列很像 求一个子序列，使得满足 $a’ib_i<a’{i+1}$ 取个对数？然后就变成了 $\ln a’ib_i<\ln a’{i+1}$ 也就是 $\ln a’i+\ln b_i<\ln a’{i+1}$ 变成了加法，感觉会好做一点 现在变成了加上一个权值的最长上升子序列 考虑在正常的最长上升子序列中，我们设 $f_i$ 表示长度为 $i$ 的子序列的最小最后一位值 之所以能够这样维护还是因为 $f_i$ 具有单调性 但考虑对于现在而言，这还带有单调性吗？ 显然具有，而且比之前的更强，要求在加上一个权值后仍旧比上一位要大 注意 $f_i$ 具有单调性，但由于有 $f_{i+1}>f_i+b_i$，所以 $f_i+b_i$ 也具有单调性 然后二分，应该就做完了？ T2 转化下题意，其实就是问存在多少个 $x,y$ 使得 $$ d(x-1)+y \equiv a \pmod{w}\ d(y-1)+x \equiv b \pmod{w}\ $$ $a,b$ 对 $w$ 取模，$1\le x,y \le...

T2 考虑将所有数排序再二进制拆分，那么得到这样一个排列图 000|11111 00|1|00|11 0|1|0|0|1|0|1 枚举中间位 $j$ ，那么若 j 的这一位为 1，相当于01反转 变成统计每一层左右有多少个编号小于/大于自身的个数 画两根数轴，每根数轴表示0/1的编号 枚举下方的每一个区间，等价于问区间中有多少个待查寻线段 前缀和预处理一下即可 T3 换成与先 $$ \begin{eqnarray}&& \sum_{i=1}^{n-1}i \oplus (n-i)\ &=& \sum_{i=1}^{n-1} i+n-i-i & (n-i)\ &=& n(n-1)-\sum_{i=1}^{n-1} i & (n-i)\ \end{eqnarray} $$

T1 挖槽，眼熟 step1:到 因为是树，所以先跑到 ST 的路径上先再说 此时有若干种可能： 若 $dep_{lca_{S,T}}>dep_{lca_{S,S’}}$ ，则说明最快到达点为 $lca_{S,T}$ 否则为 $lca_{S,S’}$ 与 $lca_{T,S’}$ 中深度较大的那一个 求出最快到达点后，开始追逐，设其为点 $M$ step2:追 当 $dis_{M,S’}>dis_{M,S}$ 时，只能在终点相见了 否则答案为 $\left \lfloor\frac{dis_{S,S’}+1}{2}\right \rfloor$

T1 三维BFS乱搞一下应该就可以了吧 T2 经典套路，不难发现每个数最后到达的位置都是固定的 而根据冒泡排序的观点，其实排序也就等价于交换两个相邻的偏序点 $O(n^2)$ 枚举交换即可 T3 GF? 假设我们固定某些位后，其实转换题意后，就是求 $$ \begin{eqnarray}&& \left(\frac{1-x^{m+1}}{1-x} \right)^{L} \ &=& \left(1-x^{m+1} \right)^{L} \left(1-x\right)^{-L}\end{eqnarray} $$ 分别分解得到 $$ \begin{eqnarray}&& \left(1-x^{m+1} \right)^{L}\ &=& \sum_{i=0}^{L}C_{L}^{i}(-x^{im+i})\ &=& \sum_{i=0}^{L}C_{L}^{i}(-1)^{im+i}x^{im+i}\ \end{eqnarray} $$ $$ \begin{eqnarray}&&...

T2 考虑提取出某个树上连通块的代表元 发现对于每个连通块，它的根都是唯一的 所以 树上连通块的数量 = 树上无父亲点的数量 期望其实就是 $\frac{\sum_{p \in S} X_pY_p}{\mid S\mid}$ ,其中 $\mid S \mid = 2^{n}$ 变成求 $\sum\limits_{p\in S}X_pY_p$ 考虑对 $X_p$ 分解，变为每个点无父亲时的贡献 也就是 $\sum\limits_{i=1}^{n}E(i,fa_i)$ ，$E(i,j)$ 表示点 $i$ 必选 点 $j$ 必不选时第二棵树的贡献和 我们发现这其实等价于 点 $i$ 必选的贡献 - 点 $i,j$ 必选的贡献 考虑怎么求点 $i,j$ 必选的贡献，考虑从一开始的 $dp$ 开始入手 一开始，我们设 $f_{i,0/1}$ 表示在以点 $i$ 为根的子树中，点 $i$ 选/不选的期望 那么有 $$ f_{u,1}=\sum_{v\in son_u} \frac12(f_{v,0}+f_{v,1})\ f_{u,0}=\frac{\mid son_u...

[[20241009]] [[20241011]] [[20241012]] [[20241015]] [[20241017]] [[20241021]] [[20241022]] [[20241024]] [[20241025]] [[20241029]] [[20241105]] [[20241107]]

模拟赛时间 T1 发现其实就是问卷不卷的问题 而且求和再差导致了前面的决策并不会影响后边的 然后从第二个开始选择所有正值即可 T2 点分治 T3 我不会树状数组上二分啊（ 其实就是找两个情况 火大于等于冰的第一个瞬间以及冰大于火的瞬间 两个其实相邻问题就变成了“如何寻找冰大于火的瞬间” 说不定卡常能过呢？ 万一呢？ 试试看吧 先把T1T2敲了，再说T3

模拟赛时间 T1 感觉好像有点眼熟 感觉要证明些贪心的结论啥的 不管了，乱搞 首先对于最大的元素，显然有答案要么是最大次大的和取模，要么是双指针搞定 得到答案后显然后续的模数都必须大于这个值，发现砍掉了很大一块 所以乱搞即可 T2 草，典 思考我需要什么 一个朴素的LCA，一个向上的 $2^k$ 级父亲的位置，一个向下的 $2^k$ 级父亲的位置 我还需要知道某个点往上的第一个 xx 点的位置，这个其实倍增顺带求解即可 T3 发现他要求的其实是“结束排名的可能顺序有多少种” 而我们知道一种排名想要合法，那么应该满足其最小的使用数小于等于m 考虑设 $f_{S,i,j,k}$ 表示已经选的集合为 $S$ ，上一个选择的数为 $i$ ,上一次额外加的数为 $j$ ，总共额外加了 $k$ 的方案数 然后你发现其实 j 根本就没有意义，因为 j 显然与 $S$ 中的 $a_i$ 的最大值相等最好(或加减1) 所以就变成 $f_{S,i,0/1,k}$ 表示已经选的集合为 $S$ ，上一个选择的数为 $i$ ,上一次的值为最大值是否加1 ，总共额外加了 $k$...