TopCoder SRM600.5

jiangly · 2021-08-05 00:24:40 · 个人记录

CoinsOfByteland

显然要计算的就是满足 a[0]>a[1]>\cdots >a[N-1]>0 且 a[0]+a[1]+\cdots+a[k]\le \mathrm{maxSum}[k] 的数列 a 的数量。

数位 DP，要记录的是 a[i]>a[i+1] 是否满足以及只考虑高位的 f(k)=\mathrm{maxSum}[k]-(a[0]+a[1]+\cdots +a[k]) 的值。注意到如果 f(k)<0 则一定不合法，若 f(k)\ge k 则一定合法，因此 f(k) 只有 k+1 种取值，总的状态数为 O(2^N(N+1)!)。

转移时直接枚举每个数的取值，时间复杂度约为 O(N4^N(N+1)!\log C)。

HugeGraph

考虑算出有用的边数。

不失一般性，假设 d[0]<d[1]<\cdots<d[|d|-1]。

对于每个 d[i]\pod{i>1}，u\to u+d[i] 的边可以用 u+d[0]\to u+d[i] 替换。

所有边都替换后，前 \min(d[0],n-d[0]) 个点恰有一条边连向后 n-d[0] 个点，因此有用的边数增加 \min(d[0],n-d[0])，并将 n 和所有 d[i]\pod{i>0} 减去 d[0]。如果这时 n<d[0]，则删除 d[0]。

不断进行操作直到 d 为空即可得到答案。

快速进行对一个数的多次操作，容易发现每次操作后 d[0]+d[1] 的值减少到原来的 2/3，因此至多进行 O(\log C) 轮，时间复杂度 O(|d|\log C)。

JumpingOnPoints

线段树优化 Dijkstra。

两维可以分别维护。

线段树上维护 T[v] 的最大和最小值，更新时分 T[u]\le T[v] 和 T[u]>T[v] 两种情况考虑，在线段树上找到对应的点并删除即可。时间复杂度 O(N\log N)。