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.shnenglu.com/qywyh/articles/18618.html