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