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

C++