8.8~8.9长郡NOIP模拟赛总结

在两天的选拔赛后,周一周二这两天进行了一次较为轻松的NOIP模拟赛。

这次考试的结果如下:

rank

排名似乎还能看,不过实际上并没有考好。换言之大家都考的不是很好。

把六道题目分别分析一下:

1.折纸(paper)

讲道理这道题绝对是个送分题,只要看懂题目了再注意一下数据范围肯定可以AC。

很多人没有考虑到\(xfold>width/2\)的情况,而事实上如果看了数据范围会发现这样一句话:

\(0<=x1<x2<=max(xfold,width-xfold)\)

后面那部分明显暗示可以折过去啊。。所以第一题主要就是看有没有把题目读懂。

2.二叉查找树(bst)

实际上这道题也是送分题。HNOI以前的若干题比如营业额统计以及宠物收养所和这道题并没有什么区别。

通过分析插入节点的方式我们可以发现插入的每一个点要么是在前面比它大的第一个数的左儿子,要么是在前面比它小的第一个数的右儿子。

也就是要使用数据结构维护当前数的前驱后继。平衡树显然可以做到。

当然很多人就是写的平衡树,或者直接用STL中的set,然而考虑到评测机的常数巨大,平衡树非常危险。。果不其然平衡树被或多或少地卡掉了几个点。

唐旻鹏写的线段树,利用线段树的结构特点避免了二分,或者说是维护了二分结构,常数比平衡树小了很多。

考虑到这道题中数字的权值范围只有\([1,n]\),我写了两个树状数组维护前缀最大值和后缀最小值,由于这道题只需要插入不需要删除,所以能够维护最大最小值。常数显然比线段树更小,实测跑的也更快。

当然还有李淳风的复杂度更优的\(O(n)\)并查集做法,不过因为爆栈RE了一个点。改成非递归版的肯定跑的最快。

所以这道题题目并不难。。但是想AC还要优化常数。

3.游戏(game)

这道题是D1有难度的一道题。不过说难其实也难不到哪里去。

题意不难理解,也很容易想到dp或者记忆化搜索。然而我在设计状态的时候只搞了一维,另一维如果是卡片的选取情况显然存不下。。于是一直纠结转移时会发生的错误。。然而没有想到只需要存对当前数字无影响的卡片个数就可以了。

于是打了个暴力。。其实这个暴力没有记忆化应该是没有分的,不过为什么得了20分呢?

233就是这一句话:

暴力部分数据里所有\(n>20\)的结果都是\(1\),特别是第二个点所有的结果都是\(1\)。。

实在是运气太好。。

4.立方体(cubes)

这个题的数据范围如此之小,显然暴搜。并且听说是白书上的原题。

每个立方体旋转出不同的形状共24种,固定第一个并枚举其它立方体的旋转方式,然后对于每一面将所有的立方体的颜色刷成当前颜色最多的一种。不断更新答案即可。

可以预处理给每种颜色编号,避免频繁地进行颜色相同和不同的比较。

复杂度\(O(24^{n-1}6n)\)。

AC人数不多,0分的不少。

5.匹配数(patterns)

一开始看错题目了,没有很懂这个题要干什么。。这道题的题面没看几眼,因为看到最后一题很可做就去先做最后一题了。结果一直做到考完都没回来再看一下这个题目。

这题的做法好像有好几种,但也大同小异。最简单的感觉是状态压缩一下,用\(dp[i][S]\)表示到第\(i\)个字符与哪些模式匹配的方案数。枚举当前位是什么字母转移即可。

这道题不难,然而根本没有动这道题,的确是很大的失误。。还是应该把所有的题目都看懂了再决定做题顺序。

6.Byte大陆(byteland)

这道题对于正解的暗示其实很明显。

求最大距离的最小值,显然是二分答案;\(n\)个点每个点连出一条边,是一个基环外向树,显然只需要拆环成树就可以了。

不过考试的时候不知道自己是怎么想的,感觉拆环似乎有些麻烦。。于是换了个思路,因为数据范围不大,往网络流方向想。

首先floyd求出点之间的距离,然后二分答案,那么如果某一个点\(i\),有另一个点\(j\)到它的距离小于二分的答案,那么在\(i\)处建堡垒就可以覆盖\(j\)处。那么在\((i,j)\)之间连边。问题转化为,选择一个点可以覆盖它相邻的点,求覆盖整张图的最小点数。

想了半个多小时没有想出怎么建网络流,这个时候突然想起了NOI2008志愿者招募的加强版。和当前的模型似乎并没有很大区别?

这道题想象成有\(n\)个志愿者,能到达的点为能工作的时间,所有志愿者的费用均为\(1\),共有\(n\)天需要志愿者,每天需要的人数为\(1\)。

那么就可以直接用那道题的方法,建立线性规划,用单纯形法解即可。

不过在今年的集训队论文中这个方法被指出了问题,也就是说志愿者招募加强版实际上没有正解。但如果不是构造数据卡这个算法的话,它的正确率还是极高的。所以这道题用这个方法可以AC。

不过我只得到了30分。。最后没有时间检查了犯了两个错误:

题目中点的编号从\(0\)开始,我在第二行数据特判了而第四行没判。然而过了样例。

我二分答案的上界设成了\(n\),因为忘记了边有边权。然而过了样例。

所以说样例不可信。。还是需要造数据对拍的。(不过也没时间写拍了)

 

总之,这套题没有特别难的题,我的理想得分应该上500。D2的时间的确是不够用,不过写了第二题再写第三题暴力总共就有250分了。

NOIP的题目不会很难,不过一旦写错一道题多辄100分就没了。。

去年王队也就是因为D2T1想成了贪心没有拿到高分。

在这次考试中很多人也因为这样那样的原因没有获得理想分数。归结起来,避免这类问题发生的方法也就几种:认真看题,仔细写题,写拍。这样在NOIP中就能稳定得分。

4
说点什么

1 Comment threads
3 Thread replies
0 Followers
 
Most reacted comment
Hottest comment thread
3 Comment authors
Recent comment authors
  Subscribe  
最新 最旧 得票最多
提醒
游客

我做过这套题啊。。T6模拟退火裸题啊

游客

正解是树p的说,拆掉环上一条边然后树上花式dp