Problem A: Modular multiplication of polynomials
A題是一道模擬題，主要考察選手數(shù)組的和循環(huán)控制的運用能力。
題目要求模擬的是多項式除法，且給出了具體的運算規(guī)則，異或運算。給出f(x),g(x)兩個多項式相乘，然后除以h(x)多項式，求其余數(shù)(亦為多項式)。先用兩重循環(huán)將f(x),g(x)相乘，用一數(shù)組記錄相乘后多項式k(x)的x^i的系數(shù)，然后做多項式除法。設被除數(shù)的最高次為x^n, 除數(shù)h(x)的最高次為y^m, 直到n<m時候循環(huán)結束。

Problem B:Checking an Alibi
這題其實就是求每個點到1號點的最短路。 然后判斷每只牛所在地到1號點的需時是否小于等于M.
題目沒明確說有沒有重邊，一般情況下是要考慮的。 在比賽時，我們認為數(shù)據(jù)中有長度為0的邊，與題目中1－70000不符。但ACM就是這樣，題目出問題是常有的事。在確定自己程序沒錯的前提下，選手們只能考經(jīng)驗和感覺去猜。

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

Problem D:Multiplication Puzzle
這題是經(jīng)典的動態(tài)規(guī)劃。
用a[1000]表示愿數(shù)組，d[i][j]表示讓第i個數(shù)與第j個數(shù)碰面（刪掉他們之間的元素）的最小代價。
方程是：
 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來說只要統(tǒng)計一下各種字母出現(xiàn)的次數(shù)就可以很容易得到S'了
而對于操作B來說統(tǒng)計一下序列S'的各種字母的出現(xiàn)次數(shù)，然后根據(jù)p就可以得到序列的第一個字母和第二個字母，然后根據(jù)根據(jù)第一個字母就可以得到最后一個字母
比如對于樣例來說：
xelpame   7
a      x
e      e
e      l
l      p
m     a
p      m
x      e
確實了第二個字母是x,第一個字母是e，e出現(xiàn)第一次的時候就可以得到最后一個字母是e，
所以根據(jù)最后一個字母倒過來生成前面的序列，從對應e的最后一次出現(xiàn)，可以得到倒數(shù)第二個字母是l，然后對于l最后出現(xiàn)一次，可以確實l前面是p，然后一直填上去就可以得到原序列S=example

Promble F: Wall
F題考察的是選手基本的計算幾何知識。
讀懂題意后就是求凸包的周長+一個圓的周長, 求凸包可以先選取最左下角的點，然后以該點為基準對所有點作極角排序，然后就是用Graham掃描法求凸包了。

Problem G:Ouroboros Snake
這題可以用構造算法。 題目有一個限制，2^N 個數(shù)不重不漏的出現(xiàn)，這就是關鍵所在。可以想到，必然有N個零連著，這就是要求數(shù)列的開始（以后不可能有N個零連著了）。然后我們每次取后面N-1位，加0看看前是否有這N位。有，那么這一位不能是0（要不就違反了不重不漏了），只能是1。否則就加0。
但是僅僅這樣并不能得出正確的答案。 怎么辦呢？
想到這個構造算法的結尾必然是很多個1連著（因為加0的話，這N位在前面出現(xiàn)過了）。理想的情況是N個1。那么象 1000，1100，1110這些前面全是1，后面全是0的數(shù)就在首尾相接（這是一個圓環(huán)）的時候出現(xiàn)了。
修正辦法立刻有了，就是在一開始時把象 1000，1100，1110這些前面全是1，后面全是0的數(shù)標志為已經(jīng)出現(xiàn)過。然后用我們之前說的那種構造法一位位的確定那一位是0還是1。
經(jīng)過檢驗，發(fā)現(xiàn)這樣就符合要求了。

PKU 3093 Margaritas on the River Walk
        先對輸入的數(shù)組排序，然后類似于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為起點的序列的個數(shù)，再組合數(shù)學
        td[n][i]和tu[n][i]分別表示個數(shù)為n，以i開始的上升和下降的序列個數(shù)
        易知:
        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)
        動態(tài)規(guī)劃方程 ：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
        狀態(tài)表示: d[i][j][k] (i為13為二進制表示點的狀態(tài), j為當前節(jié)點, k為到達j的前驅節(jié)點)

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軸的交點分段,然后枚舉交點,統(tǒng)計x軸上下各自線段個數(shù)
pku 1177    AC    線段樹, 4k的代碼, 學會了測度和連續(xù)線段數(shù), 記在筆記本上了, 隨時復習.
pku 2564    AC    再次火星人,第一次寫trie, 標號法DP, 題目描述很陰險.
tju   2762    AC    基本的線段樹,   用了ghost_wei的寫法，省了B[]和E[]，基本思想是二分
pku 1699    AC    簡單搜索，寫下的目的是這道題用了alpha-beta剪枝
pku 1195    AC    二維樹狀數(shù)組，詳細看李睿的論文吧.
pku 2482    AC    二叉統(tǒng)計樹+樹狀DP+掃描線，絕對是一道好題.
pku 1038    AC    被這題惡了一天，算法藝術上的方法超時，換了解題報告的那個A(x, y, p)的狀態(tài)定義才過了，程序寫的真好，特別是那滾動數(shù)組
ural 1031    AC    由單調性，可以O(n)的時間與處理，然后就O(n)的線性DP, 陰險地方是start可能小于end.
pku 1850    AC    組合數(shù)學啊，以前一直不會，今天終于搞出來了，用DP先算出不符合的字符串數(shù)，然后將輸入字符串轉換成26進制-不符合的個數(shù)
pku 3067    AC    和star差不多，還是數(shù)狀數(shù)組最好寫.
ural 1018    AC    樹形DP, 把邊的蘋果數(shù)看成在樹的節(jié)點上，然后做樹狀dp, 當然開始要先dfs一次建樹
pku 2800    AC    數(shù)論，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
                  看到題目就害怕，概率的-_-結果分析之下原來也不難
                  狀態(tài)d[i][j]表示有j種顏色,拿了i個巧克力的最優(yōu)值
                  方程: d[i+1][j+1] = d[i][j]*(c-j)/c;               (c為總顏色數(shù))
                            d[i+1][j-1] = d[i][j]*j/c;
                  由于只是保留3位小數(shù)，所以加優(yōu)化if (n>1000) n = 1000+n%2; //至于為什么要分奇偶性，這個還不太懂-_-這道算是ac一半而已
pku 2904   AC
                  dp[k][i][j]表示k個郵筒時候放鞭炮數(shù)為i..j時候的最優(yōu)值
                  轉移方程為:
                  dp[k][i][j] = min{t+max(d[k-1][i][t-1],d[k][t+1][j])};
                  狀態(tài)轉移時候就是考慮選t個鞭炮放時候爆或不爆
pku 1458   已做
pku 1579   已做 
pku 1695   AC 
                 d[i][j][k]表示到達第i個點時候另外兩輛車分別在點j和k時候的最優(yōu)值
                  方程： 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
                  先對區(qū)間做預處理, 后面不足的coaches補0;
                  d[k][j] = max{d[k-1][p]}+b[j];          0<=p<=j-m (b為處理后的區(qū)間數(shù)組,m是一臺locomotiv的容量)
                  由單調性可以在狀態(tài)轉移時候保存前一次轉移時候的最大值再和b[j-m]做比較，把O(n^2)壓縮到O(n)的時間復雜度
pku 2386   已做
pku 2479   已做
pku 2951   已做      
pku 3036   已做
pku 3014   已做
pku 2229   已做
pku 1185   AC
                  最經(jīng)典的狀態(tài)DP,我用三進制表示每行狀態(tài)，然后遞推，結果tle,分析之后，枚舉出有效狀態(tài)，再推, 1000ms左右，
                  還是不夠 快， 張偉達的論文上有更快的算法。
pku 1276   AC
                  01背包

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

pku 2486 apple tree

解法：

/////////////////////////////////////////////////////////////////////
//Apple Tree
//數(shù)組二維go，bk
//go[t][i]代表節(jié)點t的所有子樹上走i步不返回,取得的最大蘋果數(shù)
//bk[t][i]代表節(jié)點t的所有子樹上走i步并返回,取得的最大蘋果數(shù)
//求節(jié)點為x，實行不斷合并子樹求最優(yōu)值
//當前合并到了q棵子樹：
//go[x][i]就是這q棵子樹上走i步不返回的最優(yōu)值
//bk[x][i]就是這q棵子樹上走i步并返回的最優(yōu)值
//合并第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