我的Noip 2013——算是比较满意

经过昨天艰难地来到了成都,略作整顿后,今天上午就参加了第一天的Noip竞赛。不过今天确是以遗憾告终T.T 原本不该错的地方大意了。

不过再怎么也比去年直接把题读错了的遗憾要小得多,总之,祝我明天发挥好!一等奖恐怕已经无缘,但二等奖是很有希望的!上帝保佑

Day 1,充满了遗憾

早上6:20,起床、吃饭、坐车,一切都和去年一样。简单的吃了点稀饭面包,就打着哈欠来到考场,迎接Day 1的检测

话说回来真心伤不起,除了Noip还有哪科竞赛是考2天,共7小时,但只有6道题,总分600分的 -。-而且就像奥数一样,做不来就是做不来,再怎么想也想不出来。再加上整个考场大家都摒住了呼吸,能听见的全是“霹哩叭啦”个不停的键盘声。。。各种压力山大幽灵

不过这场考试我倒是静下心来全部做完了的,3个半小时时间还是不够啊。

整个考场最看不惯的就是那些“装B大神”了,比如坐我对面那位,啪啪啪啪键盘故意按的特响,而且一直不停,似乎自己很厉害的样子。则都还好,关键是嘴里还不停地叨唠着诸如“耶”、“嗯”、“哈”、“呃”,这些意义不明的字眼。。。弄得周围的人都很不爽,而且看起来他做得也不怎样,应该还不如我

第一道题

第一道题都是最简单的,但我去年就是因为太轻视而把题都给看错了,遗憾到爆!这回认认真真的把题读了很多遍,虽然题没有读错,但没想到我却又在这道题上失误了,泥煤。。恶魔

经过我的认真读题,抛开一些无关内容的介绍,这道题的本质也就是求 a+b*10c 除以 d 的余数 ,其中abcd都是已知量。难点在于这里的abcd取值都会很大,就算是计算机也不能在1秒内直接算出结果,超时也就是0分,残酷!

之前百度一下听说要用“快速幂”这种东西,完全没有听说过,而我的算法是我自创的,虽说效率可能会有点低,但是拿80%的分应该也没问题

%表示取余,那原式 (a+b*10c)%d = (a%d + b%d * 10c %d )%d,基本变成了小数字取余,唯一的大数据就是10^c % d假设我要求的是 1016 % 7 ,那就等于316 % 7 (这步由10%7=3得来)
= 98 % 7 = 28 % 7 = 44 % 7 = 162 % 7 = 22 % 7 = 41 % 7 = 4按照这种算法,就可以逐渐将大指数化小,求出模
这种方法基本也不会走太远,算是个不错的题解吧

只是事不如我愿,直到回家的路上我才猛然发觉我做错了!破碎的心

316 % 7 –> 98 % 7 这步,将底数平方,并且把指数减半,使其可以和7再次取余。我也有想到在“指数减半”这个过程中指数必须为偶数才行

于是我在读数据时也进行了处理:

if ( c%2 == 1 )
{
    b = b*10;
    c--;
}

 

这样一来指数c就是偶数了,就可以按照我的算法运算了?

我真的是脑袋卡了,大概是受到了“偶数+偶数=偶数”、“偶数X偶数=偶数”的影响。。。就认为“偶数÷偶数=偶数”。。。根本就没有花上1秒钟去检查这个结论的正确性,加上样例都通过了,就误以为这道题搞出来了

比如 810 mod 6 = 210 mod 6 = 45 mod 6, 然后?由于是5作为指数,就没法再进行处理了。这里应该将4提一个出来,把45化为44

结果在回家的公车上,才突然发现10÷2=5啊!!凋谢的玫瑰也就是说,这道题除非指数c为2^n或2^n+1,不然都是错了

最后这道题估分10-30 ,泪!

第二题

这题算是考了两天试共6题中,唯一一道我下不了手的题,贴吧上对于这道题也大都没有结果,用数学老师的话来说,那就是“对于这道题嘛,是用来感受的

题目链接点我 ←。←留下链接,这题等我5年后功力上涨了,再来秒杀讽刺

纯粹乱搞的题,答案直接输出随机值- -,求RP!给个10分!

第三题

是一道有向图求最短路径的问题,在掌握范围内。虽说我用的那个算法不是最好,计算量相当的大,恐怕也只得得到40%的分。但好歹还是花了我个多小时写出来了,

第一天的“郁闷”还有很大一部分出自第三题,那就是我开的数组太小了。节点数目只开了50个,貌似题目上的节点数目写的是≤5000,我是担心内存会爆了?总之只要输入的节点数>50,我就没戏了

似乎记得当时好像是这么想的:我这个算法的时间利用率低,要尽可能的节约时间,比如开数组这种东西少开点也能节省点时间。。。唉,肯定是昨晚睡晚了。

不过本来以我那个算法,过50节点的数据也就很玄,最终的得分预测是10-25分吧

Day 2,漂亮的一天

这一天的3道题我算是考爆了,一扫昨天的郁闷气息,代码写的让我自己都陶醉,那叫一个漂亮!一个单词形容那就是Excellent

先在这里感叹一下:我们泸州在信息这方面就是赶不上成都绵阳啊!今年泸高参赛的只有2人,我和隆晋威,因为高二那年泸高没搞。成都那些学校,每个学校都是10个左右的人,围成一团,那气场!瞬间把我们秒杀。。。更厉害点的成都七中大约来了20人,还穿着整齐的校服,够威武。正当我们在感叹这种差距时,开来了一辆车,上面写着“绵阳南山中学”,然后。。。下来了一车人,大概有40人吧失望

不得不说的就是坐我对面的那位“装B大神”,今天越发猖獗了。还拍桌子、伸懒腰,弄的声音很大,代码写累了,抓起一瓶水,咕咚咕咚,声音比敲键盘还大。。无力吐槽

第四题。动规,时间复杂度O(n),这题应该是满分的节奏,保守一点80-100吧~

第五题。动规,时间复杂度O(4n),不过网上有人说可以用一种算法只需要O(n)
虽说不确定网上说的是不是真的有比我好的算法,估分还是就60-90吧

最后一题。爆搜,略微剪枝,和第三题一样,数据大了就过不了了。
这题就算是爆搜也好难写,虽然前2题只花掉了1小时,但之后的2.5小时可以说都耗在上面了。。
预计得分15-30分,←_←少的可怜:-!

—————————————————————
noip已经连续2年没考动规,所以前一天晚上专门复习了一偏,真的命中了!
相当的给力啊!

最终本次noip我的成绩预测是185-285
。。。差值刚好100,这估分神奇了。按去年的分数划分,我应该是省二,但如果RP爆发考到了285,那省一也没得问题,哈哈:-D

一切都等12月出成绩了

—————————————————————
后天就是一诊考试,缺少了3天的复习的确是个损失
但是就算是最后这一点点复习时间,我也要好好利用的!

能做到不留遗憾地考试,这就是成功了!

无论是一诊还是noip,我都是这样想的。祝我考好!

5 条评论
  1. 膜拜···

  2. 今天是个惨淡的日子,NOIP和一诊的成绩都出来了!noip第一天三题分别20,0,10。第二天分别100,70,5。。205残酷的分呐,不过尽然四川省120多名。具体几等奖还要12月才知道了。
    一诊在上次考差的情况下倒是有所进步,只是还是各种失误!!这分数估计也就是二本线上下,总之值得我学的还有很多,必须加油了!

  3. 卧槽,竞赛大佬

发表一条评论