2016.10.4 NOIP模拟赛总结

SMOJ/1419 受欢迎的奶牛

考试的时候蒙了一个满分。我反向建图,然后从每个点开始DFS/BFS,如果所有的点都能够遍历到,那么说明这个点是受欢迎的点,否则就不是。我还加了一个小优化,就是每当你遍历到一个受欢迎的奶牛,那么你也肯定受欢迎了。这个优化对于没有受欢迎的奶牛的图没有效果,不过因为不能遍历到全部,所以本身遍历的节点数量不是很多;但是假如说有成群的受欢迎就可以大大减少时间。

正确的做法

首先缩环。原来的图就变成了一个DAG(有向无环图),找没有出边的点。

  • 没有:这是不可能的,全部都有出边的话就不再是一个无环图了。
  • 有且仅有一个:这个点/环就是所找的受欢迎的奶牛,它的大小就是答案。其他的因为都有出边,怎么样都会最终指向它。
  • 大于一个:大于一个的无出边的点说明这些点之间不可能互相喜欢,所以受欢迎的奶牛个数就为0.
    时间复杂度O(n)O(n)

SMOJ/1420 交通灯

考试的时候自以为会了,硬上SPFA,找灯那里连续迭代三次,再不对就认为不可能到达了。结果WA了一个点,95分。

SPFA非常好想到,dis记录到达的时间,可以证明时间更新为更早的不会影响到最终的最小值。

问题就在于求当前节点和所连边节点下一次灯颜色相同的时间。不妨设它为nxt吧。

我们考虑从时间0开始:

  • 如果两个灯初始颜色相同,nxt就为0;
  • 如果两个灯初始颜色不同:
    • 如果两个灯初始颜色维持时间不同,nxt为较小的那个;
    • 如果两个灯初始颜色维持时间一样:
      • 如果两个灯第一个颜色的长度不一样,nxt为初始时间长度+较小的那个;
      • 如果两个灯第一个颜色长度还一样:
        • 如果两个灯第二个颜色长度不一样,nxt为初始时间长度+第一个颜色时间+较小的第二个颜色时间;
        • 如果两个灯第二个颜色长度一样,完了,两个灯颜色永远不可能一样。

几个if就搞定了。

如果时间不是从0开始,那就把前面的减掉,情况还是一样的。

SMOJ/1421 栅栏

我之前在书上看过这道题!但是还是没做出来!只用动态规划水了56分……我很明确地想起这道题要用线段树,一看坐标范围,105AiBi105-10^5\leq A_i\leq B_i\leq 10^5,如果要开线段树,岂不是要开一个101010^{10}的数组,果断放弃之!

考完试,脑袋清醒一点才发现,只要开2×1052\times 10^5大小的数组就够了……本来可以轻松AC的啊!

以坐标建线段树,一开始全部设为0。从下往上,从1到n扫描,碰到第i条边,记录它的左端点在线段树上的数,记录它的右端点在线段树上的数,再把这个区间用i覆盖。这样做之后能够得到从每条边的端点往下一直走能够走到的边。

因为奶牛只会绕到端点之后一直往下走,碰到栅栏之后再选择往左右端点走,这实际上也是x方向上路程最短的走法,我们可以给每个端点往下走到的线段的左右端点与该端点连边,之后再用SPFA。事实上,这是个DAG,所以动态规划也能解决这个问题。我在考试的时候的做法就是暴力找出这个往下到达的端点,达到了O(n2)O(n^2)的复杂度。

一些实现上的细节

  • 0号栅栏的左右端点可以设置为(0,0)(0,0).
  • 假如说你从一个边界一直往下走到了另一个边界,其实是不用处理这种特殊情况的,因为路程不会增加。

总结

这天的模拟题总分达到了247,但是其实本来可以更高的。主要问题出在了审题。比赛的时候要多走走,多出来上厕所,才能清理思路,发现错误的地方。

avatar
Kerry Su