2020 ICPC Shanghai Site

发表于 2021-10-27 分类于 XCPC

链接

$\frac{nm}{2}$ 这个限制启发我们，如果将原图所有的点的情况反转，那么可以发现总和是一样的。

那么就可以了。

考虑数位DP，设 $f_{i,j_1,j_2,k}$ 表示考虑到第 $i$ 位，第一，二个数是否打破限制，前面是否都还为 $0$ 的总和。

时间复杂度 $O(T\log n)$。

二分，算出左，右两边的人在 $mid$ 时间内最远能到哪个位置。

注意，当两个人位置一样的时候，你不知道哪个人在左边，所以需要两边都算。（否则会得到一发罚时）

要使得 $a_i>\min(a_{i-k},a_{i-k+1},\cdots,a_{i-1})$，最难处理的是 $1$。

显然，$1$ 要放在前 $k$ 个位置中的一个，假设为 $i$，那么变成 $n-i$ 的一个子问题。

设总方案数为 $f_n$，有DP式：$f_n=\sum_{i=1}^{\min(n,k)}\frac{n-1}{i-1}\times (i-1)!\times f_{n-i}$

化简后，前缀和优化即可。

时间复杂度 $O(n)$。

除了前两个，以后都是奇偶相间。签到题。

显然第 $i$ 个人一定对应着第 $(i+j)\bmod m$ 个菜。

暴力枚举 $j$，设往左转了 $x$ 个，那么往右转的度数 $y$ 也能算出来，用 $x+y+\min(x,y)$ 对答案去最小值。

排序即可。

时间复杂度 $O(m^2\log m)$。

这题花的时间有点多，需要静下时间来写写式子才行。

主要看圆上两个点 $(\cos\frac{2\pi i}{2m},\sin\frac{2\pi i}{2m})$ 和 $(\cos\frac{2\pi j}{2m},\sin\frac{2\pi j}{2m})$ 间的弦长与 $2$ 谁大。

算出来之后，理论上就可以 $O(1)$ 计算了。

如果找到一条颜色相间的简单路径，再找到一条边，使得该边的端点为该路径终点和路径上的一条边，那么就一直走这个环，就找到答案了。

将同色边拿出来，将异色边建出一个图。

每次询问一个同色边 $(u,v)$，问异色图中是否存在依次经过 $0,u,v$ 或 $9,v,u$ 的简单路径。

建出异色图的 dfs 树。

分三种情况：

$u=0$ 或 $v=0$，则两点在异色图中连通即可。
$\text{lca}(u,v)=u$ 或 $v$，那么与 $0$ 连通即可。
当不满足上述情况时，设 $w=\text{lca}(u,v)$，我们要不经过 $w$ ，到达其中一个点（不妨为 $u$），然后从这个点回去 $w$，再去走到另外一个点 $v$。

这相当于从 $fa_w$ 到 $u$ 有两条点不重复的路径，即在同一个点双上。

时间复杂度 $O(n\log n)$，主要在lca上。

~~过了之后发现自己写的是边双。。。这都能过~~

首先，一个非常显然的结论是，最多只可能选择一个中转点。

当 $\gcd(n,m)=1$ 时，不需要选中转点。

否则这个中转点一定在 $y=\frac{m}{n}x$ 附近，且不在上面。

枚举即可。

签到题，用map维护字符串建出树，树形DP即可。