比赛地址

Prime Minister

贪心地选所有能选再判断即可。

要搞清楚严格大于一半至少两倍这种词语的意思。

代码

WOW Factor

设 $f_i$ 表示 $s_{1..i}$ 中有多少个 vv 串,$g_i$ 表示 $s_{i..n}$ 中有多少个 vv 串。

然后在每个 o 处累加答案即可。

代码

Tiles

观察样例可以发现答案为 $2^{w+h}$ ,快速幂计算即可。

感性理解:当第一行和第一列被确定时整个图就确定了。

诡异的代码

Prime Graph

取边数 $m$ 为最小的 $\geq n$ 的质数。

首先连 $n$ 条边,将整个图连成一个环。这样子共有 $n$ 条边,每个点的度数为 $2$ 。

然后再连 $m-n$ 条形如 $(i,\frac{n}{2}+i)$ 的边。这样子共有 $m$ 条边,每个点的度数为 $2$ 或 $3$ ,满足条件。

因为不存在 $n\leq 1000$ 使得 $[n,\frac{3}{2}n]$ 中不存在质数,所以这个做法是对的。

代码

Archaeology

还是比较好想的,但是想错方向就会很难受...

维护两个指针 $i,j$ ,一开始分别为 $1$ 和 $n$ 。

然后每次讨论一下:

  • 如果 $s_i=s_j$ ,把这两个字符丢到答案里去,然后 ++i,--j
  • 否则只会有三种情况:$s_{i+1}=s_j$,$s_i=s_{j-1}$,$s_{i+1}=s_{j-1}$ 。根据不同的情况移动指针即可。

可以证明这样子一定可以得到满足条件的解。

代码

Short Colorful Strip

还是有点难度的。

设 $dp_{i,j}$ 表示 $[i,j]$ 涂完的方案数。

设 $[i,j]$ 内最小的颜色为 $c$ ,它的位置为 $p$ 。

第一次一定涂了 $c$ ,那么只要枚举第一次涂了哪一段即可转移。

$$ dp_{i,j}=\sum_x\sum_ydp_{i,x-1}\times dp_{x,p-1}\times dp_{p+1,y}\times dp_{y+1,j} $$

这样子是 $O(n^4)$ 的,并过不去。

但是可以发现 $x$ 和 $y$ 是独立的,于是就可以优化到 $O(n^3)$ 了。

代码

Short Colorful Strip

到这里我就不会做了 QAQ

考虑优化上题的做法。

首先可以发现,一个同色段可以只保留一个,对答案是没有影响的。

这样处理后,如果长度 $m$ 仍大于 $2n$ ,则一定无解,直接输出 $0$ 即可。

无解的原因是每次涂色最多增加 $2$ 个相邻的不同颜色。

那么现在 $n,m$ 同阶了。

沿用上题的做法。设 $[i,j]$ 内最小的颜色为 $c$ ,它出现的最前的位置为 $p$ ,最后的位置为 $q$ 。

考虑转移。

显然如果 $p<i$ 或者 $q>j$ ,那么 $dp_{i,j}=0$ 。

否则枚举涂了哪一段,容易得到

$$ dp_{i,j}=\sum_x\sum_y dp_{i,x-1}\times dp_{x,p-1}\times dp_{q+1,y}\times dp_{y+1,j}\prod_k dp_{p_k+1,p_{k+1}-1} $$

这里的 $p_k$ 表示 $c$ 出现的所有位置中的第 $k$ 个。

可以发现 $x,y,k$ 都是独立的,于是直接 $O(n^3)$ DP 即可。

代码

The Awesomest Vertex

好神仙啊...

所以咕掉了

Stock Exchange

完全不会,欢迎催更。

最后修改:2019 年 09 月 27 日 01 : 40 PM