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$ 类:
- 只能往下走。
- 只能往右走。
- 只能往右或往下走。
$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。所以贪心即可。