noip2017翻车记以及一部分参考各博客的题解及数学证明

初赛了……考完之后真是一脸懵逼= =
虽说题目难度真的不大,但是考得这么烂还真是菜啊……
大致说说考试过程和某些题目吧……
14:00
考试快开始了……很想复习点什么但又不知道复习点什么
于是就浪= =浪着浪着到了14:15就去了考场了。。
14:30
考试开始……没有什么慌的感觉说实话,
因为自己觉得初赛只要不错读程(flag)随便考考就ok了。。
还嘚瑟地抖腿。。
试卷一发下来,结果第一题就大跌眼镜(2333)
Pascal哪一年开始隐退noi?
woc……还真不知道!
后来突然想着老师好像说过我们毕业刚好不能用?那就2020吧。。
华丽丽开门红。。
后面几题都挺蠢的,不过那道算星期几的我还真算了挺久,怕算错,
但是想来想去没细节就速度加快了……(还真没细节)
14:50
顺利进入多选题……第一题……送分
第二题……送分
第三题……希尔排序啥来着,,...反正不稳定,送分
第四题……fortran是第一个高级语言吧= =怎么会面向对象去
第五题。。吐槽一下,最后一题不是说好送分的么。。
王选奖不知道为什么我就是有印象,,
不过应该不是普遍知道的吧= =
又过了一遍确认无误就pass了。。
15:00
问题求解time。。
第一题沙伯题……随便凑凑就出来了,3次。
第二题……woc这tm不是最小割么??ccf预示今年复赛考网络流??
没多想……手动跑了个网络流……好像不难跑,最大流是4.
接着第二问我真是想锤死我自己= =
我知道这个平面图是可以转对偶图然后通过最短路来求最大流的。。
所以我不厌其烦又画了一个,
然后方案数。。按理来说就是最短路的方案数啊喂。。
一开始做出来4,马上发现了相同权值的边得加上,
于是算出来8……
去图上比划比划,发现没什么问题了吧。。就没多想pass了。。
结果翻车= =有一条相同权值的边没加。。谁叫我草稿纸太乱了啊= =
答案是9。。
15:15
读程本来觉得应该不会难,结果第一题就慌了一跳,,
并没有看出来它在干嘛= =
为了第一题不错掉,我来回算了好几遍才结束,15;
第二题本来以为要暴力模拟的,结果发现竟然是个幻方= =
马上过了;
第三题……是来搞笑的么,,逆序对个数,好像是8个。
第四题……诶不想说啥了。。
本来以为折2次之后的点就好了……结果竟然每次cnt清零!!
清零!!wocccccccccc!!!
做得太快而且自信了……结果没怎么检查,
于是这一大道读程gg……8分啊。。。
15:40
喝口cola舒畅舒畅。。
填程比较简单,很快就做掉了。。
不过第二个填程题目出错了!
它要求最长的路径,,结果答案是最长路径上的点数!
就因为这个我多想了一步于是最后一格……
最简单的一格……
2分的一格……
我写了ans ……无奈。。
我当时是瞎了么没看到后面一句就是ans=len[a]。。
好吧,这回真gg了……

答案 C
不说了好吗,c++都是泪……这题过。

答案 B
补码:10101011
反码=补码-1:10101010
保留符号位,
原码=~反码:11010101
故数字=-1*(2^6+2^4+2^2+2^0)=-1*(64+16+4+1)=-85

答案 A
在数据存储中,1KB=1024B,16位色=2*8字节=2B
故总大小=
1.6*10^3 * 9*10^2 * 2
=1.6*9*2 * 10^5
=2880000B
=2812.5*1024B
=2812.5KB

答案 C
文科选手:
历史书上写着的开国大典那天是星期六!^o^!——详见历史必修课本之中国现代史之新中国成立部分。。。。
信息学选手:
(非闰年)每年天数365%7=1,即第二年的“星期x”会推后一天;
所以2017-1949=68年,
68=17*4,即1949~2017年间至多有17个闰年,
又因为2000为闰年,所以1949~2017有17个闰年,
于是,2017年的“星期”比1949年的推后:(68+17)%5=1;
所以“星期六”+1=“星期日”。
即1949.10.01为星期六。

答案 A
n个节点的最小连通图含有n-1条边,
所以必须删去m-(n-1)条边。

答案 C
由T(n)=2*T( n*2^-1 )+n*log n,我们考虑把T(n/2)即T(n*2^-1)拆到底。
T(n)
=n*log n + 2*[ n*2^-1 * log(n*2^-1) + 2*T(n*2^-1) ]
=n*log n + n*log(n*2^-1)+4*T(n*2^-1)
......
因为每次n/2,所以到达T(1)所需拆的次数为log n,
=n*log n + n*log(n*2^-1)+ n*log(n*2^-2)+......+ n*log(n*2^-logn)共logn项
=n*[ log n + log(n*2^-1) +......+ log(n*2^-logn) ]
=n*(logn)^2
所以选C

答案 B
后缀表达式的应用之一,就是在计算机上进行数学表达式的运算,
运算过程依靠 栈 进行,
详情请参见 各种表达式的求值

答案 C
简单无向图,就是没有 自环 or 重边 的无向图,
这样的图中,可能有 6,5,4,3,2,1,0条边。
边数为6,5,4时,必定能构成连通图,方案数为=22
边数为3时,可能能构成连通图,不能构成的情况有4种(如4个点各有一次机会不被连接),所以方案数为=16;
边数为2,1,0时,不可能构成连通图,方案数为0;
综上,方案数为22+16+0=38。
*小扩展1:求n个不同的点构成的简单无向连通图有多少个呢?
*小扩展2:求n个不同的点,m条边构成的简单无向连通图有多少个呢?
*小扩展3:求n个不同的点构成的简单无向图(不一定连通)有多少个呢?
*小扩展4:求n个不同的点,m条边构成的无向连通图有多少个呢?

答案 D
在数奥的排列组合题型中,有一种叫做
“放挡板”
的方法,它解决的是“固定个数的元素 放入 不同集合中 的方案数”一类问题,本题明显是这种题型:
*为什么选用“放挡板”法?
——因为元素无序,而集合有序。
挡板法如上图,
我们假定从1~4班逐班按顺序分配名额(在这里是否按班级顺序配额,对结果没有影响),即从左向右逐次安插挡板;
那么之前分给了1班的名额肯定不会被抽出来给2班(否则你会被1班小朋友打),即新加的挡板必排在已有挡板之后;
所以设f[n][m]为n个名额分给m个班级的方案数,即n个元素间插入m个挡板的方案数,
那么最后一个班可能分到0~7个名额,
那么f[7][4]=f[6][3]+f[5][3]+f[4][3]+f[3][3]+f[2][3]+f[1][3]+f[0][3];
推而广之,转移方程为。
边界条件为f[0][0]=0,f[i][0]=0,f[0][j]=1,f[i][1]=1,f[1][i]=i。于是可以轻易地推出f[7][4]的值。f[7][4]=120。
这是一年前在奥数班里学的知识,我想我可能真的是一个假的数奥生。。。。

答案 B
这一题,真的是奥数题,当然也曾经在高考压轴题出现过,由于本题涉及求数列通项公式——高考考点,我还是建议同学们了解此方法
特征根法——
“特征根”是线性代数中的一个重要概念,不知道是哪位大数学家把它和求数列通项联系了起来,于是使得一些相关计算变得简单了:
形如an=k1an-1+k2an-2+……+kian-i(i 叫做一次线性递推数列,
其特征方程为xi= k1xi-1+k2xi-2+……+kixi-i,
解得一组x1,x2,……,xi为方程的根(可以为虚数),
当x1!=x2!=…..!=xi(即这些根两两不等)时,
数列的通项为an=c1x1n-1+c2x2n-1+….+cixin-1 ①
其中c1,c2,…,ci由初始值决定
——将题目必须给出的
a1=..,a2=..,…..ai=…(题目不给就基本没法解)
带入①式中,得到i个方程组成的方程组,
解开可得c1,c2,….,ci,
最终得到数列的通项公式。
(当x1,x2…中有相等的根时,我还没找到相关资料)
(听别人说可以从线性变换的角度思考……我表示不是很懂)
让我们回到本题——
数列递推式为:f[n]=( f[n-1] + f[n-2] )/2
∴特征方程为:x2=(x+1)/2
解得x1=1,x2=-0.5,x1!=x2
∴列出如下方程组:
A0=0=c1×1-1+c2×(-0.5)-1
A1=1=c1×10+c2×(-0.5)0
解得c1=2/3,c2=1/3
故an=(2/3)×1n-1+(1/3)×(-0.5)n-1

显然当n->+∞时,an->(2/3)
如此如此,本题选B
(PS:另外推荐带入f1,f2,f3,f4,f5慢慢求解)

问题求解1,我们只要对最上面的1、中间的0和中间的0右边那个0做操作即可,共3次。
问题求解2,(裸的)最小割转对偶图。
________________________________________
阅读程序1,一个比较烦的递归,细心点应该没啥问题,10分钟肯定能模拟出来的。
阅读程序2,一看就是幻方吧,直接写上就好啊。
阅读程序3,一看就是逆序对啊。
阅读程序4,矩形内45°反弹。
________________________________________
完善程序1:
(1)是不是不少人填了0。。。但是注意下面i的循环是从1开始的!所以呢,rest的初始值是p[0]啊。
(2)这个空的话,我当时是在草稿纸上举了个100÷3来计算的,我们把这个while里面的东西模拟一遍,就可以发现它是求出一个最大的k使得q*k<=p(似乎就是p div q?),那么这里就是填rest < q咯(这里rest=q*k)。
(3)跟上面一个思路的,上面填对了下面就不可能错,很明显是rest/q。
(4)把当前的余数跟除数的下一位合起来继续除,注意要写模!
(5)最后的余数,直接模就好了啊。
完善程序2:
(1)很明显是b的入度加1吧。
(2)找到入度为0的点并进队。
(3)删掉所有与当前队头连接的边,如果有新的点入度为0就进队。
(4)傻逼空,肯定队头指针加1啊。
(5)更傻逼的空,替换最优解,就是比大小啊。

仅有 1 条评论
  1. 丁海

    真厉害啊…真的是无法想象

    丁海 September 4th, 2018 at 12:13 am回复
发表新评论