AC 代码

A. Ares, Toilet Ares

虽然这题出题的本意是好的，但是英语水平堪忧，只能说也是个脑瘫谜语题。

读懂之后就是个签到题，但是要注意特判去厕所获得 0 行代码的特例（不管有没有成功都不会对结果产生影响）。

D. OR

可以对每一个二进制位进行分析，可以得出左右两边 1 的数量之和。然后从头精选枚举取值的可能性即可。

E. Rise of Shadows

签到。

cout << "No\n";

				

					
				
				

					
				
				

					
				
				

					
				
			

F. Robots

给定一个带障碍物的 $N\times M$ 网格图，$Q$ 次询问。

每次询问会给定一个机器人，你要判断这个机器人能否从点 $(x_0,y_0)$ 走到点 $(x_1,y_1)$ 。机器人一共有 $3$ 类：

1. 只能往下走。
2. 只能往右走。
3. 只能往右或往下走。

$N,M\leq 500, Q\leq 5\times 10^5$ 。

$N,M$ 较小因此考虑 bitset 优化。

先将所有询问离线下来，然后反着做，判断能否从 $(x_1,y_1)$ 回到 $(x_0,y_0)$ 。这样做的原理是一个简单的 dp，假设 $dp [i][j]$ 表示第 $i$ 行第 $j$ 列能到达的所有坐标的集合，那么 $dp [i][j] = (dp [i][j-1]\ |\ dp [i-1][j])$ 。

这虽然是一个二维的问题，但实际上我们可以将二维的网格映射到一个 $N\times M$ 的一维 bitset 中。然后注意到这个 dp 可以通过滚动数组优化掉一维空间，就可以在 $O (\frac {N^4}{\omega})$ 的时间内解决本题。

J. Tree

设 $s$ 到 $t$ 的路径为 $p$，则一旦其中一个人离开这条路径，两个人就无法互相影响，此时两人都只需要考虑走最长路即可。
可以考虑使用双指针维护，当两人位置在 $stdl,stdr$ 时，当先手离开时，后手最大值为 $max_{stdl+1}^{stdr} dp [i]+stdr-i$，后手先离开，先手最大值为 $max_{stdl}^{stdr-1} dp [i]+i-stdl$。
我们通过维护两个从中间向两边走的指针，同时维护两个需要询问的最大值即可。

K. Yet Another Problem About Pi

考虑花费长度带来最大的收益。花费 $w$ 收益为 2，花费 $\sqrt {w^2+d^2}$ 收益为 3。所以贪心即可。