CSP模拟赛 #35
A
题意：平面上给定 \(n\) 个点，求所有点两两之间曼哈顿距离比欧几里得距离的最小值和最大值。
\(n\le 10^6\)
设两个点之间的斜率为 \(k\)，设 \(k' = \max(|k|, \frac 1 {|k|})\)，我们相当于求 \(k'\) 的最小值和最大值。
发现求 \(k'\) 的最小值相当于把整个平面旋转 \(45^\circ\) 求最大值。钦定两点之间 \(x\) 的差小于 \(y\) 的差，将所有点按 \(x\) 排序，发现两个点如果不相邻一定不优，扫一遍即可。
B
题意：给定一棵 \(n\) 个点的树，对于每个 \(k \in [0, \lfloor \frac {n - 1} 2 \rfloor]\)，你需要选出一个大小为 \(m\) 的点集 \(S\)，满足 \(S\) 中的点两两之间距离 \(\le 2k\)。求方案数，答案对 \(998244353\) 取模。
\(m\le n\le 5000\)
从 \(2k\) 的特点入手。对于一个 \(S\)，定义一个点合法当且仅当其距离 \(S\) 中所有点的距离 \(\le k\)，那么 \(S\) 合法当且仅当存在至少一个合法点。发现合法点组成了一个连通块，可以点减边容斥。枚举 \(k\) 以及一个合法点 \(u\)，设 \(f[u,k]\) 表示子树内与 \(u\) 距离 \(\le k\) 的点的个数，\(g[u,k]\) 表示子树外与 \(u\) 距离 \(\le k\) 的点的个数，那么贡献为 \(\dbinom {f[u,k] + g[u,k]} m\)。枚举边 \((u, fa)\)，贡献为 \(-\dbinom {f[u,k - 1] + g[u,k]} m\)。
C
题意：给定一棵 \(n\) 个点的树，你给每个点染色，共有 \(m\) 种颜色。求使得同色点对之间距离的最小值（注意不是对于每种颜色） \(\in [L, R]\) 的染色方案数，答案对 \(10^9+7\) 取模。
\(1\le L \le R < n, \ m\le 10^9\)
先差分，用 \(\ge L\) 的减去 \(\ge R + 1\) 的方案数，设现在计算 \(\ge k\) 的方案数。
相当于对于树上任意一条链，满足颜色互不相同。可以猜结论：按深度从小到大加入所有点，加入点 \(u\) 时统计出已加入的与 \(u\) 距离 \(< k\) 的点的个数 \(w\)，那么贡献为 \(m - w\)。
考虑这样做得正确性，相当于证明已加入的与 \(u\) 距离 \(< k\) 的点颜色一定互不相同，即这些点两两之间距离 \(<k\)，这是显然的。
使用点分树查询这样的点的个数即可。
D
同 CF1466H。