字符串少量习题小结.
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