Question

关于noip的问题

http://xc2zzl.blog.163.com/blog/static/44022485201032222756781/
做出一道给至少十分（除了最简单的那几道）
用pascal做，除第一题外求标程,能达100分的

Answer 1

第一题实在是水……由于a、b都不超过maxlongint（maxlongint=21亿多），所以直接输入a、b，做减法即可

第二题实际上是输入N，让你算出（2^n-1）%10000是多少。由于N=maxlongint，直接算的话，O（N）会超时，所以采用分治算法，思想很简单，就是：

2^n=（2^ N/2）*(2^ N/2)，这样，你算一遍2^ N/2，第二次乘的时候就不用再算了。复杂度O（logN），很快。至于%10000，你每次算的时候都%10000即可。

第三题是经典的配对动规，f（i,j），代表在A序列中的前i个，和B序列中的前j个配对，所产生的最小恶心度。那么：

f（i,j）=f（i-1，j-1）+abs（v[i]-v[j]）（选择） 或者f（i-1,j）（不选）

当中较小的那个。由于j比较小，所以当miss的时候，不能选择miss第二个序列。

第四题是记忆化广搜，每次搜到一个点的时候，如果我当前的消耗比它短，则更新我到这个点的最小消耗值。队列空了之后，输出相应的值即可。注意本题不能用动态规划，因为存在着故意绕道的情况。

第五题应该是树状数组吧。这个我真的不会了，模拟30分吧。