CDQZ Day5

C++ 有向圖 · 發表 2019-01-26 20:15:00

摘要： 1 DP #1 題目名稱題目名稱匹配塊路徑染色輸入檔名輸入檔名 match.in.in.in block.in path.in paint.in 輸出檔名輸出檔名 ma...

DP #1

題目名稱題目名稱

匹配

塊

路徑

染色

輸入檔名輸入檔名

match.in.in.in

block.in

path.in

paint.in

輸出檔名輸出檔名

match.out.out.out.out

block.out

path.out

paint.out

每個測試點時每個測試點時每個測試點時每個測試點時每個測試點時每個測試點時限

1.5 s

測試點數目測試點數目

每個測試點分每個測試點分每個測試點分每個測試點分每個測試點分每個測試點分值

記憶體限制記憶體限制

256 M

256M

256 M

是否有部分是否有部分是否有部分

否

題目型別題目型別

傳統

注意：程式碼長度限制均為注意：程式碼長度限制均為注意：程式碼長度限制均為注意：程式碼長度限制均為注意：程式碼長度限制均為注意：程式碼長度限制均為 64K ，不開，不開 O2 。

1 匹配(match.c/cpp/pas)

1.1 題目描述

現在有一排花和一排花盆，每株花有互不相同的標號，花盆也有互不相同的標號，標號

均為1~n，也就是有 n 株花和 n 個花盆。

花與花盆共排成了上下兩排，現在希望為儘可能多的花匹配一個對應的花盆，匹配時將

為其連上一條直線。要求匹配所產生的直線互不相交，並且為了和諧，匹配的花與花盆標號

應當相同。

問最多能匹配的對數。

1.2 輸入格式

第一行為一個整數n ，分別表示 A、B 的序列長度。

接下來一行 n 個數，表示序列 A。

接下來一行 n 個數，表示序列 B。

1.3 輸出格式

輸出一行一個整數，表示最多能匹配的對數。

1.4 樣例輸入

1 2 3

1 3 2

1.5 樣例輸出

1.6 資料範圍與約定

對於20％的資料，n <= 300。

對於40％的資料，n <= 1000。

對於100％的資料，n <= 100000。

2 2 塊 (block.c/cpp/pas) .c/cpp/pas) .c/cpp/pas)

2.1 .1 .1 題目描述題目描述

有一棵 n個結點個結點的樹，結點從，結點從，結點從 1到 n標號。現在希望刪去最少的邊，使得出現一個大小為 K 的聯通塊。

2.2 .2 .2 輸入格式輸入格式

第一行兩個整數 n, K，代表樹的結點個數結點個數，以及希望出現大小為 K的聯通塊。

接下來接下來 n-1行，每行兩個數 u，v，表示 u、v之間有一條連邊。

2.3 .3 .3 輸出格式輸出格式

輸出一行一個數，表示最少刪去的邊數。

2.4 .4 .4 樣例輸入樣例輸入

11 611 611 6

1 21 2

1 31 3

1 41 4

1 51 5

2 62 6

2 72 7

2 82 8

4 94 9

4 104 10 4 10

4 114 11 4 11

2.5 .5 .5 樣例輸出樣例輸出

2.6 .6 .6 資料範圍與約定資料範圍與約定資料範圍與約定資料範圍與約定

對於 20％的資料，保證％的資料，保證％的資料，保證％的資料，保證 1 <= n <= 18。

對於 50％的資料，保證％的資料，保證％的資料，保證％的資料，保證 1 <= n <= 200。

對於 100％的資料，保證％的資料，保證％的資料，保證％的資料，保證 1 <= n <= 1000，1<=K<=n。

3 路徑 (path.c/cpp/pas) .c/cpp/pas) .c/cpp/pas)

3.1 .1 .1 題目描述題目描述

給出一個有 n 個點 m 條邊的有向圖，每個條邊的有向圖，每個條邊的有向圖，每個條邊的有向圖，每個條邊的有向圖，每個條邊的有向圖，每個結點上有一個小寫字母，定義一條路徑的權，定義一條路徑的權，定義一條路徑的權，定義一條路徑的權，定義一條路徑的權值是這條路徑值是這條路徑值是這條路徑上出現次數最多的字母個，求這圖出現次數最多的字母個，求這圖出現次數最多的字母個，求這圖出現次數最多的字母個，求這圖出現次數最多的字母個，求這圖出現次數最多的字母個，求這圖出現次數最多的字母個，求這圖出現次數最多的字母個，求這圖最大權值的路徑。最大權值的路徑。最大權值的路徑。最大權值的路徑。最大權值的路徑。

3.2 .2 .2 輸入格式輸入格式

第一行兩個整數 n, m，表示結點數和邊數。

第二行一個不帶空格的字串字串，第 i 個字元表示第 i 個結點對應的小寫字母。

3.3 .3 .3 輸出格式輸出格式

輸出一行一個整數，表示最大權值的路徑的權值，若為無窮大無窮大則輸出 -1 。

3.4 .4 .4 樣例輸入樣例輸入

5 45 4

abaca abaca

1 21 2

1 31 3

3 43 4

4 54 5

3.5 .5 .5 樣例輸出樣例輸出

3 .6 .6 .6 資料範圍與約定

對於 20％的資料，保證％的資料，保證％的資料，保證％的資料，保證 1 <= n, m <= 10。

對於 50％的資料，保證 1<=n, m<=5000。

對於 100％的資料，保證％的資料，保證％的資料，保證％的資料，保證 1<=n, m<=300000 。

4 染色 (paint.c/cpp/pas) .c/cpp/pas) .c/cpp/pas)

4.1 .1 .1 題目描述題目描述

一個木板上有一個木板上有一個木板上有 n 個格子，一開始均無色（顏為個格子，一開始均無色（顏為個格子，一開始均無色（顏為個格子，一開始均無色（顏為個格子，一開始均無色（顏為個格子，一開始均無色（顏為個格子，一開始均無色（顏為個格子，一開始均無色（顏為個格子，一開始均無色（顏為 0）。現在要進行）。現在要進行）。現在要進行）。現在要進行）。現在要進行 K 次染色，每次染色，每次染色，每次告訴你染區間染區間 [li,ri]，顏色為，顏色為 ci。顏色會被覆蓋。顏色會被覆蓋。顏色會被覆蓋。顏色會被覆蓋問最後的木板上所有格子顏色。問最後的木板上所有格子顏色。問最後的木板上所有格子顏色。問最後的木板上所有格子顏色。問最後的木板上所有格子顏色。問最後的木板上所有格子顏色。問最後的木板上所有格子顏色。

4.2 .2 .2 輸入格式輸入格式

第一行兩個整數第一行兩個整數第一行兩個整數 n; Kn; Kn; K ，表示格子數和染色次。，表示格子數和染色次。，表示格子數和染色次。，表示格子數和染色次。，表示格子數和染色次。，表示格子數和染色次。，表示格子數和染色次。

接下來 K 行，每三個整數行，每三個整數行，每三個整數行，每三個整數行，每三個整數 li，ri，ci，表示染色區間和顏，表示染色區間和顏，表示染色區間和顏，表示染色區間和顏，表示染色

區間和顏4.3 .3 .3 輸出格式輸出格式

輸出一行 n 個整數，輸出這木板上的所有格子顏色。個整數，輸出這木板上的所有格子顏色。個整數，輸出這木板上的所有格子顏色。個整數，輸出這木板上的所有格子顏色。個整數，輸出這木板上的所有格子顏色。個整數，輸出這木板上的所有格子顏色。個整數，輸出這木板上的所有格子顏色。個整數，輸出這木板上的所有格子顏色。個整數，輸出這木板上的所有格子顏色。

4.4 .4 .4 樣例輸入樣例輸入

4 2

1 2 4

2 4 1

4.5 .5 .5 樣例輸出樣例輸出

4 1 1 1

4.6 .6 .6 資料範圍與約定資料範圍與約定資料範圍與約定資料範圍與約定

對於 10％的資料，保證％的資料，保證％的資料，保證％的資料，保證 n <= 100。

對於 40％的資料，保證 n, K<=100000。

對於 100％的資料，保證％的資料，保證％的資料，保證％的資料，保證 1<=n, K<=1000000 ，1<=ci<=1000000。


 1 #include<cstdio>
 2 #include<cstring>
 3 #include<iostream>
 4 #include<algorithm>
 5 #include<cmath>
 6 #include<vector>
 7 #define R(a,b,c) for(register int (a)=(b);(a)<=(c);++(a))
 8 #define nR(a,b,c) for(register int (a)=(b);(a)>=(c);--(a))
 9 #define Ii inline int
10 #define Iv inline void
11 #define Il inline long long
12 #define Ib inline bool
13 #define INF 0x7ffffff
14 #define re register
15 #define ll long long
16 #define Max(a,b) ((a)>(b)?(a):(b))
17 #define Min(a,b) ((a)<(b)?(a):(b))
18 #define Cmin(a,b) ((a)=(a)<(b)?(a):(b))
19 #define Cmax(a,b) ((a)=(a)>(b)?(a):(b))
20 #define Fill(a,b) memset((a),(b),sizeof((a)))
21 #define D_e_Line printf("\n-------------\n");
22 #define D_e(x) printf("\n______%d_______\n",x)
23 #define Pause system("pause")
24 using namespace std;
25 const int N=100005;
26 Ii read(){
27int s=0,f=1;char c;
28for(c=getchar();c>'9'||c<'0';c=getchar())if(c=='-')f=-1;
29while(c>='0'&&c<='9')s=s*10+(c^'0'),c=getchar();
30return s*f;
31 }
32 Iv print(int x){
33if(x<0)putchar('-'),x=-x;
34if(x>9)print(x/10);
35putchar(x%10^'0');
36 }
37 int a[N],f[N];
38 #define ON_JUDGE
39 int main(){
40 #ifdef ON_JUDGE
41freopen("match.in","r",stdin),freopen("match.out","w",stdout);
42 #endif
43int n=read();
44R(i,1,n)
45a[read()]=i;
46int len=0;
47R(i,1,n){
48int x=a[read()];
49if(x>=f[len])
50f[++len]=x;
51else{
52int l=0,r=len;
53while(l<=r){
54int mid=l+r>>1;
55f[mid]>=x?
56r=mid-1: 
57l=mid+1;
58}
59f[l]=x;
60}
61}
62print(len);
63return 0;
64 }
65 /*
66 4
67 1 0 9 7
68 1 9 7 0
69 
70 5
71 1 1 1 0 2
72 1 1 0 1 2
73 
74 6
75 2 3 9 7 5 7
76 3 4 7 8 5 7
77 
78 7
79 4 5 2 3 6 7 1
80 1 3 4 2 5 6 1
81 
82 7
83 1 3 2 4 5 6 7
84 3 1 4 2 6 5 7
85 */

match_My_CreatOnContest.cpp


1 #include<cstdio>
2 #include<cstring>
3 #include<iostream>
4 #include<algorithm>
5 #include<cmath>
6 #include<vector>
7 #include<bitset>
8 #define R(a,b,c) for(register int (a)=(b);(a)<=(c);++(a))
9 #define nR(a,b,c) for(register int (a)=(b);(a)>=(c);--(a))
 10 #define Ii inline int
 11 #define Iv inline void
 12 #define Il inline long long
 13 #define Ib inline bool
 14 #define INF 0x7ffffff
 15 #define re register
 16 #define ll long long
 17 #define Max(a,b) ((a)>(b)?(a):(b))
 18 #define Min(a,b) ((a)<(b)?(a):(b))
 19 #define Cmin(a,b) ((a)=(a)<(b)?(a):(b))
 20 #define Cmax(a,b) ((a)=(a)>(b)?(a):(b))
 21 #define Fill(a,b) memset((a),(b),sizeof((a)))
 22 #define D_e_Line printf("\n-------------\n");
 23 #define D_e(x) printf("\n______%d_______\n",x)
 24 #define Pause system("pause")
 25 using namespace std;
 26 const int N=2005;
 27 Ii read(){
 28int s=0,f=1;char c;
 29for(c=getchar();c>'9'||c<'0';c=getchar())if(c=='-')f=-1;
 30while(c>='0'&&c<='9')s=s*10+(c^'0'),c=getchar();
 31return s*f;
 32 }
 33 Iv print(int x){
 34if(x<0)putchar('-'),x=-x;
 35if(x>9)print(x/10);
 36putchar(x%10^'0');
 37 }
 38 int w[N],f[N][26];
 39 vector<int>V[N];
 40 //bitset<N>vis;
 41 int ans=1;
 42 Iv dfs(int u){
 43//vis[u]=1;
 44for(vector<int>::iterator v=V[u].begin();v!=V[u].end();++v){
 45R(col,0,25)
 46f[*v][col]+=f[u][col];
 47dfs(*v);
 48}
 49Cmax(ans,f[u][w[u]]);
 50 }
 51 char s[N];
 52 #define ON_JUDGE
 53 int main(){
 54 #ifdef ON_JUDGE
 55freopen("path.in","r",stdin),freopen("path.out","w",stdout);
 56 #endif
 57int n=read(),m=read();
 58if(n<=500){
 59scanf("%s",s+1);
 60R(i,1,n)
 61w[i]=(s[i]^'a');
 62R(i,1,m){
 63int u=read(),v=read();
 64V[u].push_back(v);
 65}
 66R(i,1,n)
 67{
 68R(j,1,n){
 69R(col,0,25)
 70f[j][col]=0;
 71f[j][w[j]]=1;
 72}
 73dfs(i);
 74}
 75print(ans);
 76}
 77else
 78printf("-1");
 79return 0;
 80 }
 81 /*
 82 5 4
 83 abaca
 84 1 2
 85 1 3
 86 3 4
 87 4 5
 88 
 89 5 4
 90 abacc
 91 1 2
 92 1 3
 93 3 4
 94 4 5
 95 
 96 6 5
 97 abcdcc
 98 1 2
 99 1 3
100 3 4
101 4 5
102 5 6
103 
104 7 6
105 abacaaa
106 1 2
107 1 3
108 3 4
109 4 5
110 5 6
111 6 7
112 
113 8 8
114 acacacaa
115 2 1
116 1 4
117 3 1
118 5 3
119 6 5
120 6 4
121 3 7
122 7 8
123 */ 

path_My_CreatOnContest.cpp


 1 #include<cstdio>
 2 #include<cstring>
 3 #include<iostream>
 4 #include<algorithm>
 5 #include<cmath>
 6 #include<vector>
 7 #define R(a,b,c) for(register int (a)=(b);(a)<=(c);++(a))
 8 #define nR(a,b,c) for(register int (a)=(b);(a)>=(c);--(a))
 9 #define Ii inline int
10 #define Iv inline void
11 #define Il inline long long
12 #define Ib inline bool
13 #define INF 0x7ffffff
14 #define re register
15 #define ll long long
16 #define Max(a,b) ((a)>(b)?(a):(b))
17 #define Min(a,b) ((a)<(b)?(a):(b))
18 #define Cmin(a,b) ((a)=(a)<(b)?(a):(b))
19 #define Cmax(a,b) ((a)=(a)>(b)?(a):(b))
20 #define Fill(a,b) memset((a),(b),sizeof((a)))
21 #define D_e_Line printf("\n-------------\n");
22 #define D_e(x) printf("\n______%d_______\n",x)
23 #define Pause system("pause")
24 using namespace std;
25 const int N=1000005;
26 Ii read(){
27int s=0,f=1;char c;
28for(c=getchar();c>'9'||c<'0';c=getchar())if(c=='-')f=-1;
29while(c>='0'&&c<='9')s=s*10+(c^'0'),c=getchar();
30return s*f;
31 }
32 Iv print(ll x){
33if(x<0)putchar('-'),x=-x;
34if(x>9)print(x/10);
35putchar(x%10^'0');
36 }
37 //#define ON_JUDGE
38 struct Question{
39int l,r,w;
40void Init(){l=read(),r=read(),w=read();}
41 };
42 int fa[N],ans[N];
43 vector<Question>V;
44 Ii Find(int x){
45return x==fa[x]?x:fa[x]=Find(fa[x]);
46 }
47 Iv Union(int x,int y){
48x=Find(x),y=Find(y);
49if(x!=y)
50fa[x]=y;
51 }
52 int n;
53 Iv Paint(int x,int w){
54ans[x]=w;
55if(x!=1&&ans[x-1])Union(x-1,x);
56if(x!=n&&ans[x+1])Union(x,x+1);
57 }
58 #define ON_JUDGE
59 int main(){
60 #ifdef ON_JUDGE
61freopen("paint.in","r",stdin),freopen("paint.out","w",stdout);
62 #endif
63n=read();
64int m=read();
65R(i,1,m){
66Question ques;
67ques.Init(),
68V.push_back(ques);
69//V.push_back((Question){read(),read(),read()});
70}
71R(i,1,n)fa[i]=i;
72//for(vector<int>::iterator it=V.rbegin();it!=V.rend();++it){
73nR(i,m-1,0){
74int x=V[i].l;
75while(x<=V[i].r){
76if(!ans[x])
77Paint(x,V[i].w) ;
78x=Find(x)+1;
79}
80}
81R(i,1,n)
82printf("%d ",ans[i]);
83return 0;
84 }
85 /*
86 4 2
87 1 2 4
88 2 4 1
89 */

paint_AC.cpp


 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 using namespace std;
 6 
 7 const int MAXN = 300005 ;
 8 int n, m , first[MAXN] , nexts[MAXN<<1] , 
 9 to[MAXN<<1] , egnum , vis[MAXN], inStack[MAXN] , 
10 inDeg[MAXN] ;
11 char str[MAXN] ;
12 
13 void addEdge(int a, int b){
14nexts[++egnum]=first[a], first[a]=egnum , to[egnum]=b , inDeg[b]++ ;
15 }
16 
17 int dfs(int a){
18inStack[a] = vis[a] = true ;
19for(int i=first[a];i;i=nexts[i]){
20int b=to[i] ;
21if(inStack[b]) return -1 ;
22if(!vis[b]) {
23if(dfs(b)==-1) return -1 ;
24}
25}
26inStack[a] = false ;
27return 0 ;
28 }
29 
30 int que[MAXN] , head , tail , dp[MAXN][26] ;
31 
32 void topoSort(){
33head=tail=0 ;
34for(int i=1;i<=n;++i) if(inDeg[i]==0){
35que[tail++]=i;
36dp[i][str[i]-'a'] = 1 ;
37}
38while(head<tail){
39int a=que[head++] ;
40for(int i=first[a];i;i=nexts[i]){
41int b=to[i] ;
42for(int j=0;j<26;++j) dp[b][j]=max(dp[b][j], dp[a][j]) ;
43int c=str[b]-'a';
44dp[b][c]=max(dp[b][c], dp[a][c]+1) ;
45if(--inDeg[b] == 0){
46que[tail++]=b;
47}
48}
49}
50 }
51 
52 int main(){
53freopen("path.in","r",stdin) ;
54freopen("path.out","w",stdout) ;
55scanf("%d%d%s",&n,&m,str+1) ;
56for(int i=1;i<=m;++i){
57int a,b;
58scanf("%d%d",&a,&b) ;
59addEdge(a,b) ;
60}
61for(int i=1;i<=n;++i){
62if(!vis[i] && dfs(i)==-1){
63printf("-1\n") ;
64return 0 ;
65}
66}
67topoSort() ;
68int ans=0 ;
69for(int i=1;i<=n;++i){
70for(int j=0;j<26;++j){
71ans = max(ans, dp[i][j]) ;
72}
73}
74printf("%d\n",ans) ;
75return 0 ;
76 }

path_STD.cpp


 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 using namespace std;
 6 
 7 const int MAXN = 1005 ;
 8 int n, K, dp[MAXN][MAXN] ; //dp[i][j]琛ㄧず浠涓烘牴錛岃仈閫氬潡澶у皬涓簀鏃舵渶灝戝垹杈規暟
 9 int first[MAXN] , nexts[MAXN<<1] , to[MAXN<<1] , egnum , size[MAXN] ;
10 
11 void addEdge(int a,int b){
12nexts[++egnum] = first[a] ;
13first[a] = egnum ;
14to[egnum]=b;
15 }
16 
17 void dfs(int a,int fa){
18int cnt=0 ;
19size[a]=1 ;
20for(int i=first[a];i;i=nexts[i]) if(to[i]!=fa) ++cnt ;
21dp[a][1] = cnt ;
22for(int i=first[a];i;i=nexts[i]){
23int b=to[i];
24if(b==fa) continue ;
25dfs(b,a) ;
26int lj = min(K, size[a]+size[b]) ;
27for(int j=lj; j>=1; --j){
28int lk1 = max(1, j-size[a]) , lk2 = min(K, size[b]) ;
29for(int k=lk1; k<=lk2; ++k){
30dp[a][j] = min(dp[a][j-k]+dp[b][k]-1, dp[a][j]) ;
31}
32}
33size[a] += size[b] ;
34}
35 }
36 
37 int main(){
38freopen("block.in","r",stdin) ;
39freopen("block.out","w",stdout) ;
40scanf("%d%d",&n, &K) ;
41for(int i=1;i<n;++i){
42int a, b;
43scanf("%d%d",&a,&b) ;
44addEdge(a,b) , addEdge(b,a) ;
45}
46memset(dp,0x3f,sizeof(dp)) ;
47dfs(1,0) ;
48int ans = dp[1][K] ;
49for(int i=2;i<=n;++i) ans = min(ans, dp[i][K]+1) ;
50printf("%d\n",ans) ;
51return 0 ;
52 }

block_STD.cpp

Conclution：

T1：一眼LIS，兩分鐘寫bug半小時改bug 順利A掉 ！

T2：先跳過，後來想出方程，但因為太慫，擔心理解錯誤勞而無功顧全大局而搞了個隨機數，溜了.……

T3：em 可以搞定50分，先讓我敲個20分暴力。。。（一個半小時的光陰似乎確鑿是去了罷）……

T4：haha,區間，線段樹就行了！，，，Wait！線段樹？不是說好DP專場嗎？（雖然標程是並查集*_*?）,方程無果，線段樹也悲傷，帶上40分奇蹟溜了罷

最終：

100+0+10+40=150

排名還是龜速單調不下降，單比Day1不知不覺已上漲十幾名了

CDQZ Day5

您可能也會喜歡…