字符串少量習題小結.
spoj694(易) 后綴數組
求一個字串的不同子串個數.
按rank考慮子串.加入子串S[i]時,獲得了len-Sa[i]個不同子串.但其中height[i]個已經屬于S[i-1]了,所以實際子串數增加了len-Sa[i]-S[i-1]. 順序掃一遍height數組即得解.
spoj687(中) 后綴數組
求一個串的重復次數最多的連續重復子串.
設周期為L的連續重復子串存在,則點0,L,2L,...,kL必能覆蓋到一個完整周期. 因此對L,考察這些點的字符相等情況,LCP情況,可得到L的解.
枚舉L.
復雜度是O(n/1+n/2+...+n/n) = O(nlogn)
pku3693(中) 后綴數組
同spoj687,只是結果還要輸出字典序最小的滿足條件的串.可以借助rank數組直接比較字典序.只是要注意在考察點kL時,要把以(k-1)L+1,...,(k+1)L-1為起點的子串都訪問一遍找最小rank者.
pku1743(中) 后綴數組
找一個串的最長不重疊相同子串.
由于某子串可能整體加上(或減去)相同偏移量,因此不直接對原串操作,而是構造新串b, 其中b[i]=a[i]-a[i-1]. 此時求得最長不重疊相同子串的長度+1便是結果.
可以二分長度,或者棧掃描(*)直接求最大長度.
whu1084(易) 后綴數組
求重復次數最多的不重疊子串長度
spoj687的簡單版,不要求循環節連續,直接二分長度即可.
pku2778(易) 多串匹配+DP AC自動機,trie圖
字符集大小為4, 給出m個(m<=10)禁止單詞(長度<=10), 求長度為n(n<=2*10^9)的不包含任何禁止單詞的串的個數.
對禁止單詞建立trie圖,并計算出圖中任意合法結點之間的轉移數,這樣便求得1步轉移矩陣.
做n次方后的矩陣,第1行中屬于合法狀態的元素之和即為解.
禁止單詞總長度不超過100,因此合法狀態亦<100.總復雜度100^3*logN
zju3228(中) Searching the String 后綴數組,AC自動機,trie圖
原串長10^5, 現在有10^5次查詢, 每次查詢一個長度<=6的模式串在原串中的最大匹配次數.
模式串的匹配方式有可重疊和不可重疊兩種, 需針對查詢的類型返回相應值.
后綴數組解法(在線):
對原串建立sa和height數組.由于模式串長度最大只有6, 我們可以將height數組分別按L=1..6分組,預處理求出相應長度每組內不重疊子串的最大匹配次數,此過程O(6*nlogn).
另外由于sa數組將所有后綴按字典序排好了,所以對一個詢問, 可以二分找到它在sa中第一次出現的位置p1和最后一次出現的位置p2, 則p2-p1+1就是可重疊匹配的答案. 對不可重疊匹配,只需直接返回p1處預處理時的值. 每次查詢O(logn).
trie圖,AC自動機解法(離線):
把所有查詢建trie圖, 對圖中的每個有效結點維護:該串長度,兩類查詢的計數,該串上一次被匹配的位置, 還要用個鏈表記下這個串屬于哪些查詢.
剩下的就是經典的自動機多串匹配了.
(*)關于棧掃:
height數組具有區間性,各個不同前綴被相應的極小值隔開,而一個區間中又有多個子區間.各區間值大于區間端點的部分互不影響.因此可以維護一個存放height值不減的棧,棧中每個元素的附屬值, 記錄了它在棧中相鄰的兩個元素為端點的連續區間內所有height值不小于它的必要信息.比如此題要記錄height>=k的連續區間內sa[i] 的最大值和最小值.
棧掃描的經典例子移步pku2559.
(**)trie圖備忘:
比trie樹多了個后綴指針psuf. 設當前結點字母為c, 則psuf指向父親的后綴的pch[c].
trie樹中的后代結點指針pch(已經更名為狀態轉移指針),當相應后代存在時,指向后代;否則指向當前結點的后綴的相應后代,即pch[k]=node[pa].pch[k].
后綴指針: 在接下來的狀態轉移中,當前結點與它的后綴結點等價.
后代結點指針: 在當前狀態下,接收到字符ch時,轉移到pch[ch]指向的結點.
二分圖匹配的巧妙應用相當巧妙!CTU 2005 Openhttp://acm.pku.edu.cn/JudgeOnline/problem?id=2990題意:8*8的棋盤, 初始放置2個相同的棋子. Alice和Bob輪流行動. 每次行動可以把其中一個棋子移到它上下左右相鄰格內(某些格子壞掉了,則不能移). 當某人的移動使兩棋子重合時, 他贏. 另, 一局中不能出現重復的局面. 比如(0,0)(4,0) -> (1,0)(4,0)合法, 此時如果再(1,0)(4,0) -> (0,0)(4,0)則非法. 當一個人無子可動時, 他輸.兩人都用最優策略. 問先手的Alice必勝還是必敗?解:把每個合法狀態看成一個頂點, 則狀態轉移就是向其它點連邊. 這樣建的圖是二分圖.而兩人下棋, 就是在圖上以初始狀態的頂點為起點, 沿邊移動. 由于建的圖是由所有合法狀態與合法移動組成的, 因此, 移動到哪個集合(A與B), 就表示輪到誰行動. 當無法再移動時, 點在哪個集合就表示對應的人輸了.狀態不重復出現, 表示移動路徑沒有環.誰贏誰輸, 與路徑長度的奇偶性密切相關.考慮二分圖的最大匹配, 也是個找交替路徑擴張的過程.設起點為v, 分情況討論v的狀態與路徑長度的關系: (1) v是自由點. 這表示v的任意鄰接點vB都是浸潤點. 不管選哪個vB, 都可以沿著它的匹配邊走到vA'. 只要Bob每次都沿匹配邊走, 由于不可能達到另一個自由點, 因此終點必屬于A, Bob必勝.(2) v是浸潤點, 此時v所在的交替路徑兩個端點分布情況可能有幾種: a)對所有交替路徑, 端點都在B集. 這時只要Alice每次都沿著匹配邊走, 必勝. b)存在一條交替路徑, 端點都在A集. 把沿v的匹配邊走的那一半全部置反, 就變成(1)的狀態了, 因此2者等價. c)沿v的匹配邊走的那一半全終止于B, 另一半終止于A. 只要Alice一開始就沿匹配邊走, 后面策略同a. 其它情形不可能在最大匹配中出現, 故不討論. 這正是充分利用了最大匹配的性質.因此對本題先求最大匹配, 然后判斷是否為(1)或(2b), 即可知勝負.代碼如下:
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 //判斷合法狀態
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 //位壓縮存狀態
33 int encode(int x1, int y1, int x2, int y2)
34 {
35 if(y1 > y2 || (y1==y2 && x1 > x2)) //小點放前面, 避免重復狀態
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 //添加狀態轉移的邊
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 //這個匹配函數不分XY集, 因此匹配點雙方的mat標記都要修改
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)并轉化為(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)種字母,組成一個長度為L(L<=10^18)的串.
這個串需滿足要求:
對任意的 1<=i<=L , 以及任意的 1<=k1,k2<=K 且 k1!=k2, 在前綴 s[1..i]中,字母k1的個數和字母k2的個數之差的絕對值<=2.
例如: abac是合法的; 而abbbc不合法, 因為前綴abbb中字母b和c的個數相差為3.
建立狀態:
從<=2 入手找狀態. 可以設前c個字母中, 最小個數為m, 字母數為m的種類為i, m+1的種類為j, m+2的種類為k. 化簡狀態可得 比最小個數多1的種類為i,比最小個數多2的種類為j. 而經過數學推導(不懂), 可知 j+2k<K, 也就是當 c%K 已知時, 可直接由k確定i和j. 這樣狀態數為 50*50=2500, 還是不能用矩陣法. 進一步思考, 由c%K=0時的結果可以推出c%K=1時的結果,遞推可把c%K=0...K-1的結果都求出. 而要求L步的結果數,實際上并不用去管是1步1步走,還是2步2步走. 所以我們可以直接一次走K步! 這樣就把c%K這一維狀態也消除了.
于是可以設矩陣m[i,j]為c%K=0時,k經過K步從i轉移到j的方法數.
這樣先求出 L-L%K 步的方法數, 最后 L%K 步直接dp即可.
整體復雜度為 K^3*log(L/K).
本題關鍵: 由k和c%K唯一確定i和j; 一次走K步, 消除狀態c%K, 實際上不同c%K對應的狀態是冗余的, 因為不用去管中間的過程.
E. Ski Lessons (DP)
題意:
滑雪場有N(N<=10000)種項目, 可以從任意時刻開始, 可以反復參加. 每種項目要求參與者技能值(<=100)至少為c[i], 耗費連續的d[i]單位時間.
此外,滑雪場提供S(S<=100)個培訓課程. 每個課程開始時間為m[i], 持續時間l[i], 結束后, 參加者的技能值變為a[i]. 如果選擇參加某個課程,不能遲到早退. 只能同時參加一個課程.
一個人在任意時刻只能做一件事, 而且他總共有 T(T<=10000) 單位時間. 他必須在時刻T結束所有活動.
問如何安排可以使得此人參加最多次滑雪項目, 求最大次數.
解:
O(100*N)預處理, len[i][j]表示技能值為i時, 參加一次任意項目的最短時間.
O(S*S)DP, dp[i]表示在課程i開始的前一時刻, 已參加項目的最大次數.
注意到, 結束一項課程后人的技能值是一定的. 因此, 可以枚舉參加i之前最近參加的課程k, 兩次課程之間的收益可直接計算. 則dp[i] = max(dp[k]+ (m[i]-m[k]-l[k])/len[a[k]]).
D.
題意:
給一個初值C,和兩個迭代公式 fi(x)=a[i]*x/d[i]+b[i], 公式中1<=d<a<=20, 1<=b<=20,且都為整數. 除法為整型除法.
由初值C開始迭代, 計算出來的結果又可以任意代入公式繼續迭代.
求能得到的所有數(包括C)中第N大的. 1<=N<=400000.
解:
一個隊列,兩個指針,不斷分別將指向的兩個值代入兩個公式計算,取小的加入列尾.注意判重.
G.
題意:
無向圖,頂點集為U, 給一個不包含源點v的子頂點集S, 問至少要在U-S-{v}中刪掉多少個點,才能完全割斷S與v的聯系. S中沒有點與v直接相鄰.
解:
限制頂點流量,最大流(最小割),將點i0拆成i->i',所有入邊指向i,出邊從i'指出.對有可能損壞的點,邊容量置1,不可能損壞的點置inf.其它邊容量為inf.
I.
題意:
給一個顏色序列s, 序列長度<=40000, 其中包含的顏色種類<=40000. 可以將原序列任意分割, 分割后每一個子段的代價分別為f(k)=k*k,其中k為子段中包含的顏色種類數.
求一個分割方案,使sigma(f(k))最小.
解:
DP.關鍵的優化在于,轉移dp[i]時,只用枚舉計算min{dp[j]+cost(j+1,i)},其中子段[j+1,i]中至多有upbound=ceil(sqrt(i))種不同顏色.因為代價函數是k^2,而長度為k的子段代價上界是k,所以枚舉的顏色數<=sqrt(k).
另顯然,顏色數都為m的所有可能區間[j+1,i],選擇最長的肯定最優.
因此維護pos[m],表示從當前掃描位置開始向左,顏色種類為m的最長區間的左端點.
為了更新pos[m],再設數組last[n],記錄上一次出現顏色n的位置.
若color[i]==color[i-1],則不更新pos; 否則,所有pos[k]>=last[color[i]]的區間內顏色種類都變成k+1,因此將這段pos[1..m]右移,將pos[1]置為i.
pku 3726 Windy's ABC
題意:
給一個由ABC三種字母構成的長度不超過500的字串.
定義這個串的合法副本為:
原串任意位置字母的下標,與它在新串中的下標絕對值之差不超過 Ri.
求合法副本的種類數.
注:
1. 原串本身也是個合法副本
2. 求的是不同串的種類數, "A1B2B3A4" 和 "A1B3B2A4" 算同一種.
解:
先通過O(n)的遞推, 求出每種字母在前k位中至少需要/至多能出現多少次, 然后500^3的DP.
對一個合法的狀態(i,j,k)(分別表示3種字母的個數), 擴展它的3種后續狀態.
這里不用檢查擴展出的新狀態的合法性, 因為到下一步DP時, 只有合法的狀態才會被繼續擴展. 這是這題解法處理的巧妙之處.
代碼:
?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 發表于 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個節點的無向樹，每個節點有個權值，當第一次到達某節點時，可以獲得該權值。從節點1出發，至多走K步，每步能走到當前節點的任意鄰接點，要求能獲得的權值和的最大值。N<=100，K<=200。
對DFS樹中某節點，從它開始，可以進入任意子樹獲得一定權值后返回該點，也可以不返回（這意味著終止于子樹里）。
這樣可以設：
dp[i][j][0]: 以i為根, 以至多j步訪問該子樹并返回原地的最大收獲
dp[i][j][1]: 以i為根, 以至多j步訪問該子樹且不需要返回時的最大收獲
那么，dp[1][K][1]就是最終結果。
顯然這兩個值的更新過程可以用深搜DP。
考慮以r為根的DFS子樹，則dp[r][j][0..1]的更新，實際上是以步數j為背包容量，以所有子樹為物品的背包問題。
于是可以再設：
dps[i][j][0]：前i棵子樹，最大步數j，需要返回時的最大收獲
dps[i][j][1]：前i棵子樹，最大步數j，不需要返回時的最大收獲
DFS完一棵子樹就做一次背包，狀態復雜度O(K*子樹數），轉移復雜度O(K)
整體復雜度為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
此題我用組合數學過的. 歡迎交流各種方法.
原題意: 從(0,0)開始,初始面向y軸正方向,只能右轉或直走,每個格子至多經過1次,到達(x,y),求有多少種走法
轉化為: 從(x,y)開始,初始朝向任意,只能左轉或直走,!@#%^$#$^^$@%,到達(0,0)的走法數
總的走法數即為初始朝向分別為上下左右的走法數之和.
觀察符合要求的路徑,其肯定是螺旋形的,也就是各邊不相交.
所以可以分別設 (x,y)上方橫線數up, 下方橫線數down, 左側豎線數left, 右側豎線數right
按初始朝向分4種情況,可以找出up,down,left,right之間的數量關系! 可以自己畫一下,很容易發現.
以初始朝向左為例,求 S左:
left-1 = up = right = down (令其 = k)
這樣對某個k ,走法數即為在4個方位取出對應數量線段的方法數.
設(x,y)到地圖4個邊界的距離分別為 dl, du, dr, dd
則 Sk = C(left-1, dl-1) * C(up, du) * C(right, dr) * C(down, dd)
其中left項的上下標都減了1,是因為左側豎線肯定有一條是y軸,所以只選出剩下的left-1條
枚舉所有不會越界的 k ,即保證 C(k, n) 中 k<=n, 就求得這個方向方法數之和
最后把4個方向的S加起來即可
注意一些特殊情況:
1. (x,y)在 y 軸上時,直接輸出1
2. 初始方向為下的情況,枚舉k要從1開始,也就是至少要繞一圈. 因為 !%!@^$#$@#$ :)
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