CF938E Max History
定义一个序列 (a) 的值 (f_a) 如下：
- 初始 (f_a=0, M=1)
- 对于 (2leq ileq n) ，若 (a_M<a_i) ，则将 (f_a) 加上 (a_M) ，并让 (M=i)
计算给定序列 (a) 的 (n!) 个排列的 (f_a) 之和，答案模 (10^9+7)
(nleq10^6) ， (a_ileq10^9)
考虑 (a) 中每个数对答案造成的贡献，对于数 (x) ，假设它出现了 (u) 次，严格大于 (x) 的数出现了 (v) 次， (x) 会对 (a) 的某个排列 (b) 的 (f_b) 造成贡献当且仅当 (b) 中第一个大于等于 (x) 的数是 (x) ，对于随机排列，这个概率是 (frac{u}{u+v}) ，因为 (x) 必须是 (u+v) 个数中第一个出现的。因此答案即为每个数的概率乘上 (n!) 之和
接下来是又臭又长的标算解法，得出的式子是和概率解法一样的
同样的，考虑 (a) 中每个数对答案造成的贡献，注意到数 (x) 只有满足在排列中所有它之前的数都严格小于它才会产生贡献，假设序列中严格小于 (x) 的数的个数为 (k) ，则造成贡献的次数为 (displaystylesum_{i=0}^{k}inom{k}{i} imes(n-i-1)! imes i!) ，即枚举 (k) 个数中有 (i) 个在排列中被放在了 (x) 之前
把组合数拆开，提出 (k!) ，得到 (k!displaystylesum_{i=0}^kfrac{(n-i-1)!}{(k-i)!})
给里面强行配一个 (frac{1}{(n-k-1)!}) ，得到 (k!(n-k-1)!displaystylesum_{i=0}^kinom{n-i-1}{n-k-1})
由于 (displaystyleinom{m}{m}+inom{m+1}{m}+cdots+inom{n}{m}=inom{n+1}{m+1})
原式即为 (k!(n-k-1)!displaystyleinom{n}{n-k})
因此答案为 (displaystylesum_{i=1}^na_i imes k_i!(n-k_i-1)!inom{n}{n-k_i}=sum_{i=1}^nfrac{a_i imes n!}{n-k_i}) ，注意要去掉 (a) 中最大值的贡献
CF1292C Xenon's Attack on the Gangs
给定一棵 (n) 个点的树，需要给每条边分配一个互不相同的 ([0, n-2]) 的整数权值
定义 (S_{path(s, t)}=operatorname{mex}_{(u, v)in path(s, t)}w(u, v))
最大化 (displaystylesum_{1leq s<tleq n}S_{path(s, t)})
(nleq3000)
若将 ((u, v)) 赋值为 (0) ，则答案会加上删掉 ((u, v)) 后，树两部分的大小乘积
显然边权为 (1) 的边一定会放在 ((u, v)) 的邻边，边权为 (2) 的边一定会放在 边权为 (0) 或 (1) 的边 的邻边……如此填成一条路径
设 (dp_{u, v}) 为用边权小于 (dis(u, v)) 的数填完路径 (u, v) 后，答案的最大值
考虑令 (s_{u, v}) 为以 (u) 为根时， (v) 的子树大小，令 (p_{u, v}) 为以 (u) 为根时， (v) 的父节点
可以发现 (dp_{u, v}=max(dp_{u, p_{u, v}}, dp_{v, p_{v, u}})+s_{u, v} imes s_{v, u}) ，用记搜实现即可
CF1322C Instant Noodles
- 有 (T) 组测试数据
- 给出一张点数为 (2n) 的二分图，其中右侧的第 (i) 个点有点权为 (c_i)
- 令 (S) 表示左侧点的一个非空点集，设 (f(S)) 表示右侧点中至少与 (S) 中一个点相连的点的点权和
- 请你求出，对于所有非空集合 (S) ， (f(S)) 的 (gcd)
- (1 leq t,sum n,sum m leq 5 imes 10^5) ， (1 leq c_i leq 10^{12})
考虑两个右部点 (u, v) ，它们对应的左部点集合分别为 (R(u), R(S)) ，分以下几种情况讨论：
- (R(u)=R(v)) ，可以直接将两个点合并，点权相加
- (R(u)subseteq R(v)) ，若存在 (win S) 满足 (win R(v), w otin R(u)) ，点权和为 (c_v) ；否则为 (c_u+c_v) 。此时 (gcd(c_v, c_u+c_v)=gcd(c_v, c_u))
- (R(u)cap R(v) eqvarnothing) ，且 (S(u), S(v)) 没有包含关系，感性理解可以用 (gcd(c_u, c_v)) 计算贡献
- (R(u)cap R(v)=varnothing) ，此时 (u, v) 互不影响，可以用 (gcd(c_u, c_v)) 计算贡献
因此将所有 (R(u)=R(v)) 的点缩成一个点，点权为包含点点权之和，求缩完后的点的 (gcd) ，判定 (R(u)=R(v)) 可以用 hash
Luogu4151 [WC2011]最大XOR和路径
给定一张带权无向连通图，有重边、自环，找一条 (1) 到 (n) 的路径（不要求是简单路径），使得边权异或值最大
- (nleq5 imes10^4, mleq10^5)
- (w_ileq10^{18})
CF938G Shortest Path Queries
给定一张带权无向连通图，有 (q) 个操作：
- 给定 (x, y, d) ，在原图中添加一条 (x, y) 之间边权为 (d) 的边
- 给定 (x, y) ，将图中 (x, y) 之间的边删掉
- 给定 (x, y) ，查询 (x) 到 (y) 的异或最短路
保证任意操作后原图连通无重边自环，且操作合法
- (n, m, qleq2 imes10^5)
- (0leq d<2^{30})
像上一道题，如果没有删边操作可以直接用线性基维护，否则用线段树分治，用可撤销并查集维护异或前缀和，在线段树上维护 (log) 个线性基，时间复杂度 (O(nlog^2))
牛客练习赛59C
有 (x) 件材料 (A) 和 (y) 件材料 (B) ，用 (2) 件材料 (A) 和 (3) 件材料 (B) 可以合成一件装备，用 (4) 件材料 (A) 和 (1) 件材料 (B) 也可以合成一件装备。最大化合成的装备的数量
假设用第一种方式合成了 (a) 次，用第二种方式合成了 (b) 次，原题即为在满足 (egin{cases}2a+4bleq x\3a+bleq yend{cases}) 的条件下最大化 (a+b)
二分最后的答案 (mid) ，由于 (a+b=mid) ，将上述不等式减去 (mid) 得到 (egin{cases}2bleq x-2mid\2aleq y-2midend{cases}) ，即判定满足这个条件时 (a+b) 是否大于等于 (mid)
牛客练习赛59F
小松鼠站在地面上，地面上长了 (m) 棵松树从左到右排成一排，不妨用一维坐标表示每棵松树的位置，第 (i) 棵松树的位置为 (a_i) 。每棵松树分为树干部分和树叶部分，树叶部分会掉落果实，第 (i) 棵松树树干的长度为 (b_i) 。
有 (n) 个松果会从松树上掉落，第 (i) 个松果会在 (t_i) 时刻在第 (p_i) 棵松树的树叶上掉落，价值是 (c_i) 。小松鼠最开始可以站在任意位置，它单位时间内的移动速度为 (1) ，松果单位时间内掉落的速度为 (1) ，如果一个松果掉落到地面，并且小松鼠正好站在松果掉落的地方，小松鼠就会立即把松果吃掉，否则 (0.5) 秒后松果就会消失，小松鼠吃坚果不消耗时间。
小松鼠想最大化吃到的松果的价值，但是小松鼠不知道怎么才能吃到，于是这个问题就交个聪明的你了。
- (n, mleq10^5)
- (a_i, b_i, t_i, c_ileq10^9)
记第 (i) 个松果的落地时间为 (q_i) ，将松果按 (q_i) 升序排序。记 (f_i) 为当前刚吃掉第 (p_i) 个松果，吃过的松果最大价值和。容易发现，只有满足 (|a_{p_i}-a_{p_j}|leq q_i-q_j) 的 (j) 才能对 (f_i) 造成贡献，拆开绝对值，变成一个二维偏序问题，可以用 cdq分治 解决，时间复杂度 (O(nlog^2n))
有一个很巧妙的 (nlog n) 做法
假设横轴为位置，纵轴为时间，一个点在某一段时间能走到的范围一定是一个倒三角形：
*****/
***/
*/
将坐标轴顺时针方向旋转 (45^circ) ，一个点 ((x_1, y_1)) 能够到达另一个点 ((x_2, y_2)) 当且仅当 (x1leq x2, y1leq y2) ，因此在新坐标系下用二维偏序维护 dp 转移，即可做到 (nlog n)