Codeforces Round #724 Omkar and Forest 题解 (Java/C++)

题解

有两个结论:

  1. 对于图上任意一个点,假设这个点的值为x。则从这个点出发一定能找到一条路径使这个路径上的值为:[x,x-1,x-2,...,2,1,0]。
    根据题目中第二个条件,这个结论是显然的。
  2. 从图上任意一个值为0的点出发,走x步后,所在的位置的值最多为x。
    根据题目中第一个条件,这个结论是显然的。

于是我们就可以根据上面两个结论得出任意一个值不为0的点的值域:

  1. 根据结论1。我们知道$x\geq \min{(dis\_to\_0)}$。也就是x的值大于等于这个点到最近的一个0的距离。
  2. 根据结论2。我们知道x其实的值最多是这个点到最近一个0的距离。

于是我们得到,任意一个点的值其实必然等于这个点到离他最近的0的距离。于是所有非0点的值其实完全由为0的点决定。

于是我们只需要枚举#中有哪些是0即可。于是就是$C_n^0+C_n^1+C_n^2+...+C_n^n=2^n$。
另外,如果本身就全是#的话,因为不能选择$C_n^0$所以要减1。

代码

Java

Submission #118809046 - Codeforces
Codeforces. Programming competitions and contests, programming community

C++

Submission #118809293 - Codeforces
Codeforces. Programming competitions and contests, programming community
展示评论