64 lines
2.6 KiB
Plaintext
64 lines
2.6 KiB
Plaintext
NOIP2010解题报告
|
||
|
||
Translate
|
||
|
||
开一个队列进行模拟就行了。
|
||
|
||
PS:这题数据比较厚道，按照题目的描述来说，单词的编号是非负整数，也就是说可以是0。但是数据中并没有0，否则就要有很多人要降10分了。
|
||
|
||
Tortoise
|
||
|
||
动态规划。
|
||
|
||
用F[i1,i2,i3,i4]表示数字1的卡片取了i1张，数字2的卡片取了i2张，数字3的卡片取了i3张，数字4的卡片取了i4张，可以取得最大的分数。写起来很好写，四个for，再加上四个if。
|
||
|
||
F[i1,i2,i3,i4]=max(F[i1-1,i2,i3,i4],F[i1,i2-1,i3,i4],F[i1,i2,i3-1,i4],F[i1,i2,i3,i4-1])+score[1+i1+i2*2+i3*3+i4*4]
|
||
|
||
PS:这题用120*40*40*40，350*40*40*40的算法都是可以的。
|
||
|
||
Prison
|
||
|
||
二分+二分图判定\并查集
|
||
|
||
解法1：先二分答案，然后进行二分图的判定。判定方法如下：首先取一个没有走过的结点放在了左图，然后把和这个点有边的点放在右图，然后再把和这些右图有边的点放在左图，一直下去，知道把所有点都放好，或者出现矛盾为止。
|
||
|
||
解法2：把边权从大到小排一次序，依次插入。用并查集维护这些边之间有没有矛盾。详情看并查集经典例题：PKU1182食物链。
|
||
|
||
Flow
|
||
|
||
[(floodfill\动态规划\各种乱搞算法)+(贪心+动态规划\各种乱搞算法)]\最短路
|
||
|
||
显然第一问一次O(NM)的floodfill就可以求出是否可以到达全部最后一层的格子。现在假设最后一行的所有格子都可以到达。
|
||
|
||
定理1：从第一行的格子，可以到达的最后一行的格子必然是连续的一段。
|
||
|
||
证明1：假设格子A可以到达的最后一行中间有部分格子不可到达。由题设可知，必有另一个格子B可以到达这些A不可到达的格子。但是，显然A到达下面格子的路径必然与B到达这些A不可到达的格子的路径有重合部分，所以，A也能到达下面的A到达不了的格子。矛盾，所以假设不成立，原命题成立。
|
||
|
||
定理2：第一行从左到右的格子对应下面的格子区间的左边界和右边界必然是单调不递减的。
|
||
|
||
证明2：假设第一行有格子A、B，并且A在B左边，最后一行有格子C、D，并且C在D左边。假设A能到达D不能到达C，B能到达C不能到达D。那么，A到D和B到C的路径必然有重合的部分，所以A也能到达C，B也能到达D。所以假设不成立，原命题成立。
|
||
|
||
定理3：从任何一个格子出发，可以到达的最后一层格子也是连续。
|
||
|
||
证明3：与定理1类似，略。
|
||
|
||
上面3个定理，可以得出一个大概的算法：
|
||
|
||
第一步：先把上面每一个格子对应的区间求出来；
|
||
|
||
第二步：然后再对这些区间进行操作。
|
||
|
||
第一步方法1：枚举上面一层每个格子，进行floodfill，把下面可以到达的区间求出来。然后对于第一层每个格子，它需要枚举当且仅当它左边和右边的格子都不能到达它。
|
||
|
||
第一步方法2：从fl[x,y]表示(x,y)能到达区间的左边界，用fr[x,y]表示(x,y)能到达区间的右边界。fl[x,y]:=min(fl[x1,y1])，fr[x,y]:=min(fr[x1,y1])，条件是(x,y)可以走到(x1,y1)。转移顺序按照格子的海拔从小到大进行。
|
||
|
||
第二步方法1：贪心。
|
||
|
||
第二步方法2：动态规划。如果嫌时间多可以加上个单调队列去优化一下。
|
||
|
||
事实上这题的瓶颈在于第1步，第一步方法1是O(N^3)的，但是经过试验，我在这题加上了若干常数优化后，A掉了。详细的运行时间看下面的图片。
|
||
|
||
新增一个最短路的方法：http://hi.baidu.com/wywy/blog/item/4e937f891e75cca30f2444f7.html
|
||
|
||
附：这应该是我最后的一次NOIP的，这份也可能是我写的最后一份NOIP解题报告了。最后附上我OI生涯的最后一份成绩单。
|