Problem A: Modular multiplication of polynomials
A题是一道模拟题，主要考察选手数组的和循环控制的运用能力。
题目要求模拟的是多项式除法，且给出了具体的运算规则，异或运算。给出f(x),g(x)两个多项式相乘，然后除以h(x)多项式，求其余数(亦为多项式)。先用两重循环将f(x),g(x)相乘，用一数组记录相乘后多项式k(x)的x^i的系数，然后做多项式除法。设被除数的最高次为x^n, 除数h(x)的最高次为y^m, 直到n<m时候循环结束。

Problem B:Checking an Alibi
这题其实就是求每个点到1号点的最短路。 然后判断每只牛所在地到1号点的需时是否小于等于M.
题目没明确说有没有重边，一般情况下是要考虑的。 在比赛时，我们认为数据中有长度为0的边，与题目中1－70000不符。但ACM就是这样，题目出问题是常有的事。在确定自己程序没错的前提下，选手们只能考经验和感觉去猜。

Problem C:The Game of Mafia
直接搜索就行了，白天和黑夜轮着搜，注意一下只剩下他自己的时候的情况就可以了。

Problem D:Multiplication Puzzle
这题是经典的动态规划。
用a[1000]表示愿数组，d[i][j]表示让第i个数与第j个数碰面（删掉他们之间的元素）的最小代价。
方程是：
 d[i][j]= max(d[i][k]+d[k][j]+a[k]*a[i]*a[j]，i<k<j)
时间复杂度是O(n^3)。

Problem E:Zip
这题有两种操作A和B
对于操作A来说只要统计一下各种字母出现的次数就可以很容易得到S'了
而对于操作B来说统计一下序列S'的各种字母的出现次数，然后根据p就可以得到序列的第一个字母和第二个字母，然后根据根据第一个字母就可以得到最后一个字母
比如对于样例来说：
xelpame   7
a      x
e      e
e      l
l      p
m     a
p      m
x      e
确实了第二个字母是x,第一个字母是e，e出现第一次的时候就可以得到最后一个字母是e，
所以根据最后一个字母倒过来生成前面的序列，从对应e的最后一次出现，可以得到倒数第二个字母是l，然后对于l最后出现一次，可以确实l前面是p，然后一直填上去就可以得到原序列S=example

Promble F: Wall
F题考察的是选手基本的计算几何知识。
读懂题意后就是求凸包的周长+一个圆的周长, 求凸包可以先选取最左下角的点，然后以该点为基准对所有点作极角排序，然后就是用Graham扫描法求凸包了。

Problem G:Ouroboros Snake
这题可以用构造算法。 题目有一个限制，2^N 个数不重不漏的出现，这就是关键所在。可以想到，必然有N个零连着，这就是要求数列的开始（以后不可能有N个零连着了）。然后我们每次取后面N-1位，加0看看前是否有这N位。有，那么这一位不能是0（要不就违反了不重不漏了），只能是1。否则就加0。
但是仅仅这样并不能得出正确的答案。 怎么办呢？
想到这个构造算法的结尾必然是很多个1连着（因为加0的话，这N位在前面出现过了）。理想的情况是N个1。那么象 1000，1100，1110这些前面全是1，后面全是0的数就在首尾相接（这是一个圆环）的时候出现了。
修正办法立刻有了，就是在一开始时把象 1000，1100，1110这些前面全是1，后面全是0的数标志为已经出现过。然后用我们之前说的那种构造法一位位的确定那一位是0还是1。
经过检验，发现这样就符合要求了。

PKU 3093 Margaritas on the River Walk
        先对输入的数组排序，然后类似于01对a[i]做决策，核心代码加了注释：
         for (i=1; i<=n; i++) {
                 for (j=1; j<=maxsum; j++) {
                        if (j >= sum[i]) d[i][j] = 1; //j比sum[i]大，肯定这时候d[i][j]=1;
                        else {
                                d[i][j] = d[i-1][j];//不考虑a[i]
                                if (j-a[i]>=0) {//考虑a[i]
                                         if (d[i-1][j-a[i]] > 0) d[i][j] += d[i-1][j-a[i]];//把a[i]加进以前的选择里面
                                         else d[i][j]++;//a[i]单独作为一个选择(这里需要先对a[i]排序，消除后效性)
                               }
                        }
                 }
         }

PKU 1037 A decorative fence
        先dp算出以i为起点的序列的个数，再组合数学
        td[n][i]和tu[n][i]分别表示个数为n，以i开始的上升和下降的序列个数
        易知:
        td[n][1] = 0;
        td[n][i] = sigma(tu[n-1][j], j从1..i-1)  = td[n][i-1] + tu[n-1][i-1] ;
        tu[n][i]  = td[n][n+i-1];

PKU 2677 Tour
        双调欧几里德旅行商问题(明显阶段dp)
        动态规划方程 ：d[i+1][i] = mint(d[i+1][i], d[i][j]+g[j][i+1]); 
                                      d[i+1][j] = mint(d[i+1][j], d[i][j]+g[i][i+1]);
                                       0<=j<i   

PKU 2288 Islands and Bridges
        集合DP
        状态表示: d[i][j][k] (i为13为二进制表示点的状态, j为当前节点, k为到达j的前驱节点)

pku 2513    AC    火星人了, 第一次用hash, 以前都是用map偷懒的, 不过这题用trie应该会更好, 建好图之后就是DFS判连通,然后欧拉回路了.
pku 3216    AC    二分图最小路径覆盖, 建立图的时候要求一次多源最短路(这个害我wa了好几次).
pku 3211    AC    理解题目后就是最每一种颜色做01背包了.
pku 3214    AC    这的确是一道好题, 先后序遍历heap,每次减去一个sub值, 然后对得到的序列求最长不降子序列,要nlogn的才能过.
pku 3213    AC    看了解题报告才会做,先进行坐标转换[(x-y)/2, (x+y)/2], 然后求sig|xi-xj|+sig|yi-yj|的最小值.
pku 3215    AC    理解题意后其实是一道比较简单的计算几何,但是很容易WA,按方程和X轴的交点分段,然后枚举交点,统计x轴上下各自线段个数
pku 1177    AC    线段树, 4k的代码, 学会了测度和连续线段数, 记在笔记本上了, 随时复习.
pku 2564    AC    再次火星人,第一次写trie, 标号法DP, 题目描述很阴险.
tju   2762    AC    基本的线段树,   用了ghost_wei的写法，省了B[]和E[]，基本思想是二分
pku 1699    AC    简单搜索，写下的目的是这道题用了alpha-beta剪枝
pku 1195    AC    二维树状数组，详细看李睿的论文吧.
pku 2482    AC    二叉统计树+树状DP+扫描线，绝对是一道好题.
pku 1038    AC    被这题恶了一天，算法艺术上的方法超时，换了解题报告的那个A(x, y, p)的状态定义才过了，程序写的真好，特别是那滚动数组
ural 1031    AC    由单调性，可以O(n)的时间与处理，然后就O(n)的线性DP, 阴险地方是start可能小于end.
pku 1850    AC    组合数学啊，以前一直不会，今天终于搞出来了，用DP先算出不符合的字符串数，然后将输入字符串转换成26进制-不符合的个数
pku 3067    AC    和star差不多，还是数状数组最好写.
ural 1018    AC    树形DP, 把边的苹果数看成在树的节点上，然后做树状dp, 当然开始要先dfs一次建树
pku 2800    AC    数论，k mod i  = k - floor(k/i) * i
pku 2516    AC    拆点，然后二分图最佳匹配

pku 1014   已做
pku 1037   
pku 1050   已做
pku 1088   已做
pku 1141   已做
pku 1159   已做
pku 1163   已做
pku 1322   AC
                  看到题目就害怕，概率的-_-结果分析之下原来也不难
                  状态d[i][j]表示有j种颜色,拿了i个巧克力的最优值
                  方程: d[i+1][j+1] = d[i][j]*(c-j)/c;               (c为总颜色数)
                            d[i+1][j-1] = d[i][j]*j/c;
                  由于只是保留3位小数，所以加优化if (n>1000) n = 1000+n%2; //至于为什么要分奇偶性，这个还不太懂-_-这道算是ac一半而已
pku 2904   AC
                  dp[k][i][j]表示k个邮筒时候放鞭炮数为i..j时候的最优值
                  转移方程为:
                  dp[k][i][j] = min{t+max(d[k-1][i][t-1],d[k][t+1][j])};
                  状态转移时候就是考虑选t个鞭炮放时候爆或不爆
pku 1458   已做
pku 1579   已做 
pku 1695   AC 
                 d[i][j][k]表示到达第i个点时候另外两辆车分别在点j和k时候的最优值
                  方程： d[i+1][j][k] = min(d[i+1][j][k], d[i][j][k]+g[i][i+1]);
                               d[i+1][i][k] = min(d[i+1][i][k], d[i][j][k]+g[j][i+1]);
                               d[i+1][i][j] = min(d[i+1][i][j], d[i][j][k]+g[k][i+1]);
                  //初始条件d[1][1][1] = 0;
pku 1732   AC
                  线型模型，本想用trie的，结果用map偷懒了。
                  d[i] = min{d[j]} + 1      0<=j<i && j+1..i字符合法
pku 1953   已做
pku 1976   AC
                  先对区间做预处理, 后面不足的coaches补0;
                  d[k][j] = max{d[k-1][p]}+b[j];          0<=p<=j-m (b为处理后的区间数组,m是一台locomotiv的容量)
                  由单调性可以在状态转移时候保存前一次转移时候的最大值再和b[j-m]做比较，把O(n^2)压缩到O(n)的时间复杂度
pku 2386   已做
pku 2479   已做
pku 2951   已做      
pku 3036   已做
pku 3014   已做
pku 2229   已做
pku 1185   AC
                  最经典的状态DP,我用三进制表示每行状态，然后递推，结果tle,分析之后，枚举出有效状态，再推, 1000ms左右，
                  还是不够 快， 张伟达的论文上有更快的算法。
pku 1276   AC
                  01背包

有空把以前的也再做一次!~   

pku 2486 apple tree

解法：

/////////////////////////////////////////////////////////////////////
//Apple Tree
//数组二维go，bk
//go[t][i]代表节点t的所有子树上走i步不返回,取得的最大苹果数
//bk[t][i]代表节点t的所有子树上走i步并返回,取得的最大苹果数
//求节点为x，实行不断合并子树求最优值
//当前合并到了q棵子树：
//go[x][i]就是这q棵子树上走i步不返回的最优值
//bk[x][i]就是这q棵子树上走i步并返回的最优值
//合并第q+1棵子树(不妨设第q+1棵子树的根为y)的时候，有
//go[x][i] = max( bk[x][j]+go[y][i-j], bk[y][j]+go[x][i-j] ), j=0.....i
//bk[x][i] = max( bk[x][j]+bk[y][i-j] ) j=0,.....i;
////////////////////////////////////////////////////////////////////////////

代码：http://www.cppblog.com/qywyh/articles/18618.html