比赛地址

警告:下面没有任何的证明。

Cat Snuke and a Voyage

最短路即可

判一下有没有 $1\to n$ 或者 $1\to u\to n$ 即可。后面那个可以把 $1\to u$ 和 $u\to n$ 的 $u$ 分别标记一下。

代码

Decrease (Contestant ver.)

既然是构造,那肯定令 $n=50$。

那么,我们可以令最后的序列是 $n$ 个 $n-1$,然后还原出最初的序列。

可以发现,对 $1\sim n$ 全部操作一遍后相当于每个数都减了 $1$。于是我们先给每个数加上 $\left\lfloor\frac{k}{n}\right\rfloor$。

这样子还有 $k\bmod n$ 次操作,随便找这么多个数出来模拟一下即可。

代码

Decrease (Judge ver.)

每次找一个最大的出来一直减到 $n$ 以下即可。

官方题解证明了这样子的次数是 $\mathcal{O}(n^2)$ 的。

代码

Namori Grundy

先考虑树的情况,显然叶节点只能是 $0$,所以可以直接推出根的最小权值。

再考虑环上。现在环上每个点都有一个权值 $a_u$,我们希望对其进行调整。假设环上有一条边 $u\to v$:

  • 如果 $a_u>a_v$ 或者 $a_u<a_v$,不需要调整。
  • 如果 $a_u=a_v$,则 $a_u$ 会变大。

进一步发现,当环是一个所有 $a_u$ 都相等的奇环时,无法调整得到合法方案,否则一定可以得到合法方案。

因此当环是所有 $a_u$ 都相等的奇环时无解,否则有解。

代码

最后修改:2020 年 09 月 21 日 09 : 18 PM