2021牛客暑期多校训练营8

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。所以贪心即可。

暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇