8.9
POJ 3189 枚舉 多重匹配
/*
題意：N頭cow，B個(gè)barn 每個(gè)barn有容量ci，給出每頭cow對(duì)這些barn喜愛(ài)程度排序的列表
問(wèn)如何安排，使所有的牛之間的滿意度的最大差最小
題意比較繞口
設(shè)最滿意程度為u，最不滿意程度為v 則答案就是u-v了
可以直接O(B^2)枚舉[v,u]
更快的做法是，如果[v,u]可行，則[v,u+k]肯定可行！
根據(jù)這個(gè)，用兩個(gè)指針，如果可行，left++；不行right++
然后用匈牙利多重匹配做即可
這種用兩個(gè)指針枚舉的方法有通用性
*/
URAL 1699 ★★★ 建立LCA 細(xì)節(jié)處理好
/*
題意：給出一個(gè)地圖，一些地方可以走
The ground is constructed in such a way that there is exactly one way to get from one passable cell to another passable cell without visiting any cell twice.
表明是一棵樹(shù)
然后給出Q個(gè)詢問(wèn)，問(wèn)a到b的最少轉(zhuǎn)的次數(shù)
以'#'建一棵樹(shù)，預(yù)處理LCA
然后讀入查詢，找到LCA 再分情況討論一下cost[]即可
if LCA(a,b)=a da=0
else 考慮LCA(a,b)向上有沒(méi)轉(zhuǎn) 有的話da=dist[a]-dist[LCA(a,b)]-1 要-1
R*C<=100000 遞歸會(huì)爆
要用非遞歸...
*/
http://www.shnenglu.com/Yuan/archive/2010/08/09/122849.html
POJ 1149 構(gòu)圖不錯(cuò)
/*
題意: 給出m個(gè)豬圈，n個(gè)顧客。每個(gè)顧客有一些鑰匙開(kāi)豬圈的，開(kāi)了后那些豬可重新分配也行
顧客要買Bi頭豬 顧客走后門(mén)就關(guān)了就不能再調(diào)整豬了
豬圈一開(kāi)始有一些豬，豬圈可容納無(wú)限的豬
問(wèn)能賣出去的最大豬的數(shù)目
這道題，我一開(kāi)始做，構(gòu)圖是正確，一個(gè)小地方寫(xiě)錯(cuò)了，搞了我半天了！
構(gòu)圖如下：
S向豬圈連邊，容量為豬圈豬的數(shù)目
顧客向T連邊，容量為顧客要買的數(shù)目
顧客的鑰匙對(duì)應(yīng)的豬圈向顧客連邊，容量無(wú)限
如果顧客i跟前面的顧客j有共同的鑰匙就能連j->i，容量無(wú)限
我這樣子構(gòu)圖跟網(wǎng)上的有點(diǎn)不一樣，不過(guò)核心都是差不多吧
“若第i個(gè)人與他后面的第j個(gè)人有同一個(gè)豬圈的鑰匙，則從i引邊到j(luò),容量為無(wú)窮大”
網(wǎng)上詳細(xì)構(gòu)圖：http://imlazy.ycool.com/post.2059102.html
他這種構(gòu)圖方法更巧，去掉了豬圈了（豬圈數(shù)目較大） 不過(guò)對(duì)我就難想到
*/
hdu 2888
二維RMQ 用dp[i][j][k1][k2]表示矩形(i,j) (i+(1<<k1)-1,j+(1<<k2)-1)的最值
8.10
hdu 3485
求長(zhǎng)度為n的不包含101子串串的個(gè)數(shù) 跟hdu 2604類似
如圖，長(zhǎng)度為n的合法串，后綴可以是0，001,0011,00111,...
所以dp[n]=dp[n-1]+dp[n-3]+dp[n-4]+...+dp[1]
而dp[n-1]=dp[n-2]+dp[n-4]+...+dp[1]
兩式相減，得到dp[n]=2*dp[n-1]-dp[n-2]+dp[n-3]
hdu 3486
/*
題意：給出n個(gè)數(shù)，求分成多少段，使得每段的最大值之和>k （末尾不足一段的丟棄）
二分分成多少段，直接做即可 O(nlogn)
用線段樹(shù)會(huì)更慢，O(nlognlogn)
*/
hdu 3482
/*
題意:問(wèn)滿足條件的長(zhǎng)度為n的串的個(gè)數(shù) 條件是每個(gè)長(zhǎng)度為m的子串的數(shù)字要么全不同、要么全相同
分類討論
m=1 1
m=2 2^n
m>n (不存在長(zhǎng)度為m的子串) m^n
m<=n m!+m (其實(shí)，確定了前m個(gè)后面的都會(huì)確定的，所以m! 再加上全相同)
*/
hdu 3478
/*
題意：給出一個(gè)無(wú)向圖，一個(gè)起點(diǎn)，問(wèn)是否在某個(gè)時(shí)候，這個(gè)人有可能在所有點(diǎn)都可以出現(xiàn)
人不能停留在原地
畫(huà)一下圖就知道，只要存在奇圈，那么奇圈的點(diǎn)就可以任何時(shí)刻都出現(xiàn)人
同時(shí)，對(duì)于奇圈外的，奇圈可以源源不斷地傳到奇圈外
這樣肯定存在某個(gè)時(shí)刻，其他點(diǎn)也可以同時(shí)出現(xiàn)人（因?yàn)樵丛床粩鄠鞒鰜?lái)，所以肯定會(huì)波及所有）
*/
http://www.shnenglu.com/Yuan/archive/2010/08/11/123005.html
8.11
hdu 3516
/*
題意:給出n個(gè)點(diǎn)，如果滿足 xi < xj and yi > yj for all i < j 就可以在點(diǎn)(xi,yj)向點(diǎn)i,j連邊
求把他們連成一棵樹(shù)的最小代價(jià)
跟矩陣連乘的加括號(hào)一樣
dp[i][j]=min{dp[i][k]+dp[k+1][j]+(pt[k+1].x-pt[i].x)+(pt[k].y-pt[j].y)}
n<1000
需要四邊形不等式 O(n^2)
*/
hdu 3512
/*
題意：給出上面n個(gè)數(shù)，下面n個(gè)數(shù)，求完美匹配的最大邊最小。邊權(quán)定義為兩個(gè)數(shù)相乘。可以負(fù)數(shù)
應(yīng)該有點(diǎn)YY的
先分一下情況
同號(hào)：大*小 才能使最大那個(gè)最小
異號(hào)：小*小 才能使最大那個(gè)最小
一點(diǎn)貪心的思想
上面的那些正數(shù)跟下面的負(fù)數(shù)匹配
上面的那些負(fù)數(shù)跟下面的正數(shù)匹配
這樣剩下來(lái)的（當(dāng)然可以沒(méi)有剩下），肯定是同號(hào)的，而且這些數(shù)更接近于0
現(xiàn)在再來(lái)看那些 正數(shù)*負(fù)數(shù) 的情況
剛才提到“小*小 才能使最大那個(gè)最小”，而且越小的話越好
所以上面那些最大的正數(shù)跟下面那些最小的負(fù)數(shù)匹配（順序匹配，大-大，小-小）
同理，上面的那些最小的負(fù)數(shù)跟下面那些最大的正數(shù)匹配
就這樣先排序，然后找出各自的0的位置
再分類一下即可
*/
http://www.shnenglu.com/Yuan/archive/2010/08/11/123105.html
8.12
hdu 3481
/*
題意：?jiǎn)栭L(zhǎng)度為n的bad serial串的個(gè)數(shù)。bad serial 指每一個(gè)長(zhǎng)度為m的子串都不是good serial
(good serial指要么全相同，要么全不同)，所以bad serial就是兩個(gè)以上不同，但不能m個(gè)都不同
dp[i,j](1<=j<m)表示長(zhǎng)度為i的串最后j個(gè)數(shù)字互不相同的串個(gè)數(shù)（即str[i-j]與末尾這j個(gè)數(shù)中一個(gè)相同）
考慮dp[i+1,j+1]
(1)dp[i+1,j+1]+=dp[i,j]*(m-j) 選一個(gè)與i及之前j個(gè)數(shù)字都不同的
(2)dp[i+1,k]+=dp[i,j] 2<=k<=j 選一個(gè)與i之前j個(gè)數(shù)字某個(gè)相同的 str[i+1]=str[i+1-k]
還有一種特殊的就是dp[i,1]，即末尾幾個(gè)數(shù)字都相同的合法串個(gè)數(shù)
(3)dp[i+k,1]+=dp[i,j] (1+k<=m-1, j>1||i==1)
如果j=1的話有可能一連串都相同導(dǎo)致不合法，要j>1
特殊的是i=1，j=1就可取，因?yàn)?之前沒(méi)有數(shù)字，認(rèn)為與1不同（跟j>1一樣）
心得：只考慮最后一個(gè)字符（第i+1），考慮怎么合法過(guò)來(lái)的
dp轉(zhuǎn)移時(shí)，由之前的轉(zhuǎn)移過(guò)來(lái)難寫(xiě)的話，寫(xiě)成從當(dāng)前擴(kuò)展到之后的！
按照題意定義狀態(tài)，這里要2個(gè)以上不同，定義末尾有j個(gè)不同（j=1時(shí)是特殊情況，即末尾可以幾個(gè)連續(xù)相同）
*/
hdu 3510
/*
題意：給出n個(gè)任務(wù)，m臺(tái)機(jī)器 任務(wù)間有依賴關(guān)系，這些關(guān)系構(gòu)成一棵樹(shù) 問(wèn)最短完成時(shí)間
顯然完成時(shí)間不能少于最深的深度，而每次只能選葉子被機(jī)器加工
這樣，每次選深度最深的葉子加工（用PQ）直到完成
如果不選深度最深的，可能會(huì)使時(shí)間變長(zhǎng)
*/
hdu 3508
/*
題意：?jiǎn)杗內(nèi)，與n互質(zhì)的所有數(shù)的乘積模n是多少
打了一些數(shù)據(jù)，發(fā)現(xiàn)只有1和n-1
當(dāng)n=1,2,4,p^k,2*p^k時(shí) 答案為n-1
*/
hdu 3483
/*
題意：給出N,x,M 要計(jì)算
N
∑(k^x)*(x^k) MOD M
k=1
x
用到二項(xiàng)式定理，(n+1)^x = ∑C(x,k)n^k
k=0
然后構(gòu)造矩陣，求和 S(n)表示前n項(xiàng)和
http://www.shnenglu.com/Yuan/archive/2010/08/13/123268.html
*/
hdu 3366
/*
如果已經(jīng)知道走這些passage的順序的話，應(yīng)該可以dp出來(lái)的
但是這里不確定順序，要選擇最優(yōu)，可以按照P/Q從大到小排序
遇到匪徒幾率Q越小，出去幾率P越大，肯定是我們優(yōu)先考慮的！
Help Bill to find out the probability that he can escape from this castle if he chose the optimal strategy.
dp[i][j]表示現(xiàn)在有錢(qián)j，在i個(gè)passage處，最后能夠出去的概率
dp[n-1,j]=P[n-1]
dp[i,j]=P[i]+Q[i]*dp[i+1,j-1]+(1-P[i]-Q[i])*dp[i+1,j] j>0
dp[i,j]=P[i]+(1-P[i]-Q[i])*dp[i+1,j] j=0
概率題期望題，一般都是表示現(xiàn)在離目標(biāo)的值
（因?yàn)楫?dāng)前接下來(lái)的方案確定了，概率也知道了，而當(dāng)前從前面過(guò)來(lái)就不確定概率了，其概率跟路徑有關(guān)）
*/
8.13
zoj 2597
/*
題意：題目定義一種n位的yellow code 相鄰兩個(gè)數(shù)之間要差別至少[n/2]。讓你構(gòu)造出n位的yellow code
觀察發(fā)現(xiàn)，n位可以由n-1位復(fù)制一遍，然后最后一列再算一下得來(lái)
對(duì)最后一列的前n個(gè)爆搜即可，后n個(gè)是前n個(gè)取反
*/
zoj 1619
/*
題意：n個(gè)人n個(gè)禮物混亂，問(wèn)每人取一個(gè)，最終m個(gè)人取到自己的概率
直接用錯(cuò)排公式即可 C(n,m)*D[n-m]/n!
或者dp
dp[i,j]表示前i個(gè)人j個(gè)取得自己的概率
dp[i,j]可以先安置好i-1的，然后再用乘法原理乘起來(lái)
dp[i,j] = dp[i-1,j]*(i-1-j)/i 先把i-1個(gè)人安置出j個(gè)人取到自己的情況，為使還是j個(gè)人，第i個(gè)人需跟剩下的i-1-j個(gè)人其中一個(gè)交換
+ dp[i-1,j-1]*1/i 先把i-1個(gè)人安置出j-1個(gè)人取到自己的情況，然后第i個(gè)人取到自己的概率
+ dp[i-1,j+1]*(j+1)/i 先把i-1個(gè)人安置出j+1個(gè)人取到自己的情況，然后第i個(gè)人跟這j+1個(gè)人之一交換
*/
8.14
zoj 2703 被這道題卡了好久，還是wa
8.16
做了下伸展樹(shù)的
spoj 4487 1470
8.17
cii 2193
/*
sample：
##-(##+###)
3333333
用下面的數(shù)字去填上面的#使得該式子最大 有多個(gè)時(shí)輸出字典序最小的
首先，去括號(hào)
沒(méi)有真的去掉，利用括號(hào)前的那些正負(fù)號(hào)來(lái)確定每個(gè)數(shù)字真實(shí)的正負(fù)號(hào)
為每個(gè)數(shù)字或者括號(hào)這樣的整體添加正負(fù)號(hào)
如下面的例子 +(-(+a+b)+c)
這里在最外的括號(hào)及a也要有一個(gè)正號(hào)
為了轉(zhuǎn)化出上面的式子用一個(gè)棧
1) '(' 如果其前面不是符號(hào)，就需要添加一個(gè)符號(hào)（跟棧頂一樣） push(top)
2) '(' pop
3) '±' push(op^top) 這里把負(fù)號(hào)當(dāng)成1
4) '#' 如果其前面不是符號(hào)就需要添加一個(gè)符號(hào)（跟棧頂一樣） push(top)
然后連讀... 存起這個(gè)數(shù) 再pop
正數(shù)存在positive 負(fù)數(shù)存在negative
現(xiàn)在就來(lái)貪心 先將digit排序
對(duì)于正數(shù)，每次將digit里最大的數(shù)賦值給positive里長(zhǎng)度最大的，或長(zhǎng)度相同靠后的
對(duì)于負(fù)數(shù)，每次將digit里最小的數(shù)賦值給negative里長(zhǎng)度最大的，或長(zhǎng)度相同靠前的
可用一個(gè)堆來(lái)實(shí)現(xiàn)，取出后再放進(jìn)去（這時(shí)長(zhǎng)度少1了）
*/