【[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

加入对话

8条评论

  1. 回复溟雨潇潇:这个嘛。。。就是OI的保送生有两种条件,1是NOIP 1=。2是进省队。。。我是属于没有NOIP 1=,也没有进省队的。。。我只是用夏令营名额在NOI拿了个银= =

留下评论

您的电子邮箱地址不会被公开。