比赛地址

Range Product

简单讨论一下即可。

代码

Box and Ball

简单模拟一下即可。注意盒子里仅有一个球的情况。

代码

Knot Puzzle

能全部解开当且仅当存在两条相邻的绳子满足长度之和 $\geq L$。正确性显然。

代码

Stamp Rally

先考虑怎么算从 $x,y$ 出发最多能到达的点数。显然,如果 $x,y$ 连通,则为 $sz_x$,否则为 $sz_x+sz_y$。这里的 $sz_x$ 表示 $x$ 所在连通块的大小。

考虑单组询问时的做法。二分答案,判断仅用边权 $\leq mid$ 的边能否到达 $z$ 个点即可。可以方便的通过并查集维护。

多组询问的话就只需要改成整体二分就好了。对应地并查集应支持撤销操作。

代码

Candy Piles

下文中图片均来自官方题解。

我们把 $a_i$ 从大到小排序,然后把整个序列看成这个样子:

example

那么取走最大的一堆相当于拿掉最左边一列,所有堆减一相当于拿掉最下面一行。

我们把这个东西看作一个网格,那么游戏相当于每个人可以向上或向右走一格,谁先到边界谁就输。

这样子就能得到一个暴力做法了:把边界上的点设为必败点,然后递推推出每个点的是必胜还是必败。

考虑一些优化。我们打一个表出来可以发现除边界外,每条对角线上的胜负状态相同。

而我们要求原点的胜负状态,那么只需要找到最大的 $(x,x)$,通过计算它向上、向右能走多少格,就可以算出 $(x,x)$ 的胜负状态从而得到答案了。

example

代码

Leftmost Ball

考虑最后的序列,可以发现有 $n$ 个白球和 $n$ 种其它颜色的球,其中每种其它颜色的球各有 $k-1$个,而且任意一个前缀中白球的数量均大于其它颜色的种类数。

考虑 DP。设 $dp_{i,j}$ 表示序列中已经有 $i$ 个白球和 $j$ 种其它颜色的球的方案数。我们强制 $j\leq i$。

考虑转移。为了避免算重的问题我们强制在从左往右第一个空位放球。

一种转移是放一个白球。另一种转移是放一种新的种类的球:我们需要先选出一种颜色,然后再把一个求放在最前面的空位,然后把剩下的球放在后面的空位。综上不难得到

$$ dp_{i,j}=dp_{i-1,j}+dp_{i,j-1}\times(n-j+1)\times{n\times k-i-(j-1)\times(k-1)-1\choose k-2} $$

边界为 $dp_{i,0}=1$,答案为 $dp_{n,n}$。注意特判 $k=1$ 的情况。

代码

最后修改:2020 年 01 月 12 日 09 : 46 PM