Super pig杯NOIp2008提高组模拟赛简记

参加这场比赛的主要目的是热身，由于期末考的关系我两个星期没有进行Coding（虽然真正在复习的时间只有考试的那个星期……）。不过比赛的成绩大大出乎我的意料，许多我以前已经能够比较有效避免的失误在本次比赛中再次暴露无遗。

先说说做题的情况吧

1. 很明显是O(nlogn)的算法求两次LIS。我刚看出模型就不加思索地开始Coding，结果不仅忘了做预处理，还写错了O(nlogn)的LIS（忘了初始化）……
2. 比赛时用的是排序后套01背包模型的O(nlogn+nm)的算法，感觉这个模型应该是正确的，但不知道为什么全部WA，估计是Coding上的问题。
3. 比赛时没想到怎样统计不同最短路径数，但又不想用DFS去cheat那30%的分，于是在SPFA的基础上乱搞了一下。很囧的是对这题的理解也有问题，边信息重复我理解为了重新信息应该是相同的……
4. 求x^x mod 1000我用的方法是开一个一万的数组来记录x^n mod 1000的值，找循环节来计算x^x mod 1000。但比赛时思维短路推不出怎样通过隔板原理来利用组合数学计算，无奈之下写了个DFS骗小数据的分……

最后的得分是20+0+30+20=70.......

本次比赛我的做题情况概括来说就是建模完全正确，Coding几乎全错......而且这个比赛是NOIP模拟赛，用暴力算法是可以拿很多分的......假如用暴力算法的得分情况是60（O(n^2)）+60（DFS）+20+20=160......暴露出的很大的问题是我自以为掌握了算法，但实际编写过程中却错漏百出。事实上我这个赛季参加的比赛中除了NOIP2007外，或多或少地都暴露了这一弱点，但一直没有引起我足够的重视，结果造就了市选的惨败......这个暑假的训练计划的其中一项就是要进行大量的算法代码编写练习以及比赛的实战练习。

顺便概括下一Solution中的解法

1. 将k前面比>=k的和k后面<=k的剔除，以k为分界做两次O(nlogn)的LIS，将两个LIS的长度之和+1即为所求。
2. O(n^2m）的DP。用f[k,i]表示第k个时间，目前在第i棵树（已经摘了果子），能得到的最大价值。状态转移方程是f[k,i]=max{f[k-t[i,j]-c[i],j]+s[i]|a[j]<a[i]且k>=t[i,j]+c[i]}。
3. 先求出到各个点的最短距离，用一个队列储存。然后对这个队列进行排序，按照dist[i]递增的顺序递推，f[i] = sigma { f[j] | (dist[j]+d[j,i] = dist[i])and(d[j,i]<>maxlongint) }{1<=j<=i-1}，f[n]（注意，这里不是第N个位置，而是N顶点所在位置）就是答案。
4. 快速幂求g(x)，ans=C(g(x)-1,k-1)。

个人整理的本次比赛资料集（含我的赛后AC程序及Cena配置文件）