Leaf Duo

NOIP 2007 已经结束很长时间了，但是由于比赛之后一直比较忙，也比较担心获奖的情况，所以一直没有能对 NOIP2007 做一个总结，现在放假了，有了空闲的时间，来总结一下我的 NOIP 2007 。

首先说一下 NOIP 2007 对语言的使用和评测机器的要求吧。试题上有三条说明：

1. 文件名（程序名和输入输出文件名）必须使用小写
2. C/C++中函数main()的返回值类型必须是int，程序正常结束时的返回值必须是0。
3. 全国统一评测时采用的机器参考配置为：CPU 2.0GHz，内存256M。

第一个和第二个没有什么特别的，是大家应该能做到的，而且轻易能做到的。第三个说明评测机的配置不错，毕竟是 2.0GHz 的机器（比起 USACO 的 700MHz……），对于内存来说，这次进一步放宽了内存，成了 256MB ，而且没有说明程序最大使用多大的内存，所以除去操作系统使用的部分，大家的程序想开多大就开多大了，而不用顾及以前的 64MB 内存的限制。（希望我没有理解错）。山东省的省测更是搬出了一台服务器来进行评测，说明 NOIP 的机器配置已经很不错了。（省测这个可能也跟去年发生的一些事情有关）

拿到卷子，先发现的是卷子的样式跟以前的不一样了，个人比较喜欢 NOIP 2006 的样式，感觉那个更好用一些。（赛后看到电子版，竟然是 doc 文档，初赛题还是 pdf ，怎么复赛退化成 doc 了呢？）

再说一说题目吧。 NOIP 2007 的题目总体来说应该不算很难，可以说得上简单。（我都会做的题就是简单题……）所以 NOIP 2007 的一等奖分数线也就比较高了。

来说一下每个题目的具体情况吧。

第一题，统计数字（ count ）是一道说简单就简单，说难就难的题。我看完题，然后去看数据规模，看到最大是 200000 ，立即看到是个 O(NlogN)的题目，而且又是排序，没有多想，就写了了快排，还是调用标准库的 qsort() 函数，没几行就解决了，测了几个简单的数据，就 pass 了。

赛后，同学们说到有快排专杀数据的问题。我想了想，确实有这个问题，如果数据里有快排专杀的话，我的程序铁定过不了。同学们给出了他们的方法。有用 hash + qsort 的，复杂度 O(N+KlogK)；有用堆排的，复杂度 O(NlogN)；还有用二分查找（用于判重） + 快排的，复杂度 O(NlogK+KlogK)；还有其他的比较 BT 的算法就不列了。

成绩下来之后，是几家欢喜几家愁……我这个用纯快排的，100分；用二分查找 + 快排的，十个点全部错误；用 hash + qsort 中的一个，十个点全部崩栈……说明大家的编程熟练程度还需要增强，一些比较常规的算法/数据结构出现这样那样的错误是不应该的（这个也应该跟我说）。也说明 NOIP 的数据还是很弱，据同学报道大数据全部是随机数，所以我们这些直接用快排的全部通过。

不知道是应该傻一点还是聪明一点呢，傻一点碰到变态的数据就惨了，聪明一点编程熟练程度跟不上一样也是惨，而且是更惨。这是个值得思考的问题。我觉得考试的时候应该遵循 KISS （Keep it simple. stupid） 的原则，能 AC 就行。但是这道题，做的时候并不知道数据是怎样的，做到什么程度才能 AC 呢？

第二题，字符串的展开（ expand ）是个纯粹的字符串处理。用 Pascal 的不知道怎么样，不过用 C 的同学们就要面对那复杂的字符数组了（或许大牛们认为不复杂），而我就隆重推出 C++ 的 string ……虽然效率不高吧，但是还是非常方便的。（这个题肯定不会让你 TLE 的，除非你人品有问题，死循环了）

然后开始写……我是这样写的……

其实吧，上面的段文字吧，重复了我比赛时犯的错误……没事用什么字符串啊，直接读入读出不久 OK 了 ？（事实上，用 Pascal 的同学和没有考虑到结果串长度的用 C 的同学们的结果串可能会溢出的，偶这用 C++ 的又偷笑了……）

修改之后主要用到了三个字符型变量，分别存光标前一个字符、光标所指字符和光标后一个字符（这里的光标是逻辑上的，不是指流中所指的当前字符）。然后我们开始处理，如果当前字符不是减号，那么直接输出前一个字符，然后前进；如果当前字符是一个减号，那么按照题目所述输出若干个字符，这里我本想写一个函数进行输出，实际编码时放弃了，现在想想，写成一个函数还是很好的，这样就避免了代码的大量重复（当时这段代码大概复制了三遍）。输出的具体方法就是一个三重的循环，内含一些判断，具体就不说了……之后向后跳两个字符（是两个字符……）。最后加上了对开头字符和结尾字符的特殊处理，测了几个正常的数据，又测了几个比较变态的数据（预想到这种题的数据肯定不会正常……），全部正确，然后就 pass 了。

值得一说的是，赛后了解到同学们大部分都是自己判断这个字符是字母还是数字，是大写还是小写，并且自己进行转换。我写的时候用的是标准库中提供的函数：isdigit() isalpha() isupper() islower() toupper() tolower() ，这些函数都在 cctype 中（ C 语言是 ctype.h ），具体用法可以参考这里。用这些函数可以省去自己写代码的麻烦，避免了万一写错的风险，也使得代码更加简洁明了。（我想，这些函数的速度应该不会很慢，即使慢，又如何呢？这个题是不会卡时间的）

后来知道，我这个题得了 90 分，说明当时思考还是比较严密的。当然，数据的变态程度超出了我的估计……不过我的程序在我没有想到的情况下战胜了这些变态数据，说明解题思路还是不错的……（错了一个点，我忍……）

第三题，矩阵取数游戏（ game ）是一个动态规划+高精度。我的高精度总是出错，所以考试的时候觉得拿到 60 分就走人。然后开始考虑动规，其实这个动规也挺简单的：鉴于每行之间互不干扰，我们分开求。对于每行，定义状态 f[i][j] ， i 表示从左边取走的数的个数， j 表示从右边取走的数的个数。定义 f[0][0]=0 。每次要么从左边取，要么从右边取，所以 f[i][j]=max{f[i-1][j]+data[i]*pow(2,i+j),f[i][j-1]+data[m-j+1]*pow(2,i+j)}（2的乘方可以拿个数组来存一下）。所求最优解就是满足 i+j ==m 的 f[i][j] 的最大值。然后将每行的最优解加起来就可以得到最终的答案。

但是天知道考试的时候怎么了，我就是想不出来这个题应该怎么写了，于是乎，贪心之……发现样例就有反例……再于是乎，搜索之……看起来一般的搜索是对不了了，所以我们随机化地搜索，就是说每次的取法是随机的，然后测试很多很多次，每次更新当前最优解，看看能不能碰上最优解，能碰上就得分了……当然还得加上卡时，到 950ms 之后我们退出走人，防止 TLE …… 后来还有半个小时的时候，我良心发现，写了一个正常的搜索，但是遇到了十分诡异的错误，一直调不好，一直说有语法错误，这怎么可能…… 最后就把随机搜索的程序交上去了。

省测这个题一分没有得，没办法，谁让这个算法就是碰人品呢……不过倒是过了送交全国的线，期待着全国测…… 出乎意料的是，全国测人品爆发，过了三个点，恰好卡线过，拿到了一等奖…… 随机算法（主要指不太正常的“随机算法”）在实在不会了，准备骗分的时候还是十分有用的，这比一般的随机数得分应该会高一些…… 随机万岁！

拉回来，我们看第四题，树网的核（ core ）这题没什么好说的，因为我到现在也没看懂题，也不知道怎么做，当时就只是输出了 10 以内的随机数了事，结果一分没有……

或许过一段时间，再开始做题的时候会看看它吧。（我从比赛回来到现在也没有做过题）

题目基本上说完了，再说说赛前的准备。

这个我们从很久很久以前说起……

其实，开始学 OI 是从初一下学期，那时候有个什么什么考试，好像是程序设计培训的班的一个什么选拔考试。有点兴趣，就去考了，传说中还考了市中区还是济南市的第三名……不过最后没有去上，原因我也忘了，大概是没时间或者不想去吧。班里一个考了第八的去了，每次回来问我代码该怎么写。那时候他们学的是 Pascal ，我就给她写了，都挺简单的，就是基础的语言，什么水仙花数、金字塔什么的（传说中我那时还会写 Pascal ，现在只会看了……），然后自己也算是学会了一点 Pascal。还是初一下学期，开始学 C ，看的是谭浩强的《C程序设计》，我们那时候还只有第二版，现在高一的同学们都拿到第三版了，至于这本书的好坏，不做评价，因为看完一遍之后再也没看过，初学时候看的书，没法评价……看完之后，算是基本上会简单的 C 了。

之后是初二，NOIP2004 ，120分，济南市一等奖（相当于没有的奖）。开始学 C++ ，是从会用流开始，之后看了 OOP 和 STL ，不过至今也没写过什么 OOP 的程序， STL 也是略知皮毛，不过 C++ 确实挺方便灵活的。之后就没有什么太大的进展，算法就会排序，还是选择排序或者冒泡排序。初三， NOIP2005 ，100分，济南市一等奖。

初中只是学会了语言，不过掌握还算是牢固，到了高中基本上没碰上什么语言问题，应该说在同学中也算比较好的（自夸一下……）

毕业之后光玩了，没学东西……

刚上高一， NOIP2006 报名，我报名了，然后星期六下午开始加课辅导，一开始主要将初赛内容…… 然后初赛轻松地过了，之后准备复赛，学了半天，发现什么都不会，没办法，也只有去考了……回来发现， 10 分，三等奖……（这不公平，有的得10分的是二等奖……）一等奖分数线，没记错的话是 100 分。

然后又基本上把 OI 放下了，说是基本上，就是说也有的时候看看，虽然没背过什么算法，也不会写什么数据结构，但是起码有了个了解，知道该学什么了。

暑假的夏令营，我去了，感觉自己的水平是最差的，但是还是学到了些东西，会了点 DP ，会了点搜索，会了点并查集，会了点……

回来，开学，备战 NOIP2007 ，我还是以学习为重，搞 OI 的时间不多，只是抽出一些比较不重要的课和校本课程（本来就该学 OI 的时间）。初赛，由于对它不够重视和身体原因华丽地挂掉了。不过最后通过努力还是去了复赛。 NOIP2007 的时间也是我们学校期中考试的时间，所以我们期中考试就不用考了，相应地，也就不用复习了。 比赛前两星期，跟老师请假不上晚自习，开始不做作业，晚上回家只是学 OI ，白天好好听课。直到比赛前两天，所有科目都已经结束功课，开始复习，我待在班里已经没有什么短期的利益了，所以跟老师请假，转战机房。而这时候，其他的同学们已经在机房呆了少则几天，多则一星期（可能是一星期吧，我不常去，不清楚）。

我之所以以学习为重，是因为对 NOIP2007 没有抱太大期望，感觉自己水平不济，想 2008 再来。

考前，搞了一份资料，看了看主要算法的标程，做了几个动规，然后就拿了很多书和资料上火车了。火车上，看了看自己的资料，也参考了一下其他人的，讨论了几个题，就到了日照。

签到，住下，吃饭，试机，机器非常好。第一天晚上，大家都早休息了，为明天做准备。第二天，早起，吃饭，比赛……

看到卷子，越做越高兴，因为觉得挺简单，做得挺开心，瞬间驾驭代码的能力飞速提高……说明好的心情也是非常重要的……对提高你的成绩有很大帮助。做题时的时间分配已经记得不是很清楚，大概第一题半小时（或许不到），第二题一小时多（加上调试吧），剩下的就差不多是第三题了。嗯，大概是这样的了。还剩五分钟，多拿分已经没有希望，保存，确认，再打开，确认，再确认，看注意事项，再确认……最终交卷了。（其实说离场更准确些）

之后疯玩，大家的本子上的游戏发挥了作用，还有人带网线了，可以联机 CS 了…… 有带网线的，真后悔没带路由器过去…… 玩，玩，玩，发成绩，高兴，叹息…… 接着玩…… 坐火车回家，当然还是玩……

回到了济南，之后是等待，等待，直到全国测成绩公布，期待，期待，直到一等奖名单公布，高兴，高兴……

给新来的 OIer 一个建议吧，认真 OI ，认真学习，认真做人……

我没有完全做到，或者说做得很不好，以后努力。

就写到这里吧，也不少字了，以后再有什么东西以后再写。

仅仅是我自己的一个总结，各位神牛、天牛、大牛就不要砸鸡蛋了……（建议用西红柿代替）

ps1：谁给 noi.cn 做个镜像啊，我表示十万分的感谢…… noi.cn 的 downtime 之长是在令人发指……

ps2：写的时候，因为年代已经比较久远，思维可能比较混乱，所以如果有错别字或者其他错误还请指出，谢谢。

ps3：感谢您能读到这里……

ps4：我也不知道为什么会这个时候写完，不过就是这个时候写完了，所以顺便祝大家新春愉快，万事如意！

Tags:C++,OI

Related Posts

• clock() in C++ (0)
• 看看我的计算机 (1)
• 我的成绩变成220分了 (5)
• 开学了 (1)
• 回答问题 (8)