noip2012初赛小结
今天下午惨遭乱虐回来。。本以为会越考越简单的,想想11年的初赛还不是水过,结果这一次准备得就不是很充分,没想到各种乱爆。。 经过与noip吧的答案核对,结果如下: 1.单选爆一题,那道32位可以访问内存的,说实话,不懂。。但我记得好像以前看什么电脑书是有看过类似的,好像理论可以访问4gb但是实际上却没有那么多。。 2.多选爆5题,天呐。。 粗心了一道,最短路的那题d[v1,v2]d[v2,v1],是有向图啊。。 还有三原色、np问题什么的表示不会。。头回知道np、p问题和空间也有关系,三原色以后就记住rgb(red green bl e)呀呀呀呀。。。电脑的三原色和颜料的三原色是不一样的。。话说这个初二物理就学过,我给忘了。。 无限循环小数的那题也不大懂,多选了一个不循环。。其实这个不应该错的,猜也该猜对。。 第一道,时间复杂度的也乱跪,神牛表示n*2^n时间复杂度不能算2^n,虽然n很大的时候相比2^n,n可以忽略,但是有了n它就不能算是2^n。。然后什么渐进复杂度什么的我也不大懂,就不卖弄了。。 3.问题求解,神牛表示第一题是2^8=256,这个不大懂,但是神牛居然2^8=64了。。现在非电脑操作不便,略写:对于表达式f(p,q,r),p,q,r有2^3种选法,所以一个表达式对于8种p,q,r有8个结果(0 or 1),即得到一个8位二进制数,不等价就是至少任意一位不等,所以共2^(2^3)=256种,表达式如何构造不懂 第二题是树形dp,考场上没来及想。。方程2种,f(i)=f(i.son1)*f(i.son2)+f(son1.son1)*f(son1.son2)*f(son2.son1)*f(son2.son2),f(i)即以i为根的独立集数(包括空集),方程分为取i和不取i的相加。还有一种方程较麻烦,增一维0,1表示不取i与取i,状态只跟儿子有关,思想一样,这里点到为止 4.写结果 第一题,去掉一个最高分,去掉一个最低分,再求平均分,是整除。。 第二题,求因数个数,分解一下质因数然后乘一乘就出来了。。 第三题,某牛说是什么二进制,我是不懂,我看出来的就是n个1合并,问合并次数。。对于8是4和4合并,再拆成2和2,再拆成1和1,实际上是一个二叉树,反正对于8是7次,然后2012是合并不完的,因为他没法做到相等,会拆成1024和988,然后就是988再拆。。最后合并次数加起来就可以了,对于8合并次数是7,16就是7*2+1=15,也就是每个2^x合并都是本身-1。总之2012可以拆成8个2^x,就是2012-8=2004 第四题,一看就是和树有关的,但是我想先做完善程序,结果最后没来得及。。好像是给先序中序,然后求树的什么权值貌似。。 5.完善程序 这个真的大爆啊 第一题说实话没看懂,写的毛啊。。但是猜是可以猜出很多的,貌似我只错1空。。 第二题更是乱萎,对于循环队列的作用我很久都没理解,后来终于明白是模拟可以翻转的部分,又纠结他到底是tail为栈顶还是head为栈顶,改了好多次,只剩20分钟,越急越慌,欲哭无泪。。最后一想,平时都是取head操作,那这里也该是head为栈顶,一看果然全都解释的通了,可是我那三个headheadtail改了好几次,不记得自己最后有没有把正确的写在答题卡上。。。不过s[n]:=q[tail]是肯定爆了,开始没理解清楚,后面也没改。。 总之完善程序爆2空,如果那三个忘记改了又是大萎。。 综合:100-6*1.5-2*5-8-5=68,如果三个空再错就只剩60.5啦。。。不过就算只有60,初赛应该也是可以过的吧。。今年尼玛绝对比去年难啊。。