2016.10.5 NOIP模拟赛总结

SMOJ/1423 删除

我使用链表模拟操作。每一个节点储存这个节点代表的区间的左、右端点,在删除区间的时候分几种情况讨论:

  • 完全不覆盖这个区间,那就传递给右边那个区间处理。
  • 完全覆盖了这个区间,那么删掉自己,把多余的传给右边区间。
  • 不完全覆盖这个区间,又分几种情况:
    • 从左端点覆盖到中间,那么调整左端点的值到中间即可
    • 从中间一直覆盖到右端点或者更多,调整右端点,把多余的传给右边区间。
    • 只覆盖这个区间的一段,既不靠左,也不靠右,那么把区间一分为二。

时间复杂度O(D2)O(D^2),AC。

但是这题事实上有更简单的做法。

假如我们从后面的操作往前推,只需要判断两种情况:

  • 左端点小于等于m。那么我们把m加上区间长度。
  • 左端点大于m,不理他。

这样只要O(D)的复杂度即可。倒推能够简化&解决很多问题!

SMOJ/1424 巡回

除了深搜完全没有思路。

题解:找一条连着起点的边,设他的长度的两倍为w。因为走过去又走回来一次的长度就是w,位置没有变化,还是回到了起点,所以如果存在一条从起点到终点的路径长度为S,满足kw+S=Tk\cdot w+S=T,那么在出发之前走k个来回,之后再走S,总长度就能达到T。

kw+S=TST(modw)k\cdot w+S=T\Leftrightarrow S\equiv T(mod w)

就靠这个同余方程来判断是否存在这样的路径了。

我们把所有的点拆为w个点,分别代表走到这里的时候的长度模w的余数。再用SPFA,得到达到终点的时候S mod w的点是否存在和他的最短长度。如果这个最短长度大于T,那么还是不满足,因为原来的式子要求S≤T,否则一定存在这样一条路径。

那假如说不存在S使得kw+S=Tk\cdot w+S=T,一定不存在满足条件的路径吗?

k0,S0,kw+ST\forall k\geq 0,S\geq 0,k\cdot w+S\neq T

S0,0w+ST\Rightarrow \forall S\geq 0,0\cdot w+S\neq T

S0,ST\Leftrightarrow \forall S\geq 0,S\neq T

这不就是根本不存在一条路径满足条件的意思吗?

所以这个方法可行。

一些实现上的技巧

  • 为了保证拆点数量更少,我们一般选择与起点相连的最小的边,这样模出来的可能数更小。
  • 选择与终点相连的边也是可以的。不选中间是因为不保证能经过。

SMOJ/1425 优胜者

考试的时候,自然还是深搜。一分都没有得到。我其实想到了动态规划中的概率计算,但是没有成功写出来。原因是没有办法记录谁死谁活的状态。

这个状态究竟怎么储存呢?解决方法很巧妙!

fg,r,b,if_{g,r,b,i}为有g张绿色,r张红色,b张黑色时的游戏,第i个人获胜的几率。这个游戏仍然是从0开始。

为了方便阐述,我们就假设只有6个人,编号从0到5.

从头开始。

  1. 若最外层是绿色的(几率为gg+r+b×100\frac {g} {g+r+b}\times 100%),那么大家获胜的概率就相当于从另一个状态搬过来:

fg,r,b:0,1,2,3,4,5+GreenWrapperfg1,r,b:5,0,1,2,3,4f_{g,r,b}: 0,1,2,3,4,5+GreenWrapper\Leftrightarrow f_{g-1,r,b}:5,0,1,2,3,4

新的游戏又从0开始来过,但事实上等价于当前游戏的情况!

  1. 若最外层是红色的(几率为rg+r+b×100\frac {r} {g+r+b}\times 100%),做法也类似:

fg,r,b:0,1,2,3,4,5+RedWrapperfg,r1,b:5,4,3,2,1,0f_{g,r,b}:0,1,2,3,4,5+RedWrapper\Leftrightarrow f_{g,r-1,b}:5,4,3,2,1,0

整个游戏逆转过来了。当前游戏在5处继续,相当于子游戏从0开始。

  1. 若最外层是黑色的(几率为bg+r+b×100%),就有点变化了。

fg,r,b:0,1,2,3,4,5+BlackWrapperfg,r,b1:,0,1,2,3,4f_{g,r,b}:0,1,2,3,4,5+BlackWrapper\Leftrightarrow f_{g,r,b-1}:-,0,1,2,3,4

看到0被踢掉了!所有的东西自动连接成连续的并给了一个新的序号!这种方法处理这种一般链表才能处理的问题实在是高!

这三种情况得到概率之后,乘上这个概率,再加到当前状态的最终概率里面去。

绿色、红色、黑色都要从小到大推,所以动态规划轻松无压力。

但是我最后做完WA了一个点。开始怀疑数据错了,发现有人AC,闷头苦想一阵,还是没找出哪里错了。

总结

今天考的不怎么理想。总共100分,全部来自于第一题。但是输得心服口服,尤其是第二、第三题领悟了一些新思路,受益匪浅。

倒推是非常重要的思想,也是贪心问题中常用的策略。做题时一定要灵活使用!

其他题我也实在没有办法了,也没有什么数据点可以给我水,那就只能这样吧。毕竟这就是我当前的实力。

avatar
Kerry Su