Problem A: Modular multiplication of polynomials
A題是一道模擬題，主要考察選手?jǐn)?shù)組的和循環(huán)控制的運(yùn)用能力。
題目要求模擬的是多項(xiàng)式除法，且給出了具體的運(yùn)算規(guī)則，異或運(yùn)算。給出f(x),g(x)兩個(gè)多項(xiàng)式相乘，然后除以h(x)多項(xiàng)式，求其余數(shù)(亦為多項(xiàng)式)。先用兩重循環(huán)將f(x),g(x)相乘，用一數(shù)組記錄相乘后多項(xiàng)式k(x)的x^i的系數(shù)，然后做多項(xiàng)式除法。設(shè)被除數(shù)的最高次為x^n, 除數(shù)h(x)的最高次為y^m, 直到n<m時(shí)候循環(huán)結(jié)束。
Problem B:Checking an Alibi
這題其實(shí)就是求每個(gè)點(diǎn)到1號(hào)點(diǎn)的最短路。 然后判斷每只牛所在地到1號(hào)點(diǎn)的需時(shí)是否小于等于M.
題目沒明確說(shuō)有沒有重邊，一般情況下是要考慮的。 在比賽時(shí)，我們認(rèn)為數(shù)據(jù)中有長(zhǎng)度為0的邊，與題目中1－70000不符。但ACM就是這樣，題目出問(wèn)題是常有的事。在確定自己程序沒錯(cuò)的前提下，選手們只能考經(jīng)驗(yàn)和感覺去猜。
Problem C:The Game of Mafia
直接搜索就行了，白天和黑夜輪著搜，注意一下只剩下他自己的時(shí)候的情況就可以了。
Problem D:Multiplication Puzzle
這題是經(jīng)典的動(dòng)態(tài)規(guī)劃。
用a[1000]表示愿數(shù)組，d[i][j]表示讓第i個(gè)數(shù)與第j個(gè)數(shù)碰面（刪掉他們之間的元素）的最小代價(jià)。
方程是：
d[i][j]= max(d[i][k]+d[k][j]+a[k]*a[i]*a[j]，i<k<j)
時(shí)間復(fù)雜度是O(n^3)。
Problem E:Zip
這題有兩種操作A和B
對(duì)于操作A來(lái)說(shuō)只要統(tǒng)計(jì)一下各種字母出現(xiàn)的次數(shù)就可以很容易得到S'了
而對(duì)于操作B來(lái)說(shuō)統(tǒng)計(jì)一下序列S'的各種字母的出現(xiàn)次數(shù)，然后根據(jù)p就可以得到序列的第一個(gè)字母和第二個(gè)字母，然后根據(jù)根據(jù)第一個(gè)字母就可以得到最后一個(gè)字母
比如對(duì)于樣例來(lái)說(shuō)：
xelpame 7
a x
e e
e l
l p
m a
p m
x e
確實(shí)了第二個(gè)字母是x,第一個(gè)字母是e，e出現(xiàn)第一次的時(shí)候就可以得到最后一個(gè)字母是e，
所以根據(jù)最后一個(gè)字母倒過(guò)來(lái)生成前面的序列，從對(duì)應(yīng)e的最后一次出現(xiàn)，可以得到倒數(shù)第二個(gè)字母是l，然后對(duì)于l最后出現(xiàn)一次，可以確實(shí)l前面是p，然后一直填上去就可以得到原序列S=example
Promble F: Wall
F題考察的是選手基本的計(jì)算幾何知識(shí)。
讀懂題意后就是求凸包的周長(zhǎng)+一個(gè)圓的周長(zhǎng), 求凸包可以先選取最左下角的點(diǎn)，然后以該點(diǎn)為基準(zhǔn)對(duì)所有點(diǎn)作極角排序，然后就是用Graham掃描法求凸包了。
Problem G:Ouroboros Snake
這題可以用構(gòu)造算法。 題目有一個(gè)限制，2^N 個(gè)數(shù)不重不漏的出現(xiàn)，這就是關(guān)鍵所在。可以想到，必然有N個(gè)零連著，這就是要求數(shù)列的開始（以后不可能有N個(gè)零連著了）。然后我們每次取后面N-1位，加0看看前是否有這N位。有，那么這一位不能是0（要不就違反了不重不漏了），只能是1。否則就加0。
但是僅僅這樣并不能得出正確的答案。 怎么辦呢？
想到這個(gè)構(gòu)造算法的結(jié)尾必然是很多個(gè)1連著（因?yàn)榧?的話，這N位在前面出現(xiàn)過(guò)了）。理想的情況是N個(gè)1。那么象 1000，1100，1110這些前面全是1，后面全是0的數(shù)就在首尾相接（這是一個(gè)圓環(huán)）的時(shí)候出現(xiàn)了。
修正辦法立刻有了，就是在一開始時(shí)把象 1000，1100，1110這些前面全是1，后面全是0的數(shù)標(biāo)志為已經(jīng)出現(xiàn)過(guò)。然后用我們之前說(shuō)的那種構(gòu)造法一位位的確定那一位是0還是1。
經(jīng)過(guò)檢驗(yàn)，發(fā)現(xiàn)這樣就符合要求了。
PKU 3093 Margaritas on the River Walk
先對(duì)輸入的數(shù)組排序，然后類似于01對(duì)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]大，肯定這時(shí)候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(bǔ)[i]加進(jìn)以前的選擇里面
else d[i][j]++;//a[i]單獨(dú)作為一個(gè)選擇(這里需要先對(duì)a[i]排序，消除后效性)
}
}
}
}
PKU 1037 A decorative fence
先dp算出以i為起點(diǎn)的序列的個(gè)數(shù)，再組合數(shù)學(xué)
td[n][i]和tu[n][i]分別表示個(gè)數(shù)為n，以i開始的上升和下降的序列個(gè)數(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
雙調(diào)歐幾里德旅行商問(wèn)題(明顯階段dp)
動(dòng)態(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為二進(jìn)制表示點(diǎn)的狀態(tài), j為當(dāng)前節(jié)點(diǎn), k為到達(dá)j的前驅(qū)節(jié)點(diǎn))
pku 2513 AC 火星人了, 第一次用hash, 以前都是用map偷懶的, 不過(guò)這題用trie應(yīng)該會(huì)更好, 建好圖之后就是DFS判連通,然后歐拉回路了.
pku 3216 AC 二分圖最小路徑覆蓋, 建立圖的時(shí)候要求一次多源最短路(這個(gè)害我wa了好幾次).
pku 3211 AC 理解題目后就是最每一種顏色做01背包了.
pku 3214 AC 這的確是一道好題, 先后序遍歷heap,每次減去一個(gè)sub值, 然后對(duì)得到的序列求最長(zhǎng)不降子序列,要nlogn的才能過(guò).
pku 3213 AC 看了解題報(bào)告才會(huì)做,先進(jìn)行坐標(biāo)轉(zhuǎn)換[(x-y)/2, (x+y)/2], 然后求sig|xi-xj|+sig|yi-yj|的最小值.
pku 3215 AC 理解題意后其實(shí)是一道比較簡(jiǎn)單的計(jì)算幾何,但是很容易WA,按方程和X軸的交點(diǎn)分段,然后枚舉交點(diǎn),統(tǒng)計(jì)x軸上下各自線段個(gè)數(shù)
pku 1177 AC 線段樹, 4k的代碼, 學(xué)會(huì)了測(cè)度和連續(xù)線段數(shù), 記在筆記本上了, 隨時(shí)復(fù)習(xí).
pku 2564 AC 再次火星人,第一次寫trie, 標(biāo)號(hào)法DP, 題目描述很陰險(xiǎn).
tju 2762 AC 基本的線段樹, 用了ghost_wei的寫法，省了B[]和E[]，基本思想是二分
pku 1699 AC 簡(jiǎn)單搜索，寫下的目的是這道題用了alpha-beta剪枝
pku 1195 AC 二維樹狀數(shù)組，詳細(xì)看李睿的論文吧.
pku 2482 AC 二叉統(tǒng)計(jì)樹+樹狀DP+掃描線，絕對(duì)是一道好題.
pku 1038 AC 被這題惡了一天，算法藝術(shù)上的方法超時(shí)，換了解題報(bào)告的那個(gè)A(x, y, p)的狀態(tài)定義才過(guò)了，程序?qū)懙恼婧茫貏e是那滾動(dòng)數(shù)組
ural 1031 AC 由單調(diào)性，可以O(shè)(n)的時(shí)間與處理，然后就O(n)的線性DP, 陰險(xiǎn)地方是start可能小于end.
pku 1850 AC 組合數(shù)學(xué)啊，以前一直不會(huì)，今天終于搞出來(lái)了，用DP先算出不符合的字符串?dāng)?shù)，然后將輸入字符串轉(zhuǎn)換成26進(jìn)制-不符合的個(gè)數(shù)
pku 3067 AC 和star差不多，還是數(shù)狀數(shù)組最好寫.
ural 1018 AC 樹形DP, 把邊的蘋果數(shù)看成在樹的節(jié)點(diǎn)上，然后做樹狀dp, 當(dāng)然開始要先dfs一次建樹
pku 2800 AC 數(shù)論，k mod i = k - floor(k/i) * i
pku 2516 AC 拆點(diǎn)，然后二分圖最佳匹配
pku 1014 已做
pku 1037
pku 1050 已做
pku 1088 已做
pku 1141 已做
pku 1159 已做
pku 1163 已做
pku 1322 AC
看到題目就害怕，概率的-_-結(jié)果分析之下原來(lái)也不難
狀態(tài)d[i][j]表示有j種顏色,拿了i個(gè)巧克力的最優(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; //至于為什么要分奇偶性，這個(gè)還不太懂-_-這道算是ac一半而已
pku 2904 AC
dp[k][i][j]表示k個(gè)郵筒時(shí)候放鞭炮數(shù)為i..j時(shí)候的最優(yōu)值
轉(zhuǎn)移方程為:
dp[k][i][j] = min{t+max(d[k-1][i][t-1],d[k][t+1][j])};
狀態(tài)轉(zhuǎn)移時(shí)候就是考慮選t個(gè)鞭炮放時(shí)候爆或不爆
pku 1458 已做
pku 1579 已做
pku 1695 AC
d[i][j][k]表示到達(dá)第i個(gè)點(diǎn)時(shí)候另外兩輛車分別在點(diǎn)j和k時(shí)候的最優(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的，結(jié)果用map偷懶了。
d[i] = min{d[j]} + 1 0<=j<i && j+1..i字符合法
pku 1953 已做
pku 1976 AC
先對(duì)區(qū)間做預(yù)處理, 后面不足的coaches補(bǔ)0;
d[k][j] = max{d[k-1][p]}+b[j]; 0<=p<=j-m (b為處理后的區(qū)間數(shù)組,m是一臺(tái)locomotiv的容量)
由單調(diào)性可以在狀態(tài)轉(zhuǎn)移時(shí)候保存前一次轉(zhuǎn)移時(shí)候的最大值再和b[j-m]做比較，把O(n^2)壓縮到O(n)的時(shí)間復(fù)雜度
pku 2386 已做
pku 2479 已做
pku 2951 已做
pku 3036 已做
pku 3014 已做
pku 2229 已做
pku 1185 AC
最經(jīng)典的狀態(tài)DP,我用三進(jìn)制表示每行狀態(tài)，然后遞推，結(jié)果tle,分析之后，枚舉出有效狀態(tài)，再推, 1000ms左右，
還是不夠 快， 張偉達(dá)的論文上有更快的算法。
pku 1276 AC
01背包
有空把以前的也再做一次!~
pku 2486 apple tree
解法：
/////////////////////////////////////////////////////////////////////
//Apple Tree
//數(shù)組二維go，bk
//go[t][i]代表節(jié)點(diǎn)t的所有子樹上走i步不返回,取得的最大蘋果數(shù)
//bk[t][i]代表節(jié)點(diǎn)t的所有子樹上走i步并返回,取得的最大蘋果數(shù)
//求節(jié)點(diǎn)為x，實(shí)行不斷合并子樹求最優(yōu)值
//當(dāng)前合并到了q棵子樹：
//go[x][i]就是這q棵子樹上走i步不返回的最優(yōu)值
//bk[x][i]就是這q棵子樹上走i步并返回的最優(yōu)值
//合并第q+1棵子樹(不妨設(shè)第q+1棵子樹的根為y)的時(shí)候，有
//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