初赛

　　关于初赛：普及组的做的特别全，去年准备的时候把网上能找到的初赛题全做了一遍，然而错的题没有仔细想所以考的还是很差…今年终于要考提高组了！

　　15年：除了指针那道题都比较简单.

　　·17.AVI,MPEG,WMV都属于视频文件格式，不过这个好像没什么用了…毕竟不可能再考一次。

　　·21.在$1$和$2015$之间(包括$1$和$2015$在内)不能被$4,5,6$三个数任意一个数整除的数有_________个。

　　　　其实是一个比较简单的容斥题，但是注意第一部分容斥时使用的$x$的不是“两个数的乘积”而是“两个数的最小公倍数”。

　　·24.指针题不会也没有什么办法…尽量想清楚一点。

　　·27.初赛的题目中数组往往是从$0$开始用的,所以最右边那个是$n-1$.

　　16年:虽然这么错多不该错的地方,但是还是做的最好的一套.

　　10.我也不知道为什么这种题都会错…

　　四.4:把小于号看成大于了…

　　五.1.(3):要用大数去减小的才是正数.

　　17年:这一年明显难很多,错的也多很多.

　　3&&4.意外蒙对了?

　　8.一个比较经典的问题:有标号的连通图计数问题.然而经典归经典，之前并没有见过。思路好妙啊。设答案为$f_n$.首先可以求出带标号的图计数问题：$m=frac{n imes (n+1)}{2},h_i=2^m$,然后减掉不合法的情况.首先确定第一个点所在的集合中有$k$个点($k<=n$),就有$C_{n}^{k}$种选法,剩下的点可以随便组合为$h_{n-k}$,块内的组合为$f_i$种,乘一乘加一加就出答案了.

　　10.这题$tql$.什么时候初赛开始考这种神仙题了?$f_0=0,f_1=1,f_x=frac{f_{x-1}+f_{x-2}}{2}$,求$f_{∞}$.

　　无穷数列的收敛值！这也太…打了一个表(第一个是项数,第二个是值,第三个是它和$frac{2}{3}$差的绝对值)

　　现在我们已经知道答案是$frac{2}{3}$啦.下面是马佬的证明:

　　设$a_i=f_i-f_{i-1}$,可以发现$a_{i}=-frac{1}{2} imes a_{i-1}$

　　这个$a$数列是一个差分数列,所以要还原出$f$数列就是数列$a$的前缀和.

　 $f_{∞}=frac{a_1(1-q^∞)}{1-q}=frac{1}{frac{3}{2}}=frac{2}{3}$

　　三.2(2).

　　设粗的边边权为$2$,细边的边权为$1$,求最小割和计数…

　　最小割好求,计数是什么操作啊…

　　手玩一番只找到四种,然而答案是九种,正解:平面图转对偶图,最短路计数.

　　首先呢,让我们把$S$和$T$连接起来,造一个虚边出来,此时这个图就出现了一些”面”,对于每一个面造一个虚点出来.

　　然后对于每一条原图中的边，把它分开的两个“面”之间连一条边。

　　从$S$到$T$跑最短路计数,答案为$9$.

　　四.2:写程序的时候是模拟水题，手玩就成了模拟神题，成功写串行.

　　五.1,(3)读入是从$0$开始的,计算却从$1$开始,这就提示我们要先把$p_0$给$rest$.

　　五.1,(5)输出的时候再模一下.

　　18年…:

　　刚从考场出来…

　　一.3:挂在了所谓$CCF$赞歌上,这算是时事新闻吗?1984年邓小平指出:”计算机的普及要从娃娃做起.”中国计算机学会于1984年创办全国青少年计算机程序设计竞赛(简称：NOI)

　　一.7:这个没有错，终于做对了一次！我的做法非常奇怪：首先将线段从中间分开，可以发现有 $frac{1}{2}$ 的概率两个点选在同一半， $frac{1}{2}$ 的概率选在不同的两边，选在不同的两边时答案显然是两个$frac{1}{4}$拼起来,不同的时候就可以将问题的规模缩小一半,等于 $frac{1}{2} imes f_{0.5}$ ,发现答案是一个无穷项的等比数列相加,求得 $frac{1}{3}$ .

　　二.5:又考图灵奖,我又不会…

　　三.2:没做出来,蒙了一个$512$,显然是错误的.

　　四.1:这个..竟然算错了!!!难过(ಥ﹏ಥ) $14 imes 14\%15=11 ???$

　　四.4(2).不会，瞎蒙了一个$6$ $5$ $4$ $3$ $2$ $1$.显然是错误的.

　　五.2.第一个空忘了乘$0.98$,第二个对了，第三个对了，第四个错了，第五个…本来写对了，但是交卷前又给改成错的了。

　　AFO预定

—shzr