Solution T01

比赛链接

ABCD略去不表

E

组合计数，动态规划。

考虑合适的计数方法使得动态规划的阶段容易确定，显然可以根据 group 大小来划分阶段。相应地，考虑将一个解中所有 group 按照人数从小到大排列，就得到了一个 n 排列的一个划分。一个划分对应的解并不是 n! 个，考虑 group 内部的排列和相同大小的 group 的排列。一个划分 F 对应的解的数量是 n!/prod((F_i)!*(i!)^(F_i))。prod() 部分很容易分配到 DP 的各个阶段。

dp(i,j) 表示划分 F 包含了 j 个人，最大的 group 大小为 i，则有 dp(i,j)=dp(i-1,j)+sum(dp(i-1,j-k*i)k!(i!)^k)，其中 C≤k≤D。注意到 k 对 i 求和是 nlogn 的，总的复杂度为 O(n^2logn)。

动态规划中通过 sum(n/i) 将状态数或者转移数从 n^2 约束为 nlogn 是比较常见的技巧，请务必掌握。

F

显然不需要走回头路，假设所经过店家的最小编号为 l，最大编号为 r。那么最优策略为 sum(max(B(l..r,j)))-sum(A(l..r-1))。

考虑 B(i,j) 的“覆盖范围”。设 B(opt,1) 为 B(i,1) 的最大值，那么显然 [1..opt, opt..n] 这 opt*(n+1-opt) 个区间都应该选择在 opt 处使用 1 号券。更一般的，对于某个 B(i,j)，假设 prev 是满足 B(k,j)>B(i,j) 且 k<i 的最大的 k，next 是满足 B(k,j)≥B(i,j) 且 k>i 的最小的 k，那么 [prev+1..i, i..next-1] 这些区间都应该选择 i 作为 j 号券的使用位置。

将上文所述的区间视为网格图上的网格，那么每个 B(i,j) 都对应一个带权矩形，而且每个 j 对应的 n 个矩形都互不相交，并集恰为整个等腰直角三角形。问题转化为给定 n*m 个带权矩形，求网格图上每个位置所盖矩形的权值和。用二维数据结构可以在 O(nmlog^2n+n^2) 的时间内完成。如果将一维或者两维用差分方法（imos method）离线求和，则可以将复杂度降低到 O(nmlogn+n^2)（排序复杂度难以避免）。