时间安排
8:10 - 8:15
读题，B C D 都毫无思路。
8:15 - 8:30
A 题的 60 分暴力很好拿，15 min 敲完。
8:30 - 9:05
B 题没想法，打完爆搜走人。
9:13 - 9:20
C 题没想法，打完 \(O(n^3)\) 走人。
9:20 - 9:45
D 题一个部分分都不会写。。。瞪眼 \(25\) 分钟走人。
9:45 - 10:50
继续观察 A 题，感觉好像是 SPT，直接开写，一个小时后过了大样例。然而赛后证明我是小丑。
10:50 - 12:00
罚坐。
总结反思
- 小的 trick 积累不足，找不到题目的突破口。
- B 题 \(m \leq 20\) 那一档分没能第一时间反应过来是状压。
- 期望还是不咋会，点分治也忘干净了。
题解
A.出租车
简单题（然而赛时没想到）。只需对每一辆车跑一遍 dij，对于合法的点连边，最后再跑一遍 dij 即可，时间复杂度 \(O((n+m)n\log n)\)。
B.拍卖会
神仙题。将题目转化为有一个 \(n\) 行 \(m\) 列的矩阵，要满足：
- 每一列最多有一个 \(1\)。
- 第 \(i\) 行中，\([1,l_i]\)，\([r_i,m]\) 中各有一个 \(1\)。
考虑 DP，设 \(f_{i,j,k}\) 表示考虑了前 \(i\) 列，前 \(i\) 列中有 \(j\) 个右区间未被满足，还有 \(k\) 列没有选的方案数。显然 \(k\) 可以直接通过 \(i\) 和 \(j\) 计算出来。贴份代码 link。
C.序列
突破口在于一个小 trick：区间 \([1,x]\) 中二进制下有奇数个 \(1\) 的整数有
int get(int x) {
return (x>>1)+(x&1||__builtin_popcount(x)&1);
}
这也可以通过打表发现。接下来考虑 \(x \ xor \ y\) 在二进制下 \(1\) 的数目的奇偶性实际上只跟 \(x\) 和 \(y\) 自己二进制下的奇偶性有关。即 要使 \(x \ xor \ y\) 在二进制下有奇数个 \(1\)，\(x\) 和 \(y\) 需要满足一个在二进制下有奇数个 \(1\)，一个在二进制下有偶数个 \(1\)。设一个区间中有 \(k\) 个“奇数”，\(v\) 个“偶数”，则这个区间的好的点对的数目为 \(k \times v\)。使用动态开点权值线段树维护区间即可。
D.清除病毒
最有收获的一道题，复习了点分治和期望。一个人占据 \(x\) 个点的方案数为 \(C_n^x\)，占据某个点对的方案数为 \(C_{n-2}^{x-2}\)，所有占据某个点对的方案数为 \(\frac{ C_{n-2}^{x-2} }{ C_n^x }\) 即 \(x(x-1)/(n(n-1))\)。然后就是点分治板子了。