250p DoorsGame(一行并列的格子,每个格子中有某种颜色的障碍物,最多15种颜色.A在最左端,B在最右端...)
15种颜色,可以直接极大极小状态DP.
可以直接贪心,计数只有A需要拿走的颜色数,只有B需要拿走的,和两都要拿走的.
500p DrawingLines(两排点,每排n个.上排的和下排的连线.事先已经有些线连好了.求考虑所有的连线方案时,连线交点个数的期望)
三类计数:事先已经连好的线间的交点数.新增连线和原有连线的交点数期望.新增连线之间交点期望.
1000p BuildingRoads若干个点(<=2500)和若干条边的无向图.每个点有点权.现在有4对特殊的点.要求选一些路径出来,使每对点连通(不同对间不要求连通),总代价是经过的所有点权之和.
虽然只有4对点,但是也不要一口咬定是状态DP(250p血的教训),虽然的确是状态DP...
最后不同点对是可以不属于同一连通分量的,所以只1次DP不容易设计状态.
第1次dp: dp[mask][i], mask表示连通子树中包含的特殊点, i表示这棵子树的代表节点(or根节点).
第2次dp: dp2[mask], mask表示已经包含的特殊点, 不要求是连通的, 但是对应的2个点要在同一分量.
这个过程就像,先把每个子模块做好, 再将他们拼接整合.
ps.1000p与steiner tree有关联.
http://acm.hdu.edu.cn/showproblem.php?pid=3311
给定6个基础点，和1000个辅助点，以及无向边若干。
求一棵代价最小的生成子树，使得6个基础点连通。
http://en.wikipedia.org/wiki/Steiner_tree_problem
方法一：
状态DP。
一棵树，实际上可以看成是由两棵子树拼接而成，或者一棵树扩展一条边筛选。而要完整地表示一棵子树，需要记录它的根，和对6个基础点的覆盖状态。
这样求一棵大树，可以枚举接合点，以及两个子树的覆盖状态。
若dp[i][j]，i表示接合点，j表示覆盖状态，那么dp[i][j]=min{dp[i][k]+dp[i][j^k]}。
直接扩展一条边, 可以在保持j不变的情况下, 优先队列广搜, 大大降低复杂度.
方法二：
spfa。
dp[i][j]意义同上。一个点(i,j)，对每个邻接点i'，枚举那一头的状态j'，然后用dp[i][j]+dp[i'][j']+way[i][i']去更新dp[i][j|j']和dp[i'][j|j']。
ps. topcoder srm 470 div1 level3是此题升级版.
1 #include <string>
2 #include <vector>
3 #include <list>
4 #include <map>
5 #include <queue>
6 #include <stack>
7 #include <set>
8 #include <iostream>
9 #include <sstream>
10 #include <numeric>
11 #include <algorithm>
12 #include <cmath>
13 #include <cctype>
14 #include <cstdlib>
15 #include <cstdio>
16 #include <cstring>
17 using namespace std;
18
19 #define CLR(x) memset((x),0,sizeof(x))
20 #define SET(x,y) memset((x),(y),sizeof(x))
21 #define REP(i,x) for(int i=0;i<(x);i++)
22 #define FOR(i,x,y) for(int i=(x);i<(y);i++)
23 #define VI vector<int>
24 #define PB(i,x) (i).push_back(x)
25 #define MP(x,y) make_pair((x),(y))
26
27 struct EDGE{
28 int v,e,d;
29 }edg[20000];
30 int ecnt, gg[1006];
31
32 struct HEAP{
33 int v,d;
34 void set(int nv, int nd){v=nv;d=nd;}
35 }hp[1006*(1<<6)*10];
36 int sz;
37 bool vis[1006];
38
39 int dp[1006][1<<6];
40 int N, M, P;
41
42 bool cmp(const HEAP &a, const HEAP &b)
43 { return a.d>b.d; }
44
45 void addedge(int u, int v, int d)
46 {
47 edg[ecnt].v=v; edg[ecnt].d=d; edg[ecnt].e=gg[u]; gg[u]=ecnt++;
48 edg[ecnt].v=u; edg[ecnt].d=d; edg[ecnt].e=gg[v]; gg[v]=ecnt++;
49 }
50
51 int steiner()
52 {
53 int up = 1<<(N+1);
54 SET(dp,-1);
55 REP(i,N+1) dp[i][1<<i]=0;
56 FOR(i,N+1,N+M+1) dp[i][0]=0;
57 REP(i,up){
58 REP(j,N+M+1){
59 for(int k=i; k>0; k=(k-1)&i){
60 if(dp[j][k]!=-1 && dp[j][i^k]!=-1)
61 if(dp[j][i]==-1 || dp[j][i]>dp[j][k]+dp[j][i^k])
62 dp[j][i]=dp[j][k]+dp[j][i^k];
63 }
64 }
65 sz=0;
66 CLR(vis);
67 REP(j,N+M+1) if(dp[j][i]!=-1){
68 hp[sz++].set(j,dp[j][i]);
69 push_heap(hp, hp+sz, cmp);
70 }
71 while(sz){
72 int now=hp[0].v;
73 pop_heap(hp, hp+sz--,cmp);
74 if(vis[now])continue;
75 vis[now]=true;
76 for(int e=gg[now]; ~e; e=edg[e].e){
77 int to=edg[e].v, td=dp[now][i]+edg[e].d;
78 if(dp[to][i]==-1 || dp[to][i]>td){
79 dp[to][i]=td;
80 hp[sz++].set(to,td);
81 push_heap(hp, hp+sz, cmp);
82 }
83 }
84 }
85 }
86 return dp[0][up-1];
87 }
88
89 int main()
90 {
91 while(~scanf("%d %d %d", &N, &M, &P)){
92 int u, v, d;
93 SET(gg,-1); ecnt=0;
94 REP(i,N+M){
95 scanf("%d", &d);
96 addedge(0,i+1, d);
97 }
98 REP(i,P){
99 scanf("%d %d %d", &u, &v, &d);
100 addedge(u,v,d);
101 }
102 int ret=steiner();
103 printf("%d\n", ret);
104 }
105 return 0;
106 }
#line
$NEXTLINENUMBER$ "$FILENAME$"
#include
<
string
>
#include
<
vector
>
#include
<
list
>
#include
<
map
>
#include
<
queue
>
#include
<
stack
>
#include
<
set
>
#include
<
iostream
>
#include
<
sstream
>
#include
<
numeric
>
#include
<
algorithm
>
#include
<
cmath
>
#include
<
cctype
>
#include
<
cstdlib
>
#include
<
cstdio
>
#include
<
cstring
>
using
namespace
std;
#define
CLR(x) memset((x),0,sizeof(x))
#define
SET(x,y) memset((x),(y),sizeof(x))
#define
REP(i,x) for(int i=0;i<(x);i++)
#define
FOR(i,x,y) for(int i=(x);i<(y);i++)
#define
VI vector<int>
#define
PB(i,x) (i).push_back(x)
#define
MP(x,y) make_pair((x),(y))
class
$CLASSNAME$ {
public
:
$RC$ $METHODNAME$($METHODPARMS$)
{
//
have some fun here
}
$TESTCODE$
};
//
BEGIN CUT HERE
int
main()
{
$CLASSNAME$ ___test;
___test.run_test(
-
1
);
system(
"
pause
"
);
}
//
END CUT HERE
Two Professors
CERC 2008
题目大意:给n条线段,要求划分成尽可能少的子集,使得在同一个子集中的线段两两不重叠.
同时限定线段1和线段2不能在同一子集中.
记每条线段为[Li,Ri], 每个子集的最右端为Bi.
记线段1和2中,L较小的那个为X,另一个为Y.
如果没有那个限定,容易想到贪心的方法:将所有线段按L从小到大排序.然后依次处理线段k,如果当前存在某个集合的Bi<=Lk,就将Lk加入此集合中,并更新Bi=Rk.否则新开一个集合放入k.模拟这个过程,最后的集合数就是答案.用堆维护已有集合的信息,时间复杂度是O(nlgn).
有了限制条件后,原方法不适用了,因为在X与Y之间处理的线段,对Y有后效性.这会使得单纯按照刚才的方法随意贪心,可能轮到Y时,只有X所在集合的Bi<=LY,迫使必须开新集合.但实际上,有可能可以通过调整X与Y之间的线段排列结构,使Y避开X.
问题关键就是如何判断能否调整(并不用关心详细的调整步骤).
当一条线段(P)面临多个可插入的集合时,之前的方法是随意选一个,而不合适的决策正在此产生.下面构造一个情景:
假设P可以在两个集合s,t中选择,而X在s中.
现在P选择加入t.
接下来按部就班地处理.
轮到Y选时,它只能选择加入s,或者开新的集合.
这时候,我们能得知,如果当初P选择的是s,紧随其后的其它选择也相应地对调,那么Y此时肯定面临的是只能加入t,或者开新的集合.
这样Y当然直接加入t就行了.
这说明,只要存在一个这样的P,当Y遭遇X时,肯定存在形状对称的另一个局面使Y避开X,而P就是关键先生.
所以只需稍微改造之前的算法,在处理X与Y之间的线段时,判断并记录下是否出现过可选局面.这样就能正确处理Y遭遇X的情形了.
其它情形时策略不变(可以证明这样的解是最优的).
代码略...
1. 如果其中一个操作数为long double类型,则另一个操作数被转换为long double.
2. 否则,如果其中一个操作数为double, 则另一个操作数被转换为double.
3. 否则,如果其中一个操作数为float, 则另一个操作数也转换为float.
4. 否则,两个操作数进行 "整型升级":
a. 如果其中一个操作数为unsigned long int, 则另一个操作数也被视为unsigned long int.
b. 否则,如果其中一个操作数为long int,而另一个操作数类型是unsigned int, 并且long int能够表示unsigned int的所有值,则另一个操作数也被视为long int;如果long int不能表示unsigned int的所有值,则两个数都被视为unsigned long int.
c. 否则, 如果其中一个操作数是long int,则另一个操作数也被视为long int.
d. 否则, 如果其中一个操作数是unsigned int, 则另一个操作数也被视为unsigned int.
e. 否则, 两个操作数都被视为int.
Maximal Cliques on Circular-arc Graph
合肥2008现场赛, 2009网赛 Guarders
In graph theory, a circular-arc graph is the intersection graph of a set of arcs on the circle. --wiki
uestc_floyd的做法是搜+剪枝.
zzh@bupt大牛想出二分图匹配的做法:
固定某个区间Li肯定选中, 则剩下的区间里, 可能被选择的只有与Li有交集的那些.
(*)将那些区间分两类: 与Li的左边界交的, 与Li的右边界交的.
易知与Li两边界都交的是肯定可以选的, 不会产生不合要求的局面.
不合要求的情况只可能是, 某个一类区间和某个二类区间没有交, 却同时选了它们.
所以二分图建图方法为, 若某个一类区间和某个二类区间没有交, 则连一条边.
二分图的顶点数+1-最大匹配数即为Li对应的最优解.
枚举每个Li.
理论时间复杂度相当高, O(n)*O(匹配), 实现上可以加入排序, 最优解剪枝等方案.
ps. (*)非常巧妙的想法! 非常艺术!
摘要: 题目给出一棵树(N<=10000)以及所有边的权(<=10000). 现在要求对任意查询Q(<=10^8), 判断是否存在一条边权之和恰好为Q的路径.标程的方法暂时没看懂= =... 我用树的分治做(更多相关内容见09国家集训队漆子超的论文)考虑一棵以root为根的子树, 那么在这棵子树中, 有多少条 v1->root->v2 的路径长恰好为Q呢?...
阅读全文
后缀数组,KMP扩展,自动机
题目要求4000个长度为200的字串的最长公共子串.
只需选一个串作为基串, 枚举它的所有后缀串S[i..len], 求出其它串与这个子串的LCP. 最后选最大的输出.
关于求串S与串T所有后缀的LCP, 林希德的论文讲了扩展KMP算法. 不过我想出另一种方法:
把S和T直接连接得到新串U. 按正常KMP的方法求U的next数组, 不过当p指向U[len[S]+1]即原T串的首字母时, 直接将此位的next置为0.
最后min(len[S], next[k]) 就是串T[1..(k-len[S])]与串S的lcp长度.
代码如下:
1
#include <iostream>
2using namespace std;
3
4char wd[4000][201];
5int cnt[201][201], vis[201][201];
6char ss[401];
7int next[401];
8int N;
9
10bool readin()
11
{
12
scanf("%d",&N);
13 if(N==0)return false;
14
15 for(int i=0; i<N; i++)
16 scanf("%s",wd[i]);
17 return true;
18
}
19
20int mycmp(char *s1, int l1, char *s2, int l2)
21{
22 if(l1!=l2) return (l2-l1);
23 while(--l1 && *s1==*s2) s1++, s2++;
24 return (*s1-*s2);
25}
26
27void mycpy(char *s1, char *s2, int l)
28{
29 while(l--) *(s1++)=*(s2++);
30 *s1=0;
31}
32
33void solve()
34{
35 memset(cnt,0,sizeof(cnt));
36 memset(vis,0,sizeof(vis));
37
38 int l0=strlen(wd[0]);
39 strcpy(ss,wd[0]);
40 char ans[201]="";
41
42
for(int p=0; p<l0; p++){
43 char *s=&ss[p];
44 for(int i=1; i<N; i++){
45 strcpy(&ss[l0], wd[i]); //连接两个串
46 int l1=l0-p+strlen(wd[i]);
47 next[0]=-1;
48 int p0=-1, p1=0;
49 while(p1<l1){
50 while(p0>=0 && s[p0]!=s[p1])
51 p0=next[p0];
52 next[++p1]=++p0;
53 if(p1==l0-p) //此位置0
54 next[p1]=0, p0=0;
55 if(p1>=l0-p){
56 int len=min(l0-p, next[p1]);
57 if(vis[p][p+len-1]!=i)
58 vis[p][p+len-1]=i, cnt[p][p+len-1]++;
59
}
60 }
61 }
62
63 for(int j=l0-1; j>=p; j--){
64 if(cnt[p][j]==N-1){
65 if(mycmp(&ss[p], j-p+1, ans, strlen(ans))<0)
66 mycpy(ans, &ss[p], j-p+1);
67 }
68 }
69 }
70
71 if(ans[0]==0)
72 puts("IDENTITY LOST");
73 else
74 puts(ans);
75}
76
77int main()
78{
79 while(readin()){
80 solve();
81 }
82}
83
几道线性的题目
Tanks a Lot
题意:
一个圆,周长为整数n(n<=10^7).圆周上有k(k<=n)个加油站,每个加油站有整数的油量w[i],所有加油站总油量恰好为n. 行车单位路程耗油量为1, 车的初始油量为0. 问,以哪些加油站为起点可以走完一周? 分别判断顺时针和逆时针的情况.
解:
栈的应用.
考虑单个点v1,沿路径v1,v2,v3,...走,则从v1能完成一周的充要条件是对任意的k,S[1,k-1]-C[1,k]>=0,其中S[1,k-1]为这段路上总加油量,C[1,k]为总耗油量.
再考虑先后2个点vk1,vk2. 设沿路径vk1,vp1,vp2,...,vk2,...vpm走.如果vk1和vk2都能到达vpm,肯定vk1必需先能够达到vk2. 这说明从vk1到vpm时的剩余油量肯定>=vk2到vpm时的剩余油量. 有了这个单调性,再加上油余量的区间性以及区间可合并性, 就可以维护一个单调的栈.栈中顶点的访问次序递增,剩余油量递减且不小于0.正扫一遍反扫一遍分别判断顺时针和逆时针.
A Walk in the Park
题意:
二维平面上有一些(N<=10^5)无限长的水平线和竖直线(M<=10^5), 以及一些不在线上的点. 人可以沿任意线走.
称某个点是可见的, 当且仅当人能站在某条线上, 以垂直于线的方向正对此点,并且人与点的连线上没有其它点阻碍视线.
求可见的点的个数.
解:
排序+离散化+线性扫描; 二分
先考虑能否从水平线上看到某个点.
将点按y坐标排序.
对同一x上的所有点,考虑不是起始或末尾的相邻的两个点,它们能被看到,当且仅当它们之间有直线.
这样可以把直线也按y排序, 顺序扫一遍.对某个坐标x,记录它上一个点的y值.
离散化和排序都是nlogn的, 但是线性扫描的思路很巧,值得注意.
直接二分更简单,对每对相邻的点,二分查找它们之间是否有线段.
uva4031 Integer Transmission (DP)题意:传送一个长度在64之内的01串,第i时刻发送出第i字节(i=0,1,...,L-1).对任意第i时刻发出的字节,它有可能在i+1,i+2,...,i+d+1(d<=L)中的任一时刻到达接收端.当同一时刻有多个字节同时到达时,这些字节可以任意排列.问接收端可能收到多少种不同串? 并求出二进制最小的和最大的串.按位DP, 关键是确定前i位至多能有多少个0/1,至少必须有多少个0/1. 此题与windy's abc很相似, 但多了处变化.考虑 d=3, 原串为 1101011, 显然第1个1永远不可能跑到第2个0右边. 字符串的错位,本质上是某些1把它右边d之内的0挤到左边了. 因此对1, 它实际能向右移多少位,取决于它右边d之内有多少个0.这样预处理后按位DP即可.构造最小/最大数,只需尽量把1/0往低位扔就行了.代码:
1 #include <iostream>
2 #include <cstdio>
3 #include <cstdlib>
4 #include <cstring>
5 #include <algorithm>
6 #include <cmath>
7 using namespace std;
8
9 typedef unsigned long long ull;
10
11 int mi[2][130], mx[2][130];
12 ull dp[65][65];
13 int b[65];
14 int N,D;
15 ull K;
16 int CAS;
17
18 void init()
19 {
20 int i,j,k;
21 ull t;
22 memset(b,0,sizeof(b));
23 for(t=K, i=N; t; i--){
24 b[i] = t&1;
25 t>>=1;
26 }
27 int c[2][130];
28 memset(c,0,sizeof(c));
29 for(i=1; i<=N; i++)
30 c[b[i]][i]++;
31 for(i=N; i>=1; i--)
32 c[0][i] += c[0][i+1], c[1][i] += c[1][i+1];
33 memset(mi, 0, sizeof(mi));
34 memset(mx, 0, sizeof(mx));
35 for(i=1; i<=N; i++){
36 mx[b[i]][ min(N, i+c[b[i]^1][i+1]-c[b[i]^1][i+D+1]) ] ++;
37 }
38 for(i=N; i>=1; i--){
39 mx[0][i] += mx[0][i+1];
40 mx[1][i] += mx[1][i+1];
41 mi[0][i] = max(0, N+1-i-mx[1][i]);
42 mi[1][i] = max(0, N+1-i-mx[0][i]);
43 }
44 }
45
46 ull dodp()
47 {
48 int i,j,k,p;
49 ull ret = 0;
50 memset(dp,0,sizeof(dp));
51 for(i=0; i<=N; i++)
52 dp[N][i] = 1;
53 for(p=N; p>=1; p--){
54 for(i=mi[0][p]; i<=mx[0][p]; i++){
55 j=N+1-p-i;
56 if(j<mi[1][p] || j>mx[1][p]) continue;
57 if(dp[p][i]==0)continue;
58 if(p==1){ ret += dp[p][i]; continue; }
59 dp[p-1][i] += dp[p][i];
60 dp[p-1][i+1] += dp[p][i];
61 }
62 }
63 return ret;
64 }
65
66 void getans(ull &xx, ull &ii)
67 {
68 int i,j,k;
69 int c0[2][65],c1[2][65];
70 memset(c0,0,sizeof(c0));
71 memset(c1,0,sizeof(c1));
72 for(i=1; i<=N; i++){
73 if(b[i]==0)
74 c0[0][i]++, c1[0][min(N,i+D)]++;
75 else
76 c1[1][i]++, c0[1][min(N,i+D)]++;
77 }
78 //for(i=1; i<=N; i++
79 xx = ii = 0;
80 for(i=1; i<=N; i++){
81 while(c0[0][i]--) ii = (ii<<1);
82 while(c0[1][i]--) ii = (ii<<1)|1;
83
84 while(c1[1][i]--) xx = (xx<<1)|1;
85 while(c1[0][i]--) xx = (xx<<1);
86 }
87 }
88
89 void solve()
90 {
91 int i,j,k;
92 printf("Case %d: ", ++CAS);
93 printf("%llu ", dodp());
94 ull xx,ii;
95 getans(xx, ii);
96 printf("%llu %llu\n", ii, xx);
97 }
98
99 int main()
100 {
101 CAS = 0;
102 while(scanf("%d",&N)!=EOF && N){
103 scanf("%d %llu",&D,&K);
104 init();
105 solve();
106 }
107 }
108