CF1657E
发现充要条件即为对于每个点 \(i\),其与 \(1\) 的连边为其所有连边中最小的。
这 \(dp_{i,j}\) 表示处理了 \(i\) 个点,当前与 \(1\) 连的最大的边长度是 \(j\)。
\(dp_{i,j}=\sum_{t=1}^{i-1}(\sum_{x=0}^{j-1}dp_{t,x})\times C_{n-t}^{i-t}\times (k-j+1)^{(i+t-3)(i-t)/2}\).
表示枚举与 \(1\) 连边小于 \(j\) 距离的有 \(t\) 个,且新加的点与 \(1\) 的连边的值是 \(j\)。
在新加的 \(i-t\) 个点中,两两之间的边和与之前点的边权都不小于 \(j\)。
这里 \(\sum_{x=0}^{j-1}dp_{t,x}\) 应该用前缀和优化。
CF1109D
考虑枚举 \(a,b\) 之间距离为 \(i\)。那么先选 \(i-1\) 个点出来排列,贡献为 \(A_{n-2}^{i-1}\)。
根据插板法,确定这些边的距离,贡献为 \(C_{m-1}^{i-1}\)。
对于其他边的距离,贡献为 \(m^{n-i-1}\)。
最后,确定树的形态,根据广义 Cayley 定理,我们需要将原图构建为 \(i+1\) 个树。
贡献为 \((i+1)\times n^{n-1-(i+1)}\)。注意特判 \(i+1=n\)。
CF1753C
首先由于值域只有 \(0,1\),那么如果有 \(cnt\) 个 \(0\),排序的充要条件就是前 \(cnt\) 个数都是 \(0\)。
设 \(f_i\) 表示就是前 \(cnt\) 个数有 \(i\) 个数 都是 \(0\) 的期望。
从 \(f_{i}\) 到 \(f_{i+1}\),概率是 \(\dfrac{(cnt-i)^2}{C_n^2}\)
那么 \(f_{i+1}=f_{i}+\dfrac{C_n^2}{(cnt-i)^2}\)。
CF1253F
考虑计算走 \(u\to v\) 这条边最少的容量。
考虑贪心,我们肯定在走之前先去充满电,设最近的充电距离是 \(dis_u\),充满电走回要花 \(dis_u\)。
然后走过这条边,花费 \(w_{u\to v}\)。
然后,我们要支持剩下的点去最近的站,还需要 \(dis_v\)。
那么,走过 \(u\to v\) 的最少容量是 \(dis_u+w_{u\to v}+dis_v\)。
建出最小生成树即可。
考虑计算 \(dis\),考虑建立超级源点,向所有站点连边,跑一遍最短路即可。
CF526F
发现二维问题可以转化为一维问题,对于一个点 \((x,y)\),令 \(a_x=y\)。
现在我们要处理所有子区间,计算 \(\max-\min-len=-1\) 的个数。
扫描线,考虑往右推右端点,同时线段树维护每个左端点的 \(\max-\min-len\)。
发现 \(\max-\min-len\) 中 \(-1\) 一定是最小值,因为题目满足每行每列只有一个棋子。
那么线段树只需要维护最小值的个数,这是容易维护的。
单调栈辅助。
CF802O
恰好 \(k\) 道题,考虑 wqs 二分,现在求代价最小值。
考虑贪心,从小到大枚举 \(i\),并 \(b_i\) 与之前的最小的 \(a_i\) 匹配。
或者,替换之前最大的 \(b\)。用反悔贪心实现。
只需要维护一个堆,维护 \(a_i,-b_i\) 的最小值。