开始做noip真题

noip2006    100
之前做过一次，做了一般弃疗
今天在学校又做了一次，没什么大问题
就是程序填空那里答案的形式和我的形式不一样
话说真的有“专家上机评测”这种东西吗？

noip2007    98.5
选择题错了一个，看错了那个欧拉图的判定
问题求解也很好玩：N个人在操场里围成一圈，将这N个人按顺时针方向从1到N编号，然后从第一个人起，每隔一个人让下一个人离开操场，显然，第一轮过后，具有偶数编号的人都离开了操场。依次做下去，直到操场只剩下一个人，记这个人的编号为J(N)，例如，J(5)=3，J(10)=5，等等。 则J(400)=
这题居然还给了提示：分析N=2^n+r
在提示的指引下想出了方法：首先如果N=2^n的情况，显然就是1，因为每次去掉偶数后重编号再去掉偶数，然后1号一直是奇数，所以最后肯定剩下1号。然后我们考虑现在多了r个人，显然第一轮我们至少可以干掉r个人，原因很简单：第一轮干掉的然数为(2^N+r)/2>r，所以我们干掉r个人后，假设第i个人下一个的编号为d，那么从d开始按照1,2,...,2^n编号最后肯定是一号留下，也就是d号。那么d等于多少呢，显然就是2*r+1辣

noip2008    89
选择错了3t，问题求解居然都错了一个
问题求解还是蛮有趣的：书架上有21本书,编号从1到21,从其中选4本,其中每两本的编号都不相邻的选法一共有______种.
我开始一直在用容斥做，即：C(21,4)-3*C(20,3)+2*C(19,2)-C(18,1)，然后发现这是有问题的，因为在算C(20,3)时事实上也有重复C(18,1)
正确的做法是：我们考虑已经取出了4本书，显然剩下17本，我们要把这四本书插回17本书中，要求两个不相邻，即同一个空位只能插一本，所以答案就是C(18,4)=3060
当然这种题一般动态规划是能解决的：设f[i][j]表示前i本书取j本且两两不相邻的方案数，f[i][j]=f[i-2][j-1]+f[i-1][j]

noip 2009   89.5
除了多选其他全对
然而多选只对了3题是闹哪样...
要想背古文一样背oi...
简直excited

noip2012
做了一半不想做了
选择提错了5道还有卵用啊...
感觉被文化课的作业搞的很不爽...
特别是国庆作业，妈的这也太多了吧...
算了，认了

noip2013  95.5
单选居然错了3题TAT
主定理没有理解到位啊TAT：
T(N)=2*T(N/2)+2*N
首先后面那个f(n)=2*N=O(N)！！！！这是重点...
然后主定理f(n)=log(2)/log(2)所以T(N)=N log N
然后问题求解T2很有趣，我还记得当前太SB不会作：
fn表示从n号节点跳到1号节点的平均跳跃次数
f1=0
f2=2

f2=(f1+f2)/2+1
f2/2=1
f2=2

f3=2.5

f3=(f1+f2+f3)/3+1
f3=2/3+f3/3+1
2/3*f3=5/3
f3=2.5


f4=(f1+f2+f3+f4)/4+1
  =4.5/4+f4/4+1=f4
3/4*f4=8.5/4
f4=8.5/3

4/5*f5=(f1+f2+f3+f4)/5+1
4/5*f5=(4.5+8.5/3+5)/5
f5=(4.5+8.5/3+5)/4
  =(13.5+8.5+15)/12
  =37/12

noip2014   100
AK了很正常，去年刚刚做过
不过感觉问题求解第一题很有趣，问：用1 1 2 4 8 8能组成多少个不同的4位数
我的解法是这样的：
首先考虑4位数不重复，显然就是P(4,4)=4!=24
然后考虑只有1重复，那么其他三个任选两个，然后就有3个空，把1 1插进去，一共有P(3,2)*6=36
然后考虑只有8重复，做法同上，一共有P(3,2)*6=36
最后是只有1 1 8 8，暴力1188 1818 8811 8181 1881 8118，共有6种
所以就有102种

未完待续...