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