「ARC090E」Avoiding Collision
在一个有 \(N\) 个顶点和 \(M\) 条边的图上有两个人，分别在 \(S\) 号节点和 \(T\) 号节点。他们要各自走到对面（即在 \(S\) 的人走到 \(T\)，在 \(T\) 的人走到 \(S\)）。
给你M条边，描述为 \((u_i,v_i,d_i)\) 分别表示该边连接的两个点及边的长度。
求两人经过最短路径（可能有多条）且不相遇（在同一单位时间内都在一条边或一个点上）的方案数（答案对\(10^9+7\) 取模）。
因为走最短路，所以只会相遇一次。所以考虑容斥，总数减去相遇的数量。
考虑预处理出 \(S\) 起点的最短路和 \(T\) 起点的最短路方案数，然后枚举相遇的点和边，判一下，计个数即可。
「CF1693D」Decinc Dividing
定义一个序列 \(a\) 是好的，仅当可以通过删除 \(a\) 的一个单调递减子序列（可以为空）使得 \(a\) 单调递增。
给定一个 \(1\sim n\) 的排列 \(p\)，你需要求出 \(p\) 有多少子段是好的。
保证 \(n \le 2 \times 10^5\)。
转化一下题意，题目要求有一个上升子序列和一个下降子序列的子串数。
先考虑判定 DP。不妨设 \(f(i,0/1)\) 表示第 \(i\) 个数在递增 / 递减序列中时，递减 / 递增序列最后一个元素的最大 / 小值。
分类讨论来回转移即可。若 \(f(n,0/1) \not= \infty\) 就合法。
枚举区间直接做是 \(\mathcal{O}(n^2)\) 的。考虑从大到小枚举左端点，如果相同，那么将会完全一致，可以直接使用上次记录的点。
可以证明 \(f(i,0/1)\) 都只有四种取值，复杂度 \(\mathcal{O}(n)\)。
「CF1710E」Two Arrays
现有两个整数数组 \(a_1, a_2, \dots, a_n\) 和 \(b_1, b_2, \dots, b_m\)。
Alice 和 Bob 将要玩一个游戏，Alice 先手，然后他们轮流进行操作。
他们在一个 \(n\times m\) 的网格上进行游戏（网格有 \(n\) 排 \(m\) 列）。刚开始，有一个棋子放在网格的一排一列上。
在 Alice 或 Bob 轮次中，玩家可以选择以下两个动作中的一个进行操作：
- 将棋子移动到一个不同的格子上，该格子必须和棋子的原位置在同排或者同列上。玩家不能将棋子移动到已经被访问过 \(1000\) 次的格子上（也就是说，在游戏过程中，棋子最多可以在某个格子停留 \(1000\) 次）。请注意，我们规定起始单元格在开始时被视作访问过一次。
- 以 \(a_r + b_c\) 的得分立刻结束游戏，\((r, c)\) 表示棋子当前所在的单元格（也就是说，棋子在第 \(r\) 排第 \(c\) 列上）。
Bob 想要最大化自己的得分，Alice 则想要最小化自己的得分。如果他们都以最佳方式玩这个游戏，则最终的得分是多少？
考虑二分答案，连边 \(\le x\) 和 \(>x\) 的，是个二分图。
把 \(a,b\) 排序后变成一条折线。转化为求最大独立集，每行每列只能选 \(0\) 或 \(1\)。
于是策略为上面若干行列选 \(0\)，然后选 \(1\)。双指针维护即可。
「CF1718D」Permutation for Burenka
你题目怎么也这么长。
首先对于两个的数列，他们相似当且仅当他们的笛卡尔树形状相同。
建出笛卡尔树，然后考虑确定数对没确定数的影响。
预处理出点 \(u\) 的能选出的上下界 \(L(u),R(u)\)。然后按照右端点排序，找到最小的 \(\ge L\) 的没选过的 \(x\)，如果满足就删除，否则就 \(R=v\)。若 \(R\) 已经有值，则无解。
「CF1726E」Almost Perfect
问长度为 \(n\) 的排列数，满足对任意的 \(i\)，\(|p_i – j| \le 1\)，其中 \(j\) 满足 \(p_j = i\)。
保证 \(T \le 1000,\sum n \le 3 \times 10^5\)。
首先发现最后的形式只有 \(3\) 种，一元环二元环四元环。
一元环二元环简单，设个 DP。有转移：
然后只需要考虑四元环。设其数量为 \(k\)。首先四元环一定长这样：
那么相当于要在 \([1,n-1]\) 选出 \(k\) 个 \(i,j\)，使得这 \(2k\) 个数两两不相邻。不妨设 \(x_0,\dots,x_{2k}\) 表示这 \(2k+1\) 个空隙的长度，其需要满足 \(x_0,x_{2k} \ge 0,\forall i \in [1,2k),x_i \ge 1\)，且 \(\sum x=n-2k-1\)。
答案为 \(\dbinom{n-2k}{2k}\)，然后就是 \(2k\) 个数的组合，为 \(\dfrac{(2k)!}{k!}\)。
于是最后的答案为
复杂度 \(\mathcal{O}(n)\)。
「CF1728F」Fishermen
给你一个长度为 \(n\) 的序列 \(\{a\}\)，你可以将 \(\{a\}\) 中的数重新排列，并根据重排后的序列 \(\{a\}\) 生成序列 \(\{b\}\)，生成方法如下：
\(b_1=a_1\)。
\(\forall i\in(1,n]\)，\(b_i\) 是满足 \(a_i|b_i\) 且 \(b_i>b_{i-1}\) 的的小正整数。
求所以可能生成的序列 \(\{b\}\) 中 \(\sum\limits_{i=1}^nb_i\) 的最小值。
保证 \(n \le 10^3,1 \le a_i \le 10^6\)。
合法的 \(b\) 的条件是 \(a_i | b_i\)，且互不相同。注意到 \(b_i\) 不可能超过 \(n \cdot a_i\)。
于是考虑建图，对于 \(a_i\)，像所有 \(k \cdot a_i, k \in [1,n]\) 连一条边，然后就是二分图带权匹配问题了。
考虑如何优化，匈牙利的做法是枚举每个可能的 \(b_i\) 去增广，不妨从小到大枚举 \(b\)，这样得到的一定是最优解，因为加边也是从小到大加的。
最后如果没有匹配的时候不清空 vis，复杂度为 \(\mathcal{O}(n^3)\)。
我单方面宣布这次匈牙利薄纱网络流。（
「CF1728G」Illumination
给你一个范围 \([0,d]\) 的线段。现在有 \(n\) 盏灯 \(m\) 个点。对于每一盏灯，你可以选择一个 \([0,d]\) 的照明范围。一盏在 \(x\) 的灯可以照亮在 \([x-d,x+d]\) 的点。
一次合法的照明定义为所有的点都至少被一盏灯照亮。
现在你有 \(q\) 次询问，每次询问会给定一个整数 \(f_i\)，回答一次询问，你需要：添加一盏灯在 \(f_i\) 处。计算有多少种合法的照明方式。删除这盏灯。
保证 \(n \le 2 \times 10^5,d \le 3 \times 10^3,m \le 16\)。
先不考虑修改。因为 \(m\) 很小，于是考虑容斥计算。不妨设 \(f(S)\) 表示集合 \(S\) 内的点不会被覆盖的方案数，可以再预处理一个 \(g(l,r)\) 表示区间 \([p_l,p_r]\) 内不覆盖到边界的方案数。然后 \(f\) 就是若干个区间的积。
加一次灯后，\(g\) 可以暴力修改，但是 \(f\) 不行。
注意到，处理 \(f\) 的时候是，\(f\) 组成的区间的答案的积，所以如果把 \(f\) 和最后的容斥一起写，大概会成为这个形式：
相当于对于所有 \(f\) 有区间 \([j,i]\) 一起贡献，并且因为集合内元素增多，容斥系数再乘一个 \(-1\)。
所以每次修改完再暴力计算即可。
复杂度 \(\mathcal{O}(nm^2 + q m ^2)\)。
「CF1746F」Kazaee
给出一个长度为 \(n\) 的数组 \(a\) 和以下两种操作：
1 i x：将 \(a_i\) 修改为 \(x\)。2 l r k：询问在数组区间 \([l, r]\) 内是否每个出现过的正整数的出现次数都是 \(k\) 的倍数。（建议参照样例理解）若是则输出YES，若否则输出NO。保证 \(n,q \le 3 \times 10^5,1 \le a_i \le 10^9\)。
看着就很不能 \(\log\) （？
考虑维护前缀和，如果区间和是 \(k\) 的倍数则判对。但显然这个贪心很假。
于是对于每种 \(a_i\) 随机一个值，然后对随机值做，多做几次，正确率就高了。
「CF1750F」Majority
定义一个 \(01\) 串 \(s\) 是好的，当且仅当 \(s\) 可以通过以下操作变成全是\(1\)的串，可以操作无数次
选择 \(i,j\) 满足 \(i<j,s_i=s_j=1,2\sum_{k=i}^js_k\ge j-i+1\)，然后将 \(k\in[i,j]\) 的 \(s_k\) 全部改为 \(1\)。
给定 \(n\) 和 \(m\)，求有多少个长度为 \(n\) 的 \(01\) 串是好的，对 \(m\) 取模。
保证 \(n \le 5000,10 \le m \le 10^9\)。
最终状态可以看成若干个 \(0,1\) 段，每一个 \(0\) 段的长度都 \(>\) 两边 \(1\) 段长度和。
考虑 DP。不妨设 \(f(i,j)\) 表示长度为 \(i\)，两端为 \(1\)，最终状态下，最后一个 \(1\) 段有 \(j\) 个的方案数。于是答案为 \(f(n,n)\)。
考虑容斥，已知总数为 \(2^{i-2}\)。所以 \(f(i,i)\) 可以通过减去其他来算出。
枚举上一段 \(0\) 和 \(1\) 的长度 \(k,l\)，于是有：
然后前缀和优化一下即可。
「CF1750G」Doping
给定长度为 \(n\) 的排列 \(p\)，要对于 \(k=1,2,3,\cdots,n\) 求出，有多少个长度为 \(n\) 的排列 \(p’\) 满足 \(p’\) 字典序比 \(p\) 小，且 \(f(p’)=k\)，其中 \(f(a)\) 表示 \(a\) 最少可以划分成多少个区间，使得每个区间中的元素都是等差数列。
答案对 \(m\) 取模，\(m\) 不一定是质数。
保证 \(n\le 2000\)。
考虑容斥。不妨设 \(f(i)\) 表示能恰好分成 \(i\) 段的排列数量，\(g(i)\) 表示钦定分成 \(i\) 段的排列数量。于是有：
相当于我们选 \(j\) 段，然后为了凑齐 \(i\) 段，我们在 \(n-j\) 个位置里选出 \(i-j\) 位置切开。
接着考虑字典序。枚举 LCP，假设长度为 \(i\)。分类讨论 \(< p_i ,\ge p_i\) 的情况。于是假设两种情况分别有 \(a_1,a_2\) 个差为 \(1\) 的数对，数轴上形成了 \(b_1,b_2\) 个连续段。
所以对于要求的排列 \(p\) 的 \(i \sim n\) 位的排列，设被钦定分为了 \(k\) 段，于是有方案数：
枚举前面小于 \(p_i\) 的数构成了多少个连续段 \(j\)，并且此时一定存在 \(b_1+b_2\) 个连续段，于是剩下的段数为 \(k-b_1-b_2-j\)。于是这意味着我们需要从 \(a_1,a_2\) 中选出这些段。
然后对于这 \(k\) 个段，乱排的总方案为 \(k!\)，因为需要满足字典序的需求，也就是我们的排列的第 \(i\) 位需要 \(< p_i\)。而小于这个的连续段有 \(b_1+j\) 个，所以答案为 \((b_1 + j) (k-1)!\)。
整理一下：
然后还有个特殊情况，考虑在 \(p_i = p_{i-1}+1\)，就不用钦定 \(i\) 作为起点。于是有答案 \((k-1)! \dbinom{a_1+a_2}{k-f_1-f_2}\)。
考虑倒着枚举 \(k\)，这样 \(a,b\) 就可以直接从上一次的结果直接加过来。
复杂度 \(\mathcal{O}(n^2)\)。
「CF1753D」The Beach
有一个 \(n\times m\) 的网格图，场地上有许多不可移动的障碍，标记为
#，还有一些可以移动的障碍，如果他是横着的，定义它的一边为L，另一边为R；否则定义它的上边为U，下边为D，现在需要在这个网格图中空出一个 \(1\times 2\) 的空位，可以移动的障碍移动如下：
- 选择固定它的一边，将其旋转 \(90°\)，花费 \(p\) 单位，前提是旋转后不准与其他障碍重合。
- 将其平移一个单位，花费 \(q\) 单位，前提是平移后不准与其他障碍重合。
现在要求出在这个网格图里空出 \(1\times 2\) 的空位，至少需要花费多少单位，如果不可能，输出
-1。保证 \(n,m \le 3 \times 10^5,n \cdot m \le 3 \times 10^5\)。
可以想到要建图。那么如何建图。
首先有个结论，所有障碍移动后一定有一端在原来位置。否则没必要移动。
假设 \(s_{i,j} = \texttt{L}\) 的情况。连边 \((i-1,j+1) \rightarrow (i,j),(i+1,j+1) \rightarrow (i,j)\) 边权为 \(p\)。连边 \((i,j+2) \rightarrow (i,j)\) ，边权 \(q\)。
然后因为起点有很多个，所以建一个大起点即可。这样我们就求出了所有点空出来的最低费用。
于是答案为 \(\min \{ d(i,j)+d(i+1,j),d(i,j) + d(i,j+1) \}\)。
「CF1753E」N Machines
给定一个操作序列，每一个操作形如 \((+,a_i)\) 或 \((*,a_i)\) 。当前有一个变量 \(x\)，起始时 \(x=1\)，然后按操作序列的顺序进行操作。
当进行一次 \((+,a_i)\) 操作以后 \(x\) 变为 \(x+a_i\)。
当进行一次 \((*,a_i)\) 操作以后 \(x\) 变为 \(x \cdot a_i\)。现在你手中有 \(b\) 块钱，你可以花费 \(p\) 块钱将一个加法操作移动到操作序列的任意位置，也可以花费 \(m\) 块钱将一个乘法操作移到操作序列任意位置。
请问经过操作以后所能得到的 \(x\) 的最大值。保证初始操作序列所得结果不会超过 \(2\times 10^9\)。
考虑去掉 \(a_i =1\) 的乘法。这样乘法最多进行 \(31\) 次。
然后有一个显然的贪心策略，加法尽量往后移，乘法尽量往前移。于是就有一个做法，枚举移动到后面的乘法操作，对于加法操作，算出移动到最开头的贡献，选出最大的前几个。
考虑优化。对于 \(a_i\) 相同的乘法，只选择最前面的进行操作。加法操作可以在选完乘法后分段，每段优先考虑大的。
于是我们一样先搜哪些乘法放最后。然后不妨设剩下的钱还可以 \(k\) 次移动加法，二分出这些操作最小贡献 \(mid\)，再对于分段后的每一段二分算出贡献不小于 \(mid\) 的 \(a_i\) 数量。
可以过了。
「JOISC 2016 Day 1」俄罗斯套娃
有 \(n\) 个娃娃，每个娃娃有两个数值 \(r_i,h_i\)。如果娃娃 \(i\) 可以套住娃娃 \(j\)，当且仅当 \(r_j<r_i,h_j<h_i\)。
询问 \(q\) 次，每次询问给定 \(a_i,b_i\)。对于所有 \(r_i \ge a_i,h_i \le b_i\) 的娃娃，求没被套住的娃娃的最小值。
保证 \(n,q \le 2 \times 10^5,1 \le r_i,h_i,a_i,b_i \le 10^9\)。
首先对于一组 \(r_j<r_i,h_j<h_i\)，连边 \(j \rightarrow i\)。于是问题变成了求 DAG 上的最小链覆盖。
由 Dilworth 定理得知，我们只需要求 DAG 上的最长反链覆盖。
如果我们初始按照 \(r\) 排序，那么只需要求 DAG 上的最长不上升子序列，可以直接 DP。设 \(f(i)\) 表示 \(h_i\) 结束的答案。询问里的 \(a_i\) 限制可以用扫描线解决。
「JOISC 2019 Day1」聚会
交互题，给定一棵树，每次可以询问 \((x,y,z)\)，返回到三点距离之和最短的点，需要在有限次数内还原这棵树。
保证 \(n \le 2000,d_i \le 18,X \le 4 \times 10^4\)。
首先可以注意到如果 \((x,y,z)\) 的答案为 \(x\)，那么这意味着 \(z\) 在 \(x,y\) 的路径上。
然后没思路了。注意到题目里有个度数小于 \(18\)。可以确定是乱搞题了（？
随机一个根。每次询问两个点是否在一个子树内，就可以分治了。考虑如何优化，因为不在一个子树的点太多了，所以不妨随机两个点 \(x,y\)。然后询问其他点，如果不在这条连上，就在返回答案的点的子树里。这样分治就行了。
「JOISC 2019 Day1」考试
有 \(n\) 个学生，每个学生两个权值 \(s_i,t_i\)。
有 \(q\) 次询问，每次给定 \(a,b,c\)，问 \(s_i \ge a,t_i \ge b,s_i+t_i \ge c\) 的学生有多少个。
保证 \(n,q \le 10^5,a,b,s_i,t_i \le 10^9,c \le 2 \times 10^9\)。
把询问和学生一起做一个三维偏序即可。
注意算贡献的时候，不能算询问对询问的贡献。
复杂度 \(\mathcal{O}(n \log^2 n)\)。
「JOISC 2019 Day1」馕
给定长度为 \(M\) 的馕，和 \(N\) 个人，第 \(i\) 个人吃馕的第 \(j\) 米可以获得 \(Vi,j\) 的收益，现在需要将长为 \(M\) 的馕分成 \(N\) 段，每个人吃一段，使得每个人获得的收益至少为这个人吃掉整个馕的收益的 \(\dfrac{1}{N}\)，切的位置可以是分数。
保证 \(N \le 2000,L \le 2000,1 \le V_{i,j} \le 10^5\)。
神奇贪心。
对于一个人，如果他能恰好吃 \(\frac{1}{N}\)，后面的结果一定不劣。因此考虑对于每个人处理出他的 \(N\) 等分点。
然后每次考虑选一段，假设当前选到第 \(i\) 段，选出 \(N\) 个人中第 \(i\) 段最短的，然后再把这个人删掉。一直这样下去，可以发现一定有解。
复杂度 \(\mathcal{O}(n \log n)\)。
「JOISC 2019 Day2」两道料理
两道料理分别要 \(n,m\) 个操作。做菜需要按顺序。第一道菜第 \(i\) 个步骤用时 \(a_i\)，如果在第 \(s_i\) 前完成得分 \(p_i\)；第二道菜第 \(i\) 个步骤用时 \(b_i\)，如果在第 \(t_i\) 前完成得分 \(q_i\)。
最大化评分。
保证 \(1 \le n,m, \le 10^6,1\le a_i,b_j \le 10^9,1 \le s_i,t_i \le 10^{15},|p_i|,|q_i| \le 10^9\)。
不妨设 \(f(x,y)\) 表示第一道菜到步骤 \(x\)，第二道菜到步骤 \(y\) 的最大评分。转移都是枚举上一个位置，类似走放方格。相当于就是从 \((0,0)\) 走到 \((n,m)\) 的最大评分。
于是考虑把评分看成点，点 \((i,s_i)\) 有收益当且仅当他在路径上方，\((j,t_j)\) 在路径下方。因为不在一个边很烦，所以将答案先加上 \(\sum p_i\)，然后将点 \((i,s_i)\) 的权值 \(a_{i,s_i}\) 设为 \(-p_i\)。
预处理个前缀和，设 \(s_{i,j} = \sum\limits_{x=0}^y a_{i,x}\)。所以有转移：
对一行转移分析。考虑下 \(f(x)\) 的性质，显然 \(f(x)\) 是单调的，它相当于将 \(f(x-1)\) 值加上 \(s(x-1)\) 然后取前缀最大值。
所以我们差分一下 \(f(x)\)，得到的差分数组 \(d(i)\) 一定非负。
如果我们对 \(d(i)\) 加上一个正数，那么有影响只有位置 \(i\)。
如果加上一个负数 \(x\)，若 \(d(i)\) 变成 \(<0\)，则会变成 \(0\)。接着会影响后面值。可以发现，他会是后面连续一段总和最多为 \(-x\) 的数都变成 \(0\)，所以可以用线段树二分维护。
复杂度是 \(\mathcal{O}((n+m) \log m)\)。
「JOISC 2019 Day2」两个天线
有 \(n\) 个天线，天线高度 \(h_i\)，天线 \(i\) 可以向到它距离在 \([a_i,b_i]\) 范围内的天线发送信息。多次询问区间 \([l_i,r_i]\) 内可以相互发送信息的天线的 \(|h_x-h_y|\) 的最大值。
保证 \(n \le 2 \times 10^5,1 \le h_i \le 10^9,q \le 2 \times 10^5\)。
考虑拆开绝对值，然后正反都做一遍。
对于点 \(i\)，能算答案的只有 \(j \in [i+a_i,i+b_i]\)。于是每个点维护标记，于是对 \(i\)，在 \(i+a_i\) 放一个标记 \(p_i = – a_i\)，然后在 \(i+b_i+1\) 关闭标记 \(p_i = -inf\)。
然后查询的时候，因为要需要满足 \(i \in [j-b_j,j-a_j]\)，所以到 \(j\) 的时候直接对这个区间的与 \(a_j\) 取 \(\max\)。
可以用线段树维护。答案就是历史版本最大值。
「JOISC 2019 Day3」开关游戏
有 \(n\) 个灯。有初始状态。
每次可以选择一段区间，对灯的状态取反 / 全打开 / 全关闭。
求变成目标状态的最小操作数。
保证 \(n \le 10^6\)。
首先可以注意到，赋值操作一定在取反操作后。所以直接把操作拆成两个过程，第一个过程只赋值。
于是 DP。设 \(f(i,0/1/2,0/1)\) 表示，当前到 \(i\)；是否有以 \(i\) 为结尾的赋值操作，如果有是赋值哪个；是否有以 \(i\) 结尾的取反操作。
从 \(i-1\) 位直接转移。复杂度 \(\mathcal{O}(n)\)。
「JOISC 2019 Day3」指定城市
给定一棵树，双向边，每条边两个方向的权值分别为 \(c_i,d_i\)，多次询问 \(k\)，表示选出 \(k\) 个点，依次将以每个点为根的内向树边权赋值为 \(0\)，需要求出最后树的边权之和的最小值。
保证 \(n \le 2\times 10^6,q \le n,c_i,d_i \le 10^9\)。
我们只需要求出选出来边和的最大值即可。
先考虑 \(k=1\) 的情况，对于点 \(u\)，他的贡献就是以他为根的内向子树边的和 \(w_u\)。所以可以通过换根 DP 预处理出所有点的 \(w_u\)，然后取最大值即可。
再考虑 \(k=2\) 的情况，取两个点 \(u,v\)，贡献为 \(u,v\) 之间双向边的和，然后路径外的点向路径方向边的和。也就是 \(\dfrac{w_u+w_v+\text{dis}(u,v)}{2}\)，这东西长得就很直径。
那如果再加一个点呢？考虑把刚刚取的类似直径的东西缩起来，然后以这个点为根。每次选一个叶子，叶子到这个根的内向边的和就是贡献。
所以对于 \(k >1\) 的情况，可以把所有链预处理后排个序，然后一个一个取就行了。
复杂度 \(\mathcal{O}(n \log n)\)。
「JOISC 2019 Day4」合并
给定一棵树，每个点有一种颜色，如果能将颜色分为两组，使得两组内的点各构成一个连通块，则不合法。问最少合并多少种颜色使得树合法。
保证 \(n \le 5 \times 10^5,k \le n\)。
考虑不合法的情况。如果一条边的两侧子树内没有公共颜色，那么就一定不合法。
所以对于一条边，如果这条边合法，那么就保留，否则就把这条边的两个端点合并。最后答案就是叶子数量的一半下取整。
「JOISC 2021 Day2」道路建设
给出 \(n\) 个坐标 \((x_i,y_i)\)。连接两个坐标的费用为 \(|x_i – x_j| + |y_i – y_j|\)。选出最便宜的 \(k\) 条边。
保证 \(n \le 2.5 \times 10^5,|x_i|,|y_i| \le 10^9\)。
曼哈顿距离转切比雪夫距离。\((x,y) \rightarrow (x+y,x-y)\)。于是两个点的距离变成 \(\max( |x_i – x_j|,|y_i-y_j| )\)。
然后二分一个答案，查询距离小于等于这个答案的边数是否 \(\ge k\)。
查询过程对 \(x\) 排序，然后双指针，set 维护 \(y\) 坐标即可。
「JOISC 2021 Day4」最差记者 4
好长的题。
首先连边 \((i,a_i)\) 得到内向基环树（若干颗基环树或树）。环上的 \(\text{Rating}\) 一定相等。
环上只需要枚举维护环上的某个点或者统一改成最小值即可。
于是考虑满足限制关系，如果我们保留一个点，只需要修改剩余点一定就能满足了，因为需要代价小，所以选择点权大的即可。不妨设 \(f(u)\) 表示第 \(u\) 个人必须选，子树内能选择保留点的最大权值和。于是有：
因为和 \(h_u\) 有关，所以不妨设 \(g(u,i)\) 表示对于 \(v \in \text{son} (u)\)，仅考虑 \(h_v \ge i\) 的点，于是 \(f(u) = c_u + g(u,h_u)\)。
对于 \(g\) 数组，每次合并所有儿子，然后与父亲的 \(g(\text{fa}_u,val) (val \in [1,h_u])\) 取前缀最大值即可。线段树合并。
「POI2016」Nim z utrudnieniem
A 和 B 两个人玩游戏，一共有 \(m\) 颗石子，A 把它们分成了 \(n\) 堆，每堆石子数分别为 \(a_1,a_2,…,a_n\)，每轮可以选择一堆石子，取掉任意颗石子，但不能不取。谁先不能操作，谁就输了。在游戏开始前，B 可以扔掉若干堆石子，但是必须保证扔掉的堆数是 \(d\) 的倍数，且不能扔掉所有石子。
A 先手，请问 B 有多少种扔的方式，使得 B 能够获胜。
保证 \(n \le 5 \times 10^5,d \le 10,1 \le a_i \le 10^6\)。
首先转化一下题意，B 需要选择一个子集扔掉，使得剩下的数异或和为 \(0\)。这意味着选择的子集的异或和和整体异或和相同。
考虑 DP。设 \(f(i,j,k)\) 表示到第 \(i\) 个数，选了 \(\bmod d\) 意义下的 \(j\) 个数，异或和为 \(k\) 的结果。转移显然。
会 T。优化。注意到 \(x\) 和比 \(x\) 小的数异或和不会超过 \(2x\)，于是直接对 \(a\) 排序，然后每次只枚举到上限，均摊下来复杂度就对了。
复杂度 \(\mathcal{O}(nd)\)。
「EGOI 2022 Day1」重现赛
SubsetMex
如果我们需要一个数 \(x\)，那么我们需要消耗 \(0 \sim x-1\) 各一个。所以相当于如果我们需要 \(x\)，我们不妨将 \([0,x-1]\) 的 \(a_i\) 各减去 \(1\)。
初始时先对 \(i \in [0,n-1]\) 所有 \(a_i\) 减去 \(1\)。然后我们从大到小依次处理每个数，如果当前 \(a_i<0\) 我们就构造 \(|a_i|\) 并对于所有 \([0,i-1]\) 减去 \(|a_i|\)。
LegoWall
根号分治。
先考虑 \(n \le \sqrt{nm}\) 的情况。
先不考虑牢靠的情况，于是每一层都独立。每一层的递推式显然为 Fibonacci 数列。于是有答案 \((f_n)^m\)。
考虑容斥， 不妨设 \(h_i\) 表示有 \(i\) 列为牢靠的方案数。于是有转移：
复杂度 \(\mathcal{O}(n \log m + n^2)\)。
再考虑 \(m \le \sqrt{nm}\) 的情况。
直接 DP。不妨设 \(f(i,j)\) 表示当前到第 \(i\) 列，有 \(j\) 个凸出来的位置。有转移：
因为我们要保证牢靠，所以对于 \(\forall i \in [1,n]\) 都有 \(f(i,0) =0\)。
滚掉第一位。答案为 \(\sum\limits_{i=1}^m f(n-1,i)\)。复杂度为 \(\mathcal{O}(nm^2)\)。
可以通过本题。当然你也可以 MTT。
SocialEngineering
交互库写正解是吧你。
首先有个很自然的想法，对于 \(1\) 出去一条边，我们都要找一个路径回到 \(1\)。这意味着我们需要把 \(1\) 所连的点两两配队，且他们的路径没有重复过的边。
去掉点 \(1\)。对每个连通块考虑。首先对于一个连通块来说，连向点 \(1\) 的点一定为偶数个，否则无解。
于是问题变成了给定一张图，和偶数个点，是否能所有点两两配对，使得这些点中的路径不存在边交集。
我们发现如果是一棵树的情况，我们也一定可以通过调整法使其一定有解。所以对于一个连通块，我们对其求一个生成树，然后通过调整法构造解即可。
Tourists
考虑询问对询问的影响。
一个区间修改。相当于把一群人全都合并到一个点上。他所影响的只有和他有交集的其他询修改，也就意味着对于 \([l,r]\)，我们可以找出和他有交集的修改 \(j\)，然后把 \(j\) 的交集部分砍掉。于是这意味着，对于任何时候，我们维护的所有区间两两之间无交。可以用 set 维护。
对于交集部分，我们相当于要把一群在 \(x_j\) 的点移动到 \(x_i\)，这里贡献是固定的。而查询只查询一个点。所以用树状数组和差分维护。
考虑第二个操作。单点修改。我们可以对于每个地点维护一个数组 \(val_x\) 表示 \(x\) 的总贡献和。对于每个区间再维护一个值 \(v\) 表示我到达 \(x\) 前，\(x\) 点已经发生演讲的贡献。于是对于一个点 \(u\)，假设此时他所在的区间为 \(i\)，都会有贡献 \(val_{x_i}-v_i\)。
「2022-11-04 提高模拟赛」
破门而入 (broken)
转化题意，如果连边 \((i,a_i)\)，最后形成 \(\le k\) 个环的方案数。
发现这是第一类 Stirling 数。\(\mathcal{O}(n^2)\) 处理即可。
翻转游戏 (turn)
考虑用总数减去重复的数量，重复的情况当且仅当选择的子串是回文串。
对于单个字母，反转他不会产生变化，所以这 \(n\) 种里面只取 \(1\) 种。
如果是选择区间 \([l,r]\)，如果 \(s_l = s_r\)，那么他会和 \([l+1,r-1]\) 的情况一样。这意味着对于一个字母，假设他有 \(x\) 个，那么他会产生重复的 \(\binom{x}{2}\) 个贡献。
复杂度 \(\mathcal{O}(n+m)\)，其中 \(m\) 为不同字符数量。
奶油蛋糕塔 (cake)
首先有一个很自然的建图想法，对于有相同一面的蛋糕 \(i,j\)，连边 \(i\) 与 \(j\)。那么问题就是找到若干个可以构成哈密顿回路的点，且希望这些点的点权尽量的大。
寄了。考虑转化为欧拉回路。考虑拆点，点权变成边权。对于没有边权的边，可以发现他是基于该蛋糕的颜色决定连边的。于是不妨将颜色作为点，蛋糕作为边，那么最后会形成一个只有四个点的图，我们要找一个，可以形成欧拉路的边集，并使得边权和尽量大。
但注意到奇数点 \(>2\) 才会不存在欧拉路，所以如果存在连通块大小为 \(4\) 并且 \(4\) 个点都是奇点的情况，只要删去一条边就可以了。显然选最小边最优，注意该边需要满足删掉这条边原图依然连通。
否则，找到边权和最大的连通块即可。
战争 (warfare)
我何德何能在提高模拟赛碰到时停定理（。
「2022-11-06 提高模拟赛」
数据恢复 (data)
我觉得这题贪心很神仙！
考虑不存在数据依赖的情况，我们希望 \(a_i\) 尽量小，\(b_i\) 尽量大，所以不妨按照 \(\dfrac{b_i}{a_i}\) 从大到小排序，依次选择即可。
那如果存在依赖情况呢？因为父亲的选择会影响到儿子，所以不妨倒序考虑问题，先从叶子节点考虑。一个点选完后，将他的贡献合并到他父亲上去，也就是 \(a_u+a_v,b_u+b_v\)，然后开个堆处理即可。
正确性我不好说（？
下落的小球 (ball)
说是全场最简单的题（？）但是我觉得 T3 比他简单（指思维。
不妨先考虑答案的存在性。不妨设子树大小 \(sz_i\)，子树 \(a\) 的和 \(b_i\)，如果每次操作后都存在 \(\forall i,r_i=b_i-s_i \ge 0\)。接着可以发现，对于点 \(i\)，如果操作点 \(i\) 子树内任意一点，\(i\) 上的球都会轮换一次。当操作第 \(r_i+1\) 次时，\(i\) 将会变成无球的状态。
这意味着前 \(r_i\) 次操作只会影响子树外的，后 \(s_i\) 次只会影响子树内的。
计数的时候不妨从下到上，合并子树时，考虑一颗子树内前 \(r_i\) 次（A），和后 \(s_i\) 次（B）。A 和 A 合并，B 和 B 合并，形成当前点的 A 和 B。合并两个长度分别为 \(x\) 和 \(y\) 的序列的方案数为 \(\binom{x+y}{x}\)。
复杂度 \(\mathcal{O}(n)\)。
消失的运算符 (operator)
先考虑没有括号的情况。
考虑 DP，设 \(f(i,j)\) 表示前 \(i\) 个数字，已经有了 \(j\) 个加号的答案。但转移的时候需要枚举最后一段的乘法贡献，所以考虑设 \(f(i,j)\) 为前 \(i\) 个数，\(j\) 个加号，且不记最后一段乘法的答案，再设 \(g(i,j)\) 表示最后一段乘法的答案。
转移的时候大概就是，如果是加号的话，\(f\) 需要算上 \(g\) 的贡献，而最新的数是要放到 \(g\) 上，如果是乘法的话就只需要改变 \(g\) 就行了。
然后有括号。
首先建出一棵树，然后一个子树算完后，相当于要合并 \(m\) 个结果上去，这个类似树上背包，合并的时候再记个每种方案的方案和。为了方便记录，\(f(i,j)\) 的 \(i\) 可以改成为第 \(i\) 个括号这层的答案。
另外发现平时没注意到树形背包的复杂度这一点。见两种写法复杂度。
古老的序列问题 (sequence)
先考虑不用计算子区间的答案。
然后我们有一个离线的做法，线段树维护所有区间的答案，两个单调队列最大值和最小值，每次加入一个值相当于修改队列中相邻两个位置之间的最大值 / 最小值。线段树只用维护区间积即可，删除一个数可以乘上他的逆元。
再考虑子区间的答案，发现只要维护历史和就可以了。
复杂度 \(\mathcal{O}(n \log n)\)。
「2022-11-11 提高模拟赛」
Halcyon (halcyon)
首先排个序，相邻两个连一条边。
于是有一个贪心。每次找到一个最小的边然后加进去。
但这样的贪心显然是假的，因为加完这条边后相邻的边无法再加。可能不是最优。
但考虑到如果边 \((i,i+1)\) 加进去了。但没有加 \((i-1,i)\) 和 \((i,i+1)\)，如果当前不是最优的，那么最优的一定是相邻两条边一起加。
于是如果我们加入了一条边 \((i,i+1)\)，且他的贡献为 \(a_i\)，那么可以考虑在堆中再加入 \((i-1,i+2)\)，贡献为 \(a_{i-1}+a_{i+1}-a_i\)。
同样的，对于一个加入的区间 \((u,v)\) 贡献为 \(c\)，可以再在堆中加入 \((u-1,v+1)\) ，且贡献为 \(a_{L_u}+a_{R_u}-c\)。设 \(L_u,R_u\) 表示这段前面 / 后面的贡献，可以实时维护。
取 \(m\) 次即为答案。
复杂度 \(\mathcal{O}(m \log n)\)。
Tempestissimo (tempest)
不妨对每个点考虑答案。
对于一个点 \(u\)，能影响到他结果的只有儿子 \(v\) 与自身。然后可以发现这相当于问有 \(m\) 个数，求这些数的所有子集异或和的和，然后减去子集大小为 \(1\) 的答案。于是安位考虑，如果这一位上，存在 \(1\)，那么会有两种答案，\(0\) 或 \(1\)。
然后进行一些推导可以发现这个时候所有子集异或和的结果，为 \(0\) 和为 \(1\) 的数量是一样的。即 \(2^{n-1}\)。
不妨设 \(s = \sum a_x\)。
也就是对于一个点 \(u\)，他和他儿子的总贡献为 \(2^{m-1} \cdot \bigoplus\limits_{x \in \{u,v\}} a_x -s\)，其中 \(\bigoplus\) 表示或。
考虑剩余点，剩余点的选择并不会影响到点 \(u\) 的结果，所以直接乘上方案数即可。
所以对于一个点的贡献为 \(2^{n-1-m} \cdot (2^{m-1} \cdot \bigoplus\limits_{x \in \{u,v\}} a_x – s)\)。
注意根节点需要特判。
复杂度 \(\mathcal{O}(n)\)。
Testify (testify)
先画一画考虑什么时候不合法。
对于 \(w=0\) 的情况，直接把 \((u,v)\) 两个点合并即可。
对于 \(w \ge 1\)。可以发现如果存在 \(3\) 个点，构成的 \(3\) 条路径的公共点，没有先加进去，就是不合法的。
所以以第一个点为根，可以证明如果存在三个点 \((u,v,w)\) 不合法，那么 \((u,v,\operatorname{root})\) 一定也不合法。于是只需要考虑剩下两个点 \(u,v\)，他们与根节点的公共点就是 \(\operatorname{lca}(u,v)\)。
用 set 维护加进去的点集，和不合法点集的公共点即可。
复杂度 \(\mathcal{O}(n \log n)\)。
Steganography (stegano)
首先考虑 \(3\) 种情况的答案。不妨设 \(x = \prod\limits_{i=1}^m p_i^{x_i}\)，其中 \(p_i\) 为质数。
第一种，如果存在 \(x_i >1\)，为 \(0\)；否则为 \((-1)^{m}\)。第二种，答案为 \(\prod\limits_{i=1}^m (x_i+1)\)。第三种，答案为 \(\prod\limits_{i=1}^m \sum\limits_{j=0}^{x_i} p_i^j\)。
所以我们先将所有数质因数分解。因为对于 \(\ge \sqrt{a_i}\) 的质数数最多存在一个，所以每个数分为 \(\le 10^3\) 的小质数，和 \(> 10^3\) 的大质数 \(b_i\)。
先考虑小质数，总共只有 \(168\) 个。所以考虑直接预处理，设 \(cnt_{i,j}\) 表示对于第 \(i\) 个数，有多少个小质数 \(j\)。然后做个前缀和，就可以 \(\mathcal{O}(1)\) 查询出，这段区间的所有小质数的数量。然后再预处理所有质数的数量 \(x\) 时候的答案，直接计算即可。
对于大质数，因为最多只有 \(n\) 个，所以考虑分块。然后预处理个 \(res_{i,j}\) 表示块 \(i\) 到块 \(j\) 的答案，再预处理个 \(tot_{i,j}\) 表示块 \(i\) 的第 \(j\) 个质数的数量，再前缀和下。
查询的时候，对于散块，因为我们只关心散块所含有的 \(b_i\)，可以发现这个数量级不超过 \(\sqrt{n}\)。所以我们找出我们需要的的 \(tot_{i,j}\) 然后再暴力计算散块的贡献即可。
复杂度 \(\mathcal{O}(n \sqrt{n})\)。
原文地址：http://www.cnblogs.com/Rainy7/p/202211-note.html
