【[NOIP模拟赛]东方幻想乡系列模拟赛 Stage.3】小结

【题目链接】http://imnettle.net/contest/problemlist.asp?stage=3
里面Download里有完整的包~~
这套题目感觉上出的还是比较好的。
然后我自己做得了300分。。。
原因是第三题mokou。。。样例的边权是整数。。。然后没看清，直接就用了int存。。。但是实际上，是实数，于是爆0
然后下面写个简单的题解：
1、tenshi。二分答案然后由于每个1都要被覆盖，所以验证时，每次找第一个未被覆盖的1，然后把连续的长度为答案的1都删掉。如果覆盖次数<=k。那么可行。
2、reisen。这题一看就是动态规划。。。F[i][j][k]表示第i个时间，这一步走到j，走到j之前在k上的概率，然后加法原理一下就能解决。
3、mokou。就是最小生成树以后在树里统计。设d[x]表示以x为根的子树的所有边权之和。然后枚举切割点。然后向下的边每个分出一个区域，如果x不为根，那么x向父亲那边也构成一个区域。而这个区域的边权则为树中所有边权和-d[x]。最后模拟求方差即可。
时间复杂度O(m lg m+n)
另外纠正出题人题解一个错误，n比较大不是不能用prim，用堆或线段树优化以后还是可以的。
4、akyuu。先建图，图中的边表示第i组和第j组相斥。那么问题变为求任意图的最大独立集。
这个有几种做法：
一、若二、爆搜+调搜索顺序+最优化剪枝+Dancing Link。(我写的就是这种。。。)
三、这个解法来自WJBZBMR，名曰“分二乱搜”。。。实则就是把20个点分出来。
然后用二进制表示这20个点的某种取舍情况下，最大独立集是多少。然后在搜剩下的点。对于另一一边搜到的一个独立集，到这20个点里面把有边相连的点去掉，剩下的点全部取，接着就可以利用前面那个二进制得这种情况的最优解。
实际上第三种解法可以与前两种结合，理论上能使一个方法搜多20左右。
我再讲讲我的优化策略吧。
首先，我把所有点按在图中的度从大到小排序，然后从前往后进行选与不选的搜索。这样做的根据是如果我选取了这个点，那么就可以排除最大量的点，减少搜索量。
接下来，我有两个参数，cnt和rest。cnt表示现在已经取了多少个点。rest表示除了已经选的和排除的以后，有多少个点。于是如果cnt+rest<=ans，那么可以退出了。
最后，我用了Dancing_Link。每次调用dfs，都直接跳到下一个没选的地方。
最终所有数据都是0.01s过掉了。（没有加上WJMZBMR的方法）
【CODE】
[tenshi]http://xiudaima.appspot.com/code/detail/3117006
[reisen]http://xiudaima.appspot.com/code/detail/3226001
[mokou]http://xiudaima.appspot.com/code/detail/3122006
[akyuu]http://xiudaima.appspot.com/code/detail/3201003