20230924 NOIP#14总结
时间安排
8:10~8:35
看题，\(B,D\) 看完没一点想法先放放。
8:35~9:20
写 \(A\) 的前两档和 \(C\) 的第一档。
9:20~9:40
瞪出来了 \(A\) 的正解写了。 （但是因为没判 \(-1\) 导致 \(100\Rightarrow 30\)
9:40~10:00
写 \(B\) 的第一档。
10:00~11:55
觉得 \(B,C,D\) 里 \(D\) 最可做，想了半天终于会写了。
11:55~12:05
检查文件并抱怨为什么还不来收题我要吃饭。
总结反思
- 细心做题少犯小毛病
题解
A.最短路
做 \(n\) 遍 \(dijkstra\) 求全源最短路，对于 \(\forall i\in [1,n]\) 若 \(dis_{i,j}\leq t\) 则连一条 \(i\) 到 \(j\) 边权为 \(c\) 的边。再最后跑一遍 \(dijkstra\) 求出答案。
B.套路题
转换成一共有一个 \(n\) 行 \(m\) 列的矩阵满足：每一列最多有一个 \(1\)；对于第 \(i\) 行 \([1,l_i],[r_i,n]\) 列中各有恰好一个 \(1\)。
设 \(f_{i,j,k}\) 表示考虑了前 \(i\) 列了，前 \(i\) 列中有 \(j\) 个右区间还没有被满足，还有 \(k\) 列没有选 \(1\) 的方案数。
转移时考虑这一列是否用来匹配一个右区间，以及之前的 \(k\) 列跟当前以 \(l_i\) 结尾的左区间匹配，这两步是同时进行的。
而发现 \(k\) 可以通过 \(i,j\) 计算出来，可以优化一维复杂度。
C.位运算#
考虑 \(x\ xor\ y\) 的性质，若 \(popcount(x)\% 2==popcount(y)\% 2\) 则 \(popcount(x\ xor\ y)\% 2==0\) ，反之亦然。那么直接用线段树维护区间并集中 \(1\) 的个数为奇数和偶数的数的个数即可。
\([1,n]\) 中二进制下有奇数个 \(1\) 的数字个数为 \(x/2+(x\% 2||popcount(x)\% 2)\) #
D.点分治+"组合计数"
设一个人占据了 \(k\) 个点，则对于一个点对，被占据的概率是 \(\frac{C_{n-2}^{k-2}}{C_n^k}=\frac{k\times (k-1)}{n\times (n-1)}\) ，设点对共有 \(s\) 个（这个可以用点分治求），则答案为 \(ans=s\times \frac{k\times (k-1)}{n\times (n-1)}\)
标签：20230924,10,frac,times,popcount,区间 From： https://www.cnblogs.com/programmingysx/p/17726298.html