字符串少量習(xí)題小結(jié).
spoj694(易) 后綴數(shù)組
求一個(gè)字串的不同子串個(gè)數(shù).
按rank考慮子串.加入子串S[i]時(shí),獲得了len-Sa[i]個(gè)不同子串.但其中height[i]個(gè)已經(jīng)屬于S[i-1]了,所以實(shí)際子串?dāng)?shù)增加了len-Sa[i]-S[i-1]. 順序掃一遍height數(shù)組即得解.
spoj687(中) 后綴數(shù)組
求一個(gè)串的重復(fù)次數(shù)最多的連續(xù)重復(fù)子串.
設(shè)周期為L(zhǎng)的連續(xù)重復(fù)子串存在,則點(diǎn)0,L,2L,...,kL必能覆蓋到一個(gè)完整周期. 因此對(duì)L,考察這些點(diǎn)的字符相等情況,LCP情況,可得到L的解.
枚舉L.
復(fù)雜度是O(n/1+n/2+...+n/n) = O(nlogn)
pku3693(中) 后綴數(shù)組
同spoj687,只是結(jié)果還要輸出字典序最小的滿足條件的串.可以借助rank數(shù)組直接比較字典序.只是要注意在考察點(diǎn)kL時(shí),要把以(k-1)L+1,...,(k+1)L-1為起點(diǎn)的子串都訪問一遍找最小rank者.
pku1743(中) 后綴數(shù)組
找一個(gè)串的最長(zhǎng)不重疊相同子串.
由于某子串可能整體加上(或減去)相同偏移量,因此不直接對(duì)原串操作,而是構(gòu)造新串b, 其中b[i]=a[i]-a[i-1]. 此時(shí)求得最長(zhǎng)不重疊相同子串的長(zhǎng)度+1便是結(jié)果.
可以二分長(zhǎng)度,或者棧掃描(*)直接求最大長(zhǎng)度.
whu1084(易) 后綴數(shù)組
求重復(fù)次數(shù)最多的不重疊子串長(zhǎng)度
spoj687的簡(jiǎn)單版,不要求循環(huán)節(jié)連續(xù),直接二分長(zhǎng)度即可.
pku2778(易) 多串匹配+DP AC自動(dòng)機(jī),trie圖
字符集大小為4, 給出m個(gè)(m<=10)禁止單詞(長(zhǎng)度<=10), 求長(zhǎng)度為n(n<=2*10^9)的不包含任何禁止單詞的串的個(gè)數(shù).
對(duì)禁止單詞建立trie圖,并計(jì)算出圖中任意合法結(jié)點(diǎn)之間的轉(zhuǎn)移數(shù),這樣便求得1步轉(zhuǎn)移矩陣.
做n次方后的矩陣,第1行中屬于合法狀態(tài)的元素之和即為解.
禁止單詞總長(zhǎng)度不超過100,因此合法狀態(tài)亦<100.總復(fù)雜度100^3*logN
zju3228(中) Searching the String 后綴數(shù)組,AC自動(dòng)機(jī),trie圖
原串長(zhǎng)10^5, 現(xiàn)在有10^5次查詢, 每次查詢一個(gè)長(zhǎng)度<=6的模式串在原串中的最大匹配次數(shù).
模式串的匹配方式有可重疊和不可重疊兩種, 需針對(duì)查詢的類型返回相應(yīng)值.
后綴數(shù)組解法(在線):
對(duì)原串建立sa和height數(shù)組.由于模式串長(zhǎng)度最大只有6, 我們可以將height數(shù)組分別按L=1..6分組,預(yù)處理求出相應(yīng)長(zhǎng)度每組內(nèi)不重疊子串的最大匹配次數(shù),此過程O(6*nlogn).
另外由于sa數(shù)組將所有后綴按字典序排好了,所以對(duì)一個(gè)詢問, 可以二分找到它在sa中第一次出現(xiàn)的位置p1和最后一次出現(xiàn)的位置p2, 則p2-p1+1就是可重疊匹配的答案. 對(duì)不可重疊匹配,只需直接返回p1處預(yù)處理時(shí)的值. 每次查詢O(logn).
trie圖,AC自動(dòng)機(jī)解法(離線):
把所有查詢建trie圖, 對(duì)圖中的每個(gè)有效結(jié)點(diǎn)維護(hù):該串長(zhǎng)度,兩類查詢的計(jì)數(shù),該串上一次被匹配的位置, 還要用個(gè)鏈表記下這個(gè)串屬于哪些查詢.
剩下的就是經(jīng)典的自動(dòng)機(jī)多串匹配了.
(*)關(guān)于棧掃:
height數(shù)組具有區(qū)間性,各個(gè)不同前綴被相應(yīng)的極小值隔開,而一個(gè)區(qū)間中又有多個(gè)子區(qū)間.各區(qū)間值大于區(qū)間端點(diǎn)的部分互不影響.因此可以維護(hù)一個(gè)存放height值不減的棧,棧中每個(gè)元素的附屬值, 記錄了它在棧中相鄰的兩個(gè)元素為端點(diǎn)的連續(xù)區(qū)間內(nèi)所有height值不小于它的必要信息.比如此題要記錄height>=k的連續(xù)區(qū)間內(nèi)sa[i] 的最大值和最小值.
棧掃描的經(jīng)典例子移步pku2559.
(**)trie圖備忘:
比trie樹多了個(gè)后綴指針psuf. 設(shè)當(dāng)前結(jié)點(diǎn)字母為c, 則psuf指向父親的后綴的pch[c].
trie樹中的后代結(jié)點(diǎn)指針pch(已經(jīng)更名為狀態(tài)轉(zhuǎn)移指針),當(dāng)相應(yīng)后代存在時(shí),指向后代;否則指向當(dāng)前結(jié)點(diǎn)的后綴的相應(yīng)后代,即pch[k]=node[pa].pch[k].
后綴指針: 在接下來的狀態(tài)轉(zhuǎn)移中,當(dāng)前結(jié)點(diǎn)與它的后綴結(jié)點(diǎn)等價(jià).
后代結(jié)點(diǎn)指針: 在當(dāng)前狀態(tài)下,接收到字符ch時(shí),轉(zhuǎn)移到pch[ch]指向的結(jié)點(diǎn).
二分圖匹配的巧妙應(yīng)用相當(dāng)巧妙!CTU 2005 Openhttp://acm.pku.edu.cn/JudgeOnline/problem?id=2990題意:8*8的棋盤, 初始放置2個(gè)相同的棋子. Alice和Bob輪流行動(dòng). 每次行動(dòng)可以把其中一個(gè)棋子移到它上下左右相鄰格內(nèi)(某些格子壞掉了,則不能移). 當(dāng)某人的移動(dòng)使兩棋子重合時(shí), 他贏. 另, 一局中不能出現(xiàn)重復(fù)的局面. 比如(0,0)(4,0) -> (1,0)(4,0)合法, 此時(shí)如果再(1,0)(4,0) -> (0,0)(4,0)則非法. 當(dāng)一個(gè)人無(wú)子可動(dòng)時(shí), 他輸.兩人都用最優(yōu)策略. 問先手的Alice必勝還是必?cái)?解:把每個(gè)合法狀態(tài)看成一個(gè)頂點(diǎn), 則狀態(tài)轉(zhuǎn)移就是向其它點(diǎn)連邊. 這樣建的圖是二分圖.而兩人下棋, 就是在圖上以初始狀態(tài)的頂點(diǎn)為起點(diǎn), 沿邊移動(dòng). 由于建的圖是由所有合法狀態(tài)與合法移動(dòng)組成的, 因此, 移動(dòng)到哪個(gè)集合(A與B), 就表示輪到誰(shuí)行動(dòng). 當(dāng)無(wú)法再移動(dòng)時(shí), 點(diǎn)在哪個(gè)集合就表示對(duì)應(yīng)的人輸了.狀態(tài)不重復(fù)出現(xiàn), 表示移動(dòng)路徑?jīng)]有環(huán).誰(shuí)贏誰(shuí)輸, 與路徑長(zhǎng)度的奇偶性密切相關(guān).考慮二分圖的最大匹配, 也是個(gè)找交替路徑擴(kuò)張的過程.設(shè)起點(diǎn)為v, 分情況討論v的狀態(tài)與路徑長(zhǎng)度的關(guān)系: (1) v是自由點(diǎn). 這表示v的任意鄰接點(diǎn)vB都是浸潤(rùn)點(diǎn). 不管選哪個(gè)vB, 都可以沿著它的匹配邊走到vA'. 只要Bob每次都沿匹配邊走, 由于不可能達(dá)到另一個(gè)自由點(diǎn), 因此終點(diǎn)必屬于A, Bob必勝.(2) v是浸潤(rùn)點(diǎn), 此時(shí)v所在的交替路徑兩個(gè)端點(diǎn)分布情況可能有幾種: a)對(duì)所有交替路徑, 端點(diǎn)都在B集. 這時(shí)只要Alice每次都沿著匹配邊走, 必勝. b)存在一條交替路徑, 端點(diǎn)都在A集. 把沿v的匹配邊走的那一半全部置反, 就變成(1)的狀態(tài)了, 因此2者等價(jià). c)沿v的匹配邊走的那一半全終止于B, 另一半終止于A. 只要Alice一開始就沿匹配邊走, 后面策略同a. 其它情形不可能在最大匹配中出現(xiàn), 故不討論. 這正是充分利用了最大匹配的性質(zhì).因此對(duì)本題先求最大匹配, 然后判斷是否為(1)或(2b), 即可知?jiǎng)儇?fù).代碼如下:
1 #include <iostream>
2 using namespace std;
3
4 const int MAX_VERT = (1<<12)+1;
5 const int MAX_EDGE = MAX_VERT * 16;
6 struct EDGE{
7 int v,e;
8 }edg[ MAX_EDGE ];
9 int se, gg[ MAX_VERT ], nv;
10 int start;
11 int mat[ MAX_VERT ];
12 bool ok[ MAX_VERT ], vis[ MAX_VERT ];
13
14 int N,M;
15 char bo[20][20];
16
17 bool chkpt(int x, int y)
18 {
19 if(x<0 || x>=M || y<0 || y>=N) return false;
20 if(bo[y][x]=='#') return false;
21 return true;
22 }
23
24 //判斷合法狀態(tài)
25 bool chksta(int x1, int y1, int x2, int y2)
26 {
27 if(!chkpt(x1,y1) || !chkpt(x2,y2)) return false;
28 if(abs(x1-x2)+abs(y1-y2)<=1) return false;
29 return true;
30 }
31
32 //位壓縮存狀態(tài)
33 int encode(int x1, int y1, int x2, int y2)
34 {
35 if(y1 > y2 || (y1==y2 && x1 > x2)) //小點(diǎn)放前面, 避免重復(fù)狀態(tài)
36 swap(y1,y2), swap(x1,x2);
37 int v = x1;
38 v = (v<<3) | y1;
39 v = (v<<3) | x2;
40 v = (v<<3) | y2;
41 return v;
42 }
43
44 inline void addedge(int u, int v)
45 {
46 edg[se].v = v;
47 edg[se].e = gg[u];
48 gg[u] = se++;
49 }
50
51 void addmove(int u, int x1, int y1, int x2, int y2)
52 {
53 if(!chksta(x1, y1, x2, y2)) return ;
54 int v = encode(x1, y1, x2, y2);
55 addedge(u, v);
56 }
57
58 //添加狀態(tài)轉(zhuǎn)移的邊
59 void gene(int x1, int y1, int x2, int y2)
60 {
61 if(!chksta(x1,y1,x2,y2)) return;
62 int u = encode(x1,y1,x2,y2);
63 ok[u] = true;
64 mat[u] = -1;
65 addmove(u, x1+1, y1, x2, y2);
66 addmove(u, x1-1, y1, x2, y2);
67 addmove(u, x1, y1+1, x2, y2);
68 addmove(u, x1, y1-1, x2, y2);
69 addmove(u, x1, y1, x2+1, y2);
70 addmove(u, x1, y1, x2-1, y2);
71 addmove(u, x1, y1, x2, y2+1);
72 addmove(u, x1, y1, x2, y2-1);
73 }
74
75 //建圖
76 void input()
77 {
78 int x1, y1, x2, y2;
79
80 for(y1=0; y1<N; y1++)
81 scanf("%s",bo[y1]);
82
83 se = 1;
84 memset(gg,0,sizeof(gg));
85 nv = M << 9;
86 memset(ok, false, sizeof(ok));
87 memset(mat, 0xff, sizeof(mat));
88 memset(vis, false, sizeof(vis));
89
90 int c=0, tx[2],ty[2];
91 for(y1=0; y1<N; y1++){
92 for(x1=0; x1<M; x1++){
93 if(bo[y1][x1] == 'P')
94 tx[c]=x1, ty[c]=y1, c++;
95 for(x2=x1+1; x2<M; x2++)
96 gene(x1,y1,x2,y1);
97 for(y2=y1+1; y2<N; y2++)
98 for(x2=0; x2<M; x2++)
99 gene(x1,y1,x2,y2);
100 }
101 }
102 start = encode(tx[0], ty[0], tx[1], ty[1]);
103 }
104
105 bool hungrey(int r)
106 {
107 //這個(gè)匹配函數(shù)不分XY集, 因此匹配點(diǎn)雙方的mat標(biāo)記都要修改
108 int i,j,k;
109 vis[r] = true;
110 for(j=gg[r]; j>0; j=edg[j].e){
111 int v = edg[j].v;
112 if(!vis[v]){
113 vis[v] = true;
114 if(mat[v]==-1 || hungrey(mat[v])){
115 mat[v] = r;
116 mat[r] = v;
117 return true;
118 }
119 }
120 }
121 return false;
122 }
123
124 int main()
125 {
126 int i,j,k;
127 while(scanf("%d %d",&N,&M)!=EOF){
128 input();
129 if( !ok[start] ){
130 puts("Alice wins.");
131 continue;
132 }
133
134 for(i=0; i<nv; i++){
135 memset(vis, false, sizeof(vis));
136 if( mat[i]==-1 ) hungrey(i);
137 }
138 if( mat[start]!=-1 ){ //判斷是否是(2b)并轉(zhuǎn)化為(1)
139 memset(vis, false, sizeof(vis));
140 vis[start] = true;
141 if(hungrey(mat[start]))
142 mat[start] = -1;
143 }
144
145 if( mat[start]!=-1 )
146 puts("Alice wins.");
147 else
148 puts("Bob wins.");
149 }
150 return 0;
151 }
152
http://acm.scs.bupt.cn/onlinejudge/showproblem.php?problem_id=1586
題意:
一共有K(K<=50)種字母,組成一個(gè)長(zhǎng)度為L(zhǎng)(L<=10^18)的串.
這個(gè)串需滿足要求:
對(duì)任意的 1<=i<=L , 以及任意的 1<=k1,k2<=K 且 k1!=k2, 在前綴 s[1..i]中,字母k1的個(gè)數(shù)和字母k2的個(gè)數(shù)之差的絕對(duì)值<=2.
例如: abac是合法的; 而abbbc不合法, 因?yàn)榍熬Yabbb中字母b和c的個(gè)數(shù)相差為3.
建立狀態(tài):
從<=2 入手找狀態(tài). 可以設(shè)前c個(gè)字母中, 最小個(gè)數(shù)為m, 字母數(shù)為m的種類為i, m+1的種類為j, m+2的種類為k. 化簡(jiǎn)狀態(tài)可得 比最小個(gè)數(shù)多1的種類為i,比最小個(gè)數(shù)多2的種類為j. 而經(jīng)過數(shù)學(xué)推導(dǎo)(不懂), 可知 j+2k<K, 也就是當(dāng) c%K 已知時(shí), 可直接由k確定i和j. 這樣狀態(tài)數(shù)為 50*50=2500, 還是不能用矩陣法. 進(jìn)一步思考, 由c%K=0時(shí)的結(jié)果可以推出c%K=1時(shí)的結(jié)果,遞推可把c%K=0...K-1的結(jié)果都求出. 而要求L步的結(jié)果數(shù),實(shí)際上并不用去管是1步1步走,還是2步2步走. 所以我們可以直接一次走K步! 這樣就把c%K這一維狀態(tài)也消除了.
于是可以設(shè)矩陣m[i,j]為c%K=0時(shí),k經(jīng)過K步從i轉(zhuǎn)移到j(luò)的方法數(shù).
這樣先求出 L-L%K 步的方法數(shù), 最后 L%K 步直接dp即可.
整體復(fù)雜度為 K^3*log(L/K).
本題關(guān)鍵: 由k和c%K唯一確定i和j; 一次走K步, 消除狀態(tài)c%K, 實(shí)際上不同c%K對(duì)應(yīng)的狀態(tài)是冗余的, 因?yàn)椴挥萌ス苤虚g的過程.
E. Ski Lessons (DP)
題意:
滑雪場(chǎng)有N(N<=10000)種項(xiàng)目, 可以從任意時(shí)刻開始, 可以反復(fù)參加. 每種項(xiàng)目要求參與者技能值(<=100)至少為c[i], 耗費(fèi)連續(xù)的d[i]單位時(shí)間.
此外,滑雪場(chǎng)提供S(S<=100)個(gè)培訓(xùn)課程. 每個(gè)課程開始時(shí)間為m[i], 持續(xù)時(shí)間l[i], 結(jié)束后, 參加者的技能值變?yōu)閍[i]. 如果選擇參加某個(gè)課程,不能遲到早退. 只能同時(shí)參加一個(gè)課程.
一個(gè)人在任意時(shí)刻只能做一件事, 而且他總共有 T(T<=10000) 單位時(shí)間. 他必須在時(shí)刻T結(jié)束所有活動(dòng).
問如何安排可以使得此人參加最多次滑雪項(xiàng)目, 求最大次數(shù).
解:
O(100*N)預(yù)處理, len[i][j]表示技能值為i時(shí), 參加一次任意項(xiàng)目的最短時(shí)間.
O(S*S)DP, dp[i]表示在課程i開始的前一時(shí)刻, 已參加項(xiàng)目的最大次數(shù).
注意到, 結(jié)束一項(xiàng)課程后人的技能值是一定的. 因此, 可以枚舉參加i之前最近參加的課程k, 兩次課程之間的收益可直接計(jì)算. 則dp[i] = max(dp[k]+ (m[i]-m[k]-l[k])/len[a[k]]).
D.
題意:
給一個(gè)初值C,和兩個(gè)迭代公式 fi(x)=a[i]*x/d[i]+b[i], 公式中1<=d<a<=20, 1<=b<=20,且都為整數(shù). 除法為整型除法.
由初值C開始迭代, 計(jì)算出來的結(jié)果又可以任意代入公式繼續(xù)迭代.
求能得到的所有數(shù)(包括C)中第N大的. 1<=N<=400000.
解:
一個(gè)隊(duì)列,兩個(gè)指針,不斷分別將指向的兩個(gè)值代入兩個(gè)公式計(jì)算,取小的加入列尾.注意判重.
G.
題意:
無(wú)向圖,頂點(diǎn)集為U, 給一個(gè)不包含源點(diǎn)v的子頂點(diǎn)集S, 問至少要在U-S-{v}中刪掉多少個(gè)點(diǎn),才能完全割斷S與v的聯(lián)系. S中沒有點(diǎn)與v直接相鄰.
解:
限制頂點(diǎn)流量,最大流(最小割),將點(diǎn)i0拆成i->i',所有入邊指向i,出邊從i'指出.對(duì)有可能損壞的點(diǎn),邊容量置1,不可能損壞的點(diǎn)置inf.其它邊容量為inf.
I.
題意:
給一個(gè)顏色序列s, 序列長(zhǎng)度<=40000, 其中包含的顏色種類<=40000. 可以將原序列任意分割, 分割后每一個(gè)子段的代價(jià)分別為f(k)=k*k,其中k為子段中包含的顏色種類數(shù).
求一個(gè)分割方案,使sigma(f(k))最小.
解:
DP.關(guān)鍵的優(yōu)化在于,轉(zhuǎn)移dp[i]時(shí),只用枚舉計(jì)算min{dp[j]+cost(j+1,i)},其中子段[j+1,i]中至多有upbound=ceil(sqrt(i))種不同顏色.因?yàn)榇鷥r(jià)函數(shù)是k^2,而長(zhǎng)度為k的子段代價(jià)上界是k,所以枚舉的顏色數(shù)<=sqrt(k).
另顯然,顏色數(shù)都為m的所有可能區(qū)間[j+1,i],選擇最長(zhǎng)的肯定最優(yōu).
因此維護(hù)pos[m],表示從當(dāng)前掃描位置開始向左,顏色種類為m的最長(zhǎng)區(qū)間的左端點(diǎn).
為了更新pos[m],再設(shè)數(shù)組last[n],記錄上一次出現(xiàn)顏色n的位置.
若color[i]==color[i-1],則不更新pos; 否則,所有pos[k]>=last[color[i]]的區(qū)間內(nèi)顏色種類都變成k+1,因此將這段pos[1..m]右移,將pos[1]置為i.
pku 3726 Windy's ABC
題意:
給一個(gè)由ABC三種字母構(gòu)成的長(zhǎng)度不超過500的字串.
定義這個(gè)串的合法副本為:
原串任意位置字母的下標(biāo),與它在新串中的下標(biāo)絕對(duì)值之差不超過 Ri.
求合法副本的種類數(shù).
注:
1. 原串本身也是個(gè)合法副本
2. 求的是不同串的種類數(shù), "A1B2B3A4" 和 "A1B3B2A4" 算同一種.
解:
先通過O(n)的遞推, 求出每種字母在前k位中至少需要/至多能出現(xiàn)多少次, 然后500^3的DP.
對(duì)一個(gè)合法的狀態(tài)(i,j,k)(分別表示3種字母的個(gè)數(shù)), 擴(kuò)展它的3種后續(xù)狀態(tài).
這里不用檢查擴(kuò)展出的新狀態(tài)的合法性, 因?yàn)榈较乱徊紻P時(shí), 只有合法的狀態(tài)才會(huì)被繼續(xù)擴(kuò)展. 這是這題解法處理的巧妙之處.
代碼:
?1?#include?<cstdio>
?2?#include?<cstdlib>
?3?#include?<cstring>
?4?#include?<algorithm>
?5?using?namespace?std;
?6?const?int?MOD?=?20090305;
?7?char?ch[3]?=?{'A','B','C'};
?8?int?n[3][510][2];
?9?int?dp[2][510][510];
10?int?R[3],L;
11?char?S[510];
12?int?T;
13?
14?void?prepare(){
15?????int?i,j,k;
16?????int?c[510];
17?????memset(n,0,sizeof(n));
18?????for(i=0;?i<3;?i++){
19?????????int?cnt?=?0;
20?????????for(j=0;?j<L;?j++){
21?????????????if(S[j]-'A'?==?i)?cnt++;
22?????????????//printf("%d,%d,%d?",i,j,cnt);
23?????????????if(j>=R[i])?n[i][j-R[i]][1]?=?cnt;
24?????????????if(j<L-R[i])?n[i][j+R[i]][0]?=?cnt;
25?????????}
26?????????for(j=0;?j<R[i];?j++){
27?????????????n[i][L-1-j][1]?=?cnt;
28?????????????n[i][j][0]?=?0;
29?????????}
30?????}
31?}
32?
33?int?dodp(){
34?????int?l,i,j,k;
35?????int?ans?=?0;
36?????memset(dp,0,sizeof(dp));
37?????for(i=0;?i<L;?i++)
38?????????for(j=0;?j<L;?j++)
39?????????????dp[0][i][j]?=?1;
40?????for(l=0;?l<L;?l++){
41?????????int?p1=l%2,?p2=(l+1)%2;
42?????????memset(dp[p2],0,sizeof(dp[p2]));
43?????????for(i=n[0][l][0];?i<=n[0][l][1];?i++){
44?????????????for(j=n[1][l][0];?j<=n[1][l][1];?j++){
45?????????????????k?=?l+1-i-j;
46?????????????????//printf("s%d,%d,%d?",l,i,j);
47?????????????????if(k<n[2][l][0]?||?k>n[2][l][1])?continue;
48?????????????????if(!dp[p1][i][j])?continue;
49?????????????????//printf("y%d,%d,%d(%d)?",l,i,j,dp[p1][i][j]);
50?????????????????if(l==L-1){?ans?+=?dp[p1][i][j];?continue;?}
51?????????????????dp[p2][i+1][j]?=?(dp[p2][i+1][j]+dp[p1][i][j])?%?MOD;
52?????????????????dp[p2][i][j+1]?=?(dp[p2][i][j+1]+dp[p1][i][j])?%?MOD;
53?????????????????dp[p2][i][j]?=?(dp[p2][i][j]+dp[p1][i][j])?%?MOD;
54?????????????}
55?????????}
56?????}
57?????return?ans;
58?}
59?
60?int?main(){
61?????int?i,j,k;
62?????scanf("%d",&T);
63?????while(T--){
64?????????scanf("%d?%d?%d",R,R+1,R+2);
65?????????scanf("%s",S);
66?????????L?=?strlen(S);
67?????????prepare();
68?????????printf("%d\n",dodp());
69?????}
70?????return?0;
71?}
72?
frkstyc的POJ分類 zhj5825 發(fā)表于 2006-9-3 17:12:00
1474 geometry
1000 ad hoc
1003 ad hoc
1004 ad hoc
1005 ad hoc
1008 ad hoc
1023 ad hoc
1045 ad hoc
1046 ad hoc
1047 ad hoc
1079 ad hoc
1102 ad hoc
1126 ad hoc
1140 ad hoc
1207 ad hoc
1218 ad hoc
1220 ad hoc
1289 ad hoc
1306 ad hoc
1316 ad hoc
1326 ad hoc
1423 ad hoc
1450 ad hoc
1477 ad hoc
1488 ad hoc
1491 ad hoc
1493 ad hoc
1517 ad hoc
1519 ad hoc
1528 ad hoc
1552 ad hoc
1565 ad hoc
1583 ad hoc
1628 ad hoc
1635 ad hoc
1657 ad hoc
1658 ad hoc
1663 ad hoc
1665 ad hoc
1759 ad hoc
1775 ad hoc
1781 ad hoc
1809 ad hoc
1859 ad hoc
1868 ad hoc
1936 ad hoc
1942 ad hoc
1969 ad hoc
2000 ad hoc
2006 ad hoc
2013 ad hoc
2015 ad hoc
2017 ad hoc
2027 ad hoc
2083 ad hoc
2105 ad hoc
2109 ad hoc
2126 ad hoc
2136 ad hoc
2140 ad hoc
2141 ad hoc
2144 ad hoc
2159 ad hoc
2190 ad hoc
2196 ad hoc
2231 ad hoc
2249 ad hoc
2262 ad hoc
2272 ad hoc
2301 ad hoc
2305 ad hoc
2309 ad hoc
2316 ad hoc
2321 ad hoc
2328 ad hoc
2330 ad hoc
2350 ad hoc
2351 ad hoc
2379 ad hoc
2380 ad hoc
2390 ad hoc
2403 ad hoc
2419 ad hoc
1131 algebra
1707 algebra
1125 all pairs shortest paths
1375 analytical geometry
1473 analytical geometry
2098 analytical geometry
2242 analytical geometry
1001 arbitrary precision calculation
1354 arbitrary precision calculation
1454 arbitrary precision calculation
1503 arbitrary precision calculation
2389 arbitrary precision calculation
2413 arbitrary precision calculation
2240 Bellman-Ford algorithm
1195 binary indexed tree
1330 binary search
2418 binary search tree
1466 bipartite graph matching
1087 bipartite graph matching or maximum flow
2018 bisection and dynamic programming
1505 bisection and greedy
1434 bisection method
2155 bit operation or binary indexed tree
1111 breadth first search
1562 breadth first search
1724 breadth first search
1753 breadth first search
1915 breadth first search
1924 breadth first search
2225 breadth first search
2243 breadth first search
2251 breadth first search
2312 breadth first search
2386 breadth first search
2415 breadth first search
2426 breadth first search
2435 breadth first search
1209 calendar
2080 calendar
2210 calendar
1031 computational geometry
1127 computational geometry
1648 computational geometry
1654 computational geometry
1675 computational geometry
1912 computational geometry
2099 computational geometry
2150 computational geometry
2318 computational geometry
2398 computational geometry
2423 computational geometry
1032 construction
1147 construction
1148 construction
1702 construction
1844 construction
1898 construction
1906 construction
2085 construction
2319 construction
2356 construction
2402 construction
1426 construction or breadth first search
1606 construction or breadth first search
1113 convex hull
2187 convex hull and enumeration
1010 depth first search
1011 depth first search
1022 depth first search
1054 depth first search
1118 depth first search
1144 depth first search
1190 depth first search
1564 depth first search
1655 depth first search
1904 depth first search
1980 depth first search
2184 depth first search
2186 depth first search
2362 depth first search
2378 depth first search
2438 depth first search
1151 discretization and union of intervals or segment tree
1182 disjoint sets
1291 disjoint sets
1703 disjoint sets
1984 disjoint sets
2021 disjoint sets
2236 disjoint sets
2371 divide and conquer
2388 divide and conquer
1014 dynamic programming
1015 dynamic programming
1018 dynamic programming
1036 dynamic programming
1038 dynamic programming
1050 dynamic programming
1088 dynamic programming
1093 dynamic programming
1156 dynamic programming
1157 dynamic programming
1159 dynamic programming
1160 dynamic programming
1163 dynamic programming
1170 dynamic programming
1191 dynamic programming
1221 dynamic programming
1338 dynamic programming
1458 dynamic programming
1579 dynamic programming
1631 dynamic programming
1651 dynamic programming
1661 dynamic programming
1664 dynamic programming
1678 dynamic programming
1685 dynamic programming
1722 dynamic programming
1732 dynamic programming
1745 dynamic programming
1821 dynamic programming
1909 dynamic programming
1923 dynamic programming
1925 dynamic programming
1953 dynamic programming
2033 dynamic programming
2133 dynamic programming
2151 dynamic programming
2181 dynamic programming
2229 dynamic programming
2247 dynamic programming
2250 dynamic programming
2342 dynamic programming
2353 dynamic programming
2355 dynamic programming
2385 dynamic programming
2393 dynamic programming
2397 dynamic programming
2414 dynamic programming
2430 dynamic programming
2439 dynamic programming
2441 dynamic programming
2442 dynamic programming
2084 dynamic programming and arbitrary precision calculation
1387 dynamic programming and enumeration
1322 dynamic programming or generating function
1012 enumeration
1013 enumeration
1142 enumeration
1171 enumeration
1183 enumeration
1318 enumeration
1411 enumeration
1543 enumeration
1647 enumeration
1650 enumeration
1828 enumeration
1916 enumeration
1930 enumeration
2078 enumeration
2100 enumeration
2191 enumeration
2245 enumeration
2326 enumeration
2346 enumeration
2363 enumeration
2381 enumeration
2436 enumeration
2444 enumeration
1267 enumeration and bisection
1129 enumeration and depth first search
1186 enumeration and hash table
1348 enumration
1472 expression evaluation
2106 expression evaluation
2246 expression evaluation
2269 expression evaluation
2234 game theory
2348 game theory
2425 game theory
1799 geometry
1927 geometry
1939 geometry
1940 geometry
2007 geometry
2208 geometry
2276 geometry
2365 geometry
2405 geometry
1981 geometry and enumeration
1090 Gray code
1832 Gray code
1017 greedy
1042 greedy
1083 greedy
1230 greedy
1328 greedy
1456 greedy
1862 greedy
1922 greedy
2054 greedy
2082 greedy
2209 greedy
2291 greedy
2313 greedy
2325 greedy
2370 greedy
2376 greedy
2431 greedy
2433 greedy
2437 greedy
1405 greedy and arbitrary precision calculation
1659 greedy and construction
1026 group theory
1033 group theory
1286 group theory
1674 group theory
2369 group theory
2409 group theory
2366 hash table or binary search
1521 Huffman tree
1742 knapsack
2392 knapsack
1538 Lagrangian interpolation
2344 linear algebra and greedy
1462 linear systems
1914 linear systems
2440 matrix algebra
1149 maximum flow
1273 maximum flow
1459 maximum flow
2125 maximum flow and minimum cut
2377 maximum spanning tree
1258 minimum spanning tree
1679 minimum spanning tree
1861 minimum spanning tree
2421 minimum spanning tree
1166 modular systems
1222 modular systems
1681 modular systems
2345 modular systems
1905 Newton's iteration
2420 Newton's iteration
2299 number of inversions
1006 number theory
1061 number theory
1067 number theory
1152 number theory
1284 number theory
1320 number theory
1401 number theory
1455 number theory
1597 number theory
1808 number theory
1811 number theory
1845 number theory
1995 number theory
2115 number theory
2407 number theory
2417 number theory
2429 number theory and enumeration
1146 permutation
1256 permutation
1731 permutation
1833 permutation
2079 rotating calipers
2104 search
1177 segment tree
2182 segment tree
2352 segment tree or binary indexed tree
1016 simulation
1028 simulation
1048 simulation
1049 simulation
1051 simulation
1060 simulation
1281 simulation
1298 simulation
1363 simulation
1504 simulation
1573 simulation
1578 simulation
1589 simulation
1592 simulation
1600 simulation
1656 simulation
1660 simulation
1666 simulation
1684 simulation
1926 simulation
1928 simulation
1978 simulation
2014 simulation
2039 simulation
2050 simulation
2051 simulation
2081 simulation
2271 simulation
2317 simulation
2339 simulation
2340 simulation
2359 simulation
2383 simulation
2410 simulation
2424 simulation
2443 simulation
2387 single source shortest paths
2394 single source shortest paths
1002 sorting
1245 sorting
1520 sorting
2092 sorting
2408 sorting
1007 stable sorting
1572 string manipulation
1646 string manipulation
1917 string manipulation
2406 string matching
1128 topological sorting
1785 treap
2201 treap
2255 tree manipulation
1089 union of intervals
1797 variation of Dijkstra's shortest path algorithm
2253 variation of Dijkstra's shortest path algorithm
2395 variation of Dijkstra's shortest path algorithm
2254 vector algebra
2354 vector algebra
2412 vector algebra
1130 vertex connectivity
1308 vertex connectivity
2320 vertex connectivity
1 #include<iostream>
2 using namespace std;
3
4 #define DF(N) void N(){\
5 cout<<"function " #N " called..."<<endl;}
6
7 DF(a)DF(b)DF(c)DF(d)DF(e)DF(f)
8
9 void (*func_table[])()={a,b,c,d,e,f};
10
11 int main(){
12 for(int i=0; i<6; i++){
13 (func_table[i])();
14 }
15 return 0;
16 }
http://acm.pku.edu.cn/JudgeOnline/problem?id=2486題目給定一棵有N個(gè)節(jié)點(diǎn)的無(wú)向樹，每個(gè)節(jié)點(diǎn)有個(gè)權(quán)值，當(dāng)?shù)谝淮蔚竭_(dá)某節(jié)點(diǎn)時(shí)，可以獲得該權(quán)值。從節(jié)點(diǎn)1出發(fā)，至多走K步，每步能走到當(dāng)前節(jié)點(diǎn)的任意鄰接點(diǎn)，要求能獲得的權(quán)值和的最大值。N<=100，K<=200。
對(duì)DFS樹中某節(jié)點(diǎn)，從它開始，可以進(jìn)入任意子樹獲得一定權(quán)值后返回該點(diǎn)，也可以不返回（這意味著終止于子樹里）。
這樣可以設(shè)：
dp[i][j][0]: 以i為根, 以至多j步訪問該子樹并返回原地的最大收獲
dp[i][j][1]: 以i為根, 以至多j步訪問該子樹且不需要返回時(shí)的最大收獲
那么，dp[1][K][1]就是最終結(jié)果。
顯然這兩個(gè)值的更新過程可以用深搜DP。
考慮以r為根的DFS子樹，則dp[r][j][0..1]的更新，實(shí)際上是以步數(shù)j為背包容量，以所有子樹為物品的背包問題。
于是可以再設(shè)：
dps[i][j][0]：前i棵子樹，最大步數(shù)j，需要返回時(shí)的最大收獲
dps[i][j][1]：前i棵子樹，最大步數(shù)j，不需要返回時(shí)的最大收獲
DFS完一棵子樹就做一次背包，狀態(tài)復(fù)雜度O(K*子樹數(shù)），轉(zhuǎn)移復(fù)雜度O(K)
整體復(fù)雜度為O(N*K^2)
代碼如下：
1 #include <cstdio>
2 #include <cstdlib>
3 #include <cstring>
4 #include <cmath>
5 #include <algorithm>
6 using namespace std;
7
8 struct EDGE{
9 int v,e;
10 }edg[330];
11 int se, gg[110];
12 bool vis[110];
13 int w[110],dp[110][220][2];
14 int N,K;
15
16 inline void addedge(int u, int v){
17 edg[se].v = v;
18 edg[se].e = gg[u];
19 gg[u] = se++;
20 }
21
22 bool input(){
23 int i,j,k;
24 if(scanf("%d %d",&N,&K)==EOF)
25 return false;
26 se = 2;
27 memset(gg,0,sizeof(gg));
28 for(i=1; i<=N; i++)
29 scanf("%d",&w[i]);
30 for(i=1; i<=N-1; i++){
31 scanf("%d %d",&j,&k);
32 addedge(j,k);
33 addedge(k,j);
34 }
35 }
36
37 void dfs(int r){
38 int i,j,k,u,v,e;
39 int mx0, mx1;
40 vis[r] = true;
41 for(e=gg[r]; e>0; e=edg[e].e){
42 u = edg[e].v;
43 if(!vis[u]){
44 dfs(u);
45 for(k=K; k>=0; k--){
46 mx0 = mx1 = w[r];
47 for(j=0; j<=k-1; j++){
48 if(k>=2 && j<=k-2){
49 mx0 = max(mx0, dp[r][j][0]+dp[u][k-2-j][0]);
50 mx1 = max(mx1, dp[r][j][1]+dp[u][k-2-j][0]);
51 }
52 if(k>=1 && j<=k-1){
53 mx1 = max(mx1, dp[r][j][0]+dp[u][k-1-j][1]);
54 }
55 }
56 dp[r][k][0] = max(dp[r][k][0], mx0);
57 dp[r][k][1] = max(dp[r][k][1], mx1);
58 }
59 }
60 }
61 }
62
63 void solve(){
64 int i,j,k;
65 for(i=1; i<=N; i++)
66 for(j=0; j<=K; j++)
67 dp[i][j][0] = dp[i][j][1] = w[i];
68 memset(vis,false,sizeof(vis));
69 dfs(1);
70 printf("%d\n", max(dp[1][K][0],dp[1][K][1]) );
71 }
72
73 int main(){
74 while(input()){
75 solve();
76 }
77 return 0;
78 }
grids 3741 Escape
http://poj.grids.cn/problem?id=3741
此題我用組合數(shù)學(xué)過的. 歡迎交流各種方法.
原題意: 從(0,0)開始,初始面向y軸正方向,只能右轉(zhuǎn)或直走,每個(gè)格子至多經(jīng)過1次,到達(dá)(x,y),求有多少種走法
轉(zhuǎn)化為: 從(x,y)開始,初始朝向任意,只能左轉(zhuǎn)或直走,!@#%^$#$^^$@%,到達(dá)(0,0)的走法數(shù)
總的走法數(shù)即為初始朝向分別為上下左右的走法數(shù)之和.
觀察符合要求的路徑,其肯定是螺旋形的,也就是各邊不相交.
所以可以分別設(shè) (x,y)上方橫線數(shù)up, 下方橫線數(shù)down, 左側(cè)豎線數(shù)left, 右側(cè)豎線數(shù)right
按初始朝向分4種情況,可以找出up,down,left,right之間的數(shù)量關(guān)系! 可以自己畫一下,很容易發(fā)現(xiàn).
以初始朝向左為例,求 S左:
left-1 = up = right = down (令其 = k)
這樣對(duì)某個(gè)k ,走法數(shù)即為在4個(gè)方位取出對(duì)應(yīng)數(shù)量線段的方法數(shù).
設(shè)(x,y)到地圖4個(gè)邊界的距離分別為 dl, du, dr, dd
則 Sk = C(left-1, dl-1) * C(up, du) * C(right, dr) * C(down, dd)
其中l(wèi)eft項(xiàng)的上下標(biāo)都減了1,是因?yàn)樽髠?cè)豎線肯定有一條是y軸,所以只選出剩下的left-1條
枚舉所有不會(huì)越界的 k ,即保證 C(k, n) 中 k<=n, 就求得這個(gè)方向方法數(shù)之和
最后把4個(gè)方向的S加起來即可
注意一些特殊情況:
1. (x,y)在 y 軸上時(shí),直接輸出1
2. 初始方向?yàn)橄碌那闆r,枚舉k要從1開始,也就是至少要繞一圈. 因?yàn)?!%!@^$#$@#$ :)
ps.
初始朝向 上: left-1 = up-1 = right = down
初始朝向 右: left-1 = up-1 = right-1 = down
初始朝向 下: left = up = right = down
代碼:
1 #include <cstdio>
2 #include <cstdlib>
3 #include <cstring>
4 #include <algorithm>
5 using namespace std;
6
7 const __int64 MOD = 100000007;
8 __int64 x,y,X,Y,c[2100][2100];
9 __int64 ans,tmp;
10 int dk[4][4] = {//lurd
11 1,0,0,0, //left
12 1,1,0,0, //up
13 1,1,1,0, //right
14 1,1,1,1 //down
15 };
16 int N;
17
18 __int64 func(__int64 n, __int64 k){
19 if(n<k) return 0;
20 if(c[n][k]<0)
21 c[n][k] = (func(n-1, k-1) + func(n-1, k)) % MOD;
22 return c[n][k];
23 }
24
25 inline int mi4(int x1, int x2, int x3, int x4){
26 return min(min(x1,x2),min(x3,x4));
27 }
28
29 int main(){
30 int i,j,k,z;
31 int left,right,up,down;
32 memset(c, 0xff, sizeof(c));
33 c[0][0] = 1;
34 for(i=1; i<=2000; i++){
35 c[i][0] = 1;
36 c[i][1] = i;
37 c[i][i] = 1;
38 }
39 scanf("%d",&N);
40 while(N--){
41 scanf("%I64d %I64d %I64d %I64d",&X, &Y, &x, &y);
42 left = x; right = X-x;
43 up = Y-y; down = y;
44 if(x == 0){
45 printf("1\n");
46 continue;
47 }
48 ans = 0;
49 for(i=0; i<4; i++){
50 z = mi4(left-dk[i][0], up-dk[i][1], right-dk[i][2], down-dk[i][3]);
51 for(k=0; k<=z; k++){
52 tmp = func(left-1, k+dk[i][0]-1) % MOD;
53 tmp = (tmp * func(up, k+dk[i][1])) % MOD;
54 tmp = (tmp * func(right, k+dk[i][2])) % MOD;
55 tmp = (tmp * func(down, k+dk[i][3])) % MOD;
56 ans = (ans + tmp) % MOD;
57 }
58 }
59 printf("%I64d\n",ans);
60 }
61 return 0;
62 }
63