CDQZ Day5

1
DP #1
题目名称题目名称
匹配
块
路径
染色
输入文件名输入文件名
match.in.in.in
block.in
path.in
paint.in
输出文件名输出文件名
match.out.out.out.out
block.out
path.out
paint.out
每个测试点时每个测试点时每个测试点时每个测试点时每个测试点时每个测试点时限
1s
1s
1s
1.5 s
测试点数目测试点数目
10
10
10
10
每个测试点分每个测试点分每个测试点分每个测试点分每个测试点分每个测试点分值
10
10
10
10
内存限制内存限制
256 M
256M
256 M
256 M
是否有部分是否有部分是否有部分
否
否
否
否
题目类型题目类型
传统
传统
传统
传统
注意：代码长度限制均为注意：代码长度限制均为注意：代码长度限制均为注意：代码长度限制均为注意：代码长度限制均为注意：代码长度限制均为 64K ，不开，不开 O2 。
2
1 匹配(match.c/cpp/pas)
1.1 题目描述
现在有一排花和一排花盆，每株花有互不相同的标号，花盆也有互不相同的标号，标号
均为1~n，也就是有 n 株花和 n 个花盆。
花与花盆共排成了上下两排，现在希望为尽可能多的花匹配一个对应的花盆，匹配时将
为其连上一条直线。要求匹配所产生的直线互不相交，并且为了和谐，匹配的花与花盆标号
应当相同。
问最多能匹配的对数。
1.2 输入格式
第一行为一个整数n ，分别表示 A、B 的序列长度。
接下来一行 n 个数，表示序列 A。
接下来一行 n 个数，表示序列 B。
1.3 输出格式
输出一行一个整数，表示最多能匹配的对数。
1.4 样例输入
3
1 2 3
1 3 2
1.5 样例输出
2
1.6 数据范围与约定
对于20％的数据，n <= 300。
对于40％的数据，n <= 1000。
对于100％的数据，n <= 100000。
3
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
2.6 .6 .6 数据范围与约定数据范围与约定数据范围与约定数据范围与约定
对于 20％的数据，保证％的数据，保证％的数据，保证％的数据，保证 1 <= n <= 18。
对于 50％的数据，保证％的数据，保证％的数据，保证％的数据，保证 1 <= n <= 200。
对于 100％的数据，保证％的数据，保证％的数据，保证％的数据，保证 1 <= n <= 1000，1<=K<=n。
4
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
3 .6 .6 .6 数据范围与约定
对于 20％的数据，保证％的数据，保证％的数据，保证％的数据，保证 1 <= n, m <= 10。
对于 50％的数据，保证 1<=n, m<=5000。
对于 100％的数据，保证％的数据，保证％的数据，保证％的数据，保证 1<=n, m<=300000 。
5
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。

 #include<cstdio>

 #include<cstring>

 #include<iostream>

 #include<algorithm>

 #include<cmath>

 #include<vector>

 #define R(a,b,c) for(register int (a)=(b);(a)<=(c);++(a))

 #define nR(a,b,c) for(register int (a)=(b);(a)>=(c);--(a))

 #define Ii inline int

 #define Iv inline void

 #define Il inline long long

 #define Ib inline bool

 #define INF 0x7ffffff

 #define re register

 #define ll long long

 #define Max(a,b) ((a)>(b)?(a):(b))

 #define Min(a,b) ((a)<(b)?(a):(b))

 #define Cmin(a,b) ((a)=(a)<(b)?(a):(b))

 #define Cmax(a,b) ((a)=(a)>(b)?(a):(b))

 #define Fill(a,b) memset((a),(b),sizeof((a)))

 #define D_e_Line printf("\n-------------\n");

 #define D_e(x) printf("\n______%d_______\n",x)

 #define Pause system("pause")

 using namespace std;

 const int N=;

 Ii read(){

     int s=,f=;char c;

     for(c=getchar();c>''||c<'';c=getchar())if(c=='-')f=-;

     while(c>=''&&c<='')s=s*+(c^''),c=getchar();

     return s*f;

 }

 Iv print(int x){

     if(x<)putchar('-'),x=-x;

     if(x>)print(x/);

     putchar(x%^'');

 }

 int a[N],f[N];

 #define ON_JUDGE

 int main(){

 #ifdef ON_JUDGE

     freopen("match.in","r",stdin),freopen("match.out","w",stdout);

 #endif

     int n=read();

     R(i,,n)

         a[read()]=i;

     int len=;

     R(i,,n){

         int x=a[read()];

         if(x>=f[len])

             f[++len]=x;

         else{

             int l=,r=len;

             while(l<=r){

                 int mid=l+r>>;

                 f[mid]>=x?

                     r=mid-:

                     l=mid+;

             }

             f[l]=x;

         }

     }

     print(len);

     return ;

 }

 /*

 4

 1 0 9 7

 1 9 7 0

 5

 1 1 1 0 2

 1 1 0 1 2

 6

 2 3 9 7 5 7

 3 4 7 8 5 7

 7

 4 5 2 3 6 7 1

 1 3 4 2 5 6 1

 7

 1 3 2 4 5 6 7

 3 1 4 2 6 5 7

 */

match_My_CreatOnContest.cpp

 #include<cstdio>

 #include<cstring>

 #include<iostream>

 #include<algorithm>

 #include<cmath>

 #include<vector>

 #include<bitset>

 #define R(a,b,c) for(register int (a)=(b);(a)<=(c);++(a))

 #define nR(a,b,c) for(register int (a)=(b);(a)>=(c);--(a))

 #define Ii inline int

 #define Iv inline void

 #define Il inline long long

 #define Ib inline bool

 #define INF 0x7ffffff

 #define re register

 #define ll long long

 #define Max(a,b) ((a)>(b)?(a):(b))

 #define Min(a,b) ((a)<(b)?(a):(b))

 #define Cmin(a,b) ((a)=(a)<(b)?(a):(b))

 #define Cmax(a,b) ((a)=(a)>(b)?(a):(b))

 #define Fill(a,b) memset((a),(b),sizeof((a)))

 #define D_e_Line printf("\n-------------\n");

 #define D_e(x) printf("\n______%d_______\n",x)

 #define Pause system("pause")

 using namespace std;

 const int N=;

 Ii read(){

     int s=,f=;char c;

     for(c=getchar();c>''||c<'';c=getchar())if(c=='-')f=-;

     while(c>=''&&c<='')s=s*+(c^''),c=getchar();

     return s*f;

 }

 Iv print(int x){

     if(x<)putchar('-'),x=-x;

     if(x>)print(x/);

     putchar(x%^'');

 }

 int w[N],f[N][];

 vector<int>V[N];

 //bitset<N>vis;

 int ans=;

 Iv dfs(int u){

     //vis[u]=1;

     for(vector<int>::iterator v=V[u].begin();v!=V[u].end();++v){

             R(col,,)

                 f[*v][col]+=f[u][col];

             dfs(*v);

         }

     Cmax(ans,f[u][w[u]]);

 }

 char s[N];

 #define ON_JUDGE

 int main(){

 #ifdef ON_JUDGE

     freopen("path.in","r",stdin),freopen("path.out","w",stdout);

 #endif

     int n=read(),m=read();

     if(n<=){

         scanf("%s",s+);

         R(i,,n)

             w[i]=(s[i]^'a');

         R(i,,m){

             int u=read(),v=read();

             V[u].push_back(v);

         }

         R(i,,n)

             {

                 R(j,,n){

                     R(col,,)

                         f[j][col]=;

                     f[j][w[j]]=;

                 }

                 dfs(i);

             }

         print(ans);

     }

     else

         printf("-1");

     return ;

 }

 /*

 5 4

 abaca

 1 2

 1 3

 3 4

 4 5

 5 4

 abacc

 1 2

 1 3

 3 4

 4 5

 6 5

 abcdcc

 1 2

 1 3

 3 4

 4 5

 5 6

 7 6

 abacaaa

 1 2

 1 3

 3 4

 4 5

 5 6

 6 7

 8 8

 acacacaa

 2 1

 1 4

 3 1

 5 3

 6 5

 6 4

 3 7

 7 8

 */

path_My_CreatOnContest.cpp

 #include<cstdio>

 #include<cstring>

 #include<iostream>

 #include<algorithm>

 #include<cmath>

 #include<vector>

 #define R(a,b,c) for(register int (a)=(b);(a)<=(c);++(a))

 #define nR(a,b,c) for(register int (a)=(b);(a)>=(c);--(a))

 #define Ii inline int

 #define Iv inline void

 #define Il inline long long

 #define Ib inline bool

 #define INF 0x7ffffff

 #define re register

 #define ll long long

 #define Max(a,b) ((a)>(b)?(a):(b))

 #define Min(a,b) ((a)<(b)?(a):(b))

 #define Cmin(a,b) ((a)=(a)<(b)?(a):(b))

 #define Cmax(a,b) ((a)=(a)>(b)?(a):(b))

 #define Fill(a,b) memset((a),(b),sizeof((a)))

 #define D_e_Line printf("\n-------------\n");

 #define D_e(x) printf("\n______%d_______\n",x)

 #define Pause system("pause")

 using namespace std;

 const int N=;

 Ii read(){

     int s=,f=;char c;

     for(c=getchar();c>''||c<'';c=getchar())if(c=='-')f=-;

     while(c>=''&&c<='')s=s*+(c^''),c=getchar();

     return s*f;

 }

 Iv print(ll x){

     if(x<)putchar('-'),x=-x;

     if(x>)print(x/);

     putchar(x%^'');

 }

 //#define ON_JUDGE

 struct Question{

     int l,r,w;

     void Init(){l=read(),r=read(),w=read();}

 };

 int fa[N],ans[N];

 vector<Question>V;

 Ii Find(int x){

     return x==fa[x]?x:fa[x]=Find(fa[x]);

 }

 Iv Union(int x,int y){

     x=Find(x),y=Find(y);

     if(x!=y)

         fa[x]=y;

 }

 int n;

 Iv Paint(int x,int w){

     ans[x]=w;

     if(x!=&&ans[x-])Union(x-,x);

     if(x!=n&&ans[x+])Union(x,x+);

 }

 #define ON_JUDGE

 int main(){

 #ifdef ON_JUDGE

     freopen("paint.in","r",stdin),freopen("paint.out","w",stdout);

 #endif

     n=read();

     int m=read();

     R(i,,m){

         Question ques;

         ques.Init(),

         V.push_back(ques);

         //V.push_back((Question){read(),read(),read()});

     }

     R(i,,n)fa[i]=i;

     //for(vector<int>::iterator it=V.rbegin();it!=V.rend();++it){

     nR(i,m-,){

         int x=V[i].l;

         while(x<=V[i].r){

             if(!ans[x])

                 Paint(x,V[i].w) ;

             x=Find(x)+;

         }

     }

     R(i,,n)

         printf("%d ",ans[i]);

     return ;

 }

 /*

 4 2

 1 2 4

 2 4 1

 */

paint_AC.cpp

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 using namespace std;

 const int MAXN =  ;

 int n, m , first[MAXN] , nexts[MAXN<<] ,

 to[MAXN<<] , egnum , vis[MAXN], inStack[MAXN] ,

 inDeg[MAXN] ;

 char str[MAXN] ;

 void addEdge(int a, int b){

     nexts[++egnum]=first[a], first[a]=egnum , to[egnum]=b , inDeg[b]++ ;

 }

 int dfs(int a){

     inStack[a] = vis[a] = true ;

     for(int i=first[a];i;i=nexts[i]){

         int b=to[i] ;

         if(inStack[b]) return - ;

         if(!vis[b]) {

             if(dfs(b)==-) return - ;

         }

     }

     inStack[a] = false ;

     return  ;

 }

 int que[MAXN] , head , tail , dp[MAXN][] ;

 void topoSort(){

     head=tail= ;

     for(int i=;i<=n;++i) if(inDeg[i]==){

         que[tail++]=i;

         dp[i][str[i]-'a'] =  ;

     }

     while(head<tail){

         int a=que[head++] ;

         for(int i=first[a];i;i=nexts[i]){

             int b=to[i] ;

             for(int j=;j<;++j) dp[b][j]=max(dp[b][j], dp[a][j]) ;

             int c=str[b]-'a';

             dp[b][c]=max(dp[b][c], dp[a][c]+) ;

             if(--inDeg[b] == ){

                 que[tail++]=b;

             }

         }

     }

 }

 int main(){

     freopen("path.in","r",stdin) ;

     freopen("path.out","w",stdout) ;

     scanf("%d%d%s",&n,&m,str+) ;

     for(int i=;i<=m;++i){

         int a,b;

         scanf("%d%d",&a,&b) ;

         addEdge(a,b) ;

     }

     for(int i=;i<=n;++i){

         if(!vis[i] && dfs(i)==-){

             printf("-1\n") ;

             return  ;

         }

     }

     topoSort() ;

     int ans= ;

     for(int i=;i<=n;++i){

         for(int j=;j<;++j){

             ans = max(ans, dp[i][j]) ;

         }

     }

     printf("%d\n",ans) ;

     return  ;

 }

path_STD.cpp

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 using namespace std;

 const int MAXN =  ;

 int n, K, dp[MAXN][MAXN] ; //dp[i][j]琛ㄧず浠涓烘牴锛岃仈閫氬潡澶у皬涓簀鏃舵渶灏戝垹杈规暟

 int first[MAXN] , nexts[MAXN<<] , to[MAXN<<] , egnum , size[MAXN] ;

 void addEdge(int a,int b){

     nexts[++egnum] = first[a] ;

     first[a] = egnum ;

     to[egnum]=b;

 }

 void dfs(int a,int fa){

     int cnt= ;

     size[a]= ;

     for(int i=first[a];i;i=nexts[i]) if(to[i]!=fa) ++cnt ;

     dp[a][] = cnt ;

     for(int i=first[a];i;i=nexts[i]){

         int b=to[i];

         if(b==fa) continue ;

         dfs(b,a) ;

         int lj = min(K, size[a]+size[b]) ;

         for(int j=lj; j>=; --j){

             int lk1 = max(, j-size[a]) , lk2 = min(K, size[b]) ;

             for(int k=lk1; k<=lk2; ++k){

                 dp[a][j] = min(dp[a][j-k]+dp[b][k]-, dp[a][j]) ;

             }

         }

         size[a] += size[b] ;

     }

 }

 int main(){

     freopen("block.in","r",stdin) ;

     freopen("block.out","w",stdout) ;

     scanf("%d%d",&n, &K) ;

     for(int i=;i<n;++i){

         int a, b;

         scanf("%d%d",&a,&b) ;

         addEdge(a,b) , addEdge(b,a) ;

     }

     memset(dp,0x3f,sizeof(dp)) ;

     dfs(,) ;

     int ans = dp[][K] ;

     for(int i=;i<=n;++i) ans = min(ans, dp[i][K]+) ;

     printf("%d\n",ans) ;

     return  ;

 }

block_STD.cpp

 #include<cstdio>

 #include<cstring>

 #include<iostream>

 #include<algorithm>

 #include<cmath>

 #include<vector>

 #define R(a,b,c) for(register int (a)=(b);(a)<=(c);++(a))

 #define nR(a,b,c) for(register int (a)=(b);(a)>=(c);--(a))

 #define Ii inline int

 #define Iv inline void

 #define Il inline long long

 #define Ib inline bool

 #define INF 0x7ffffff

 #define re register

 #define ll long long

 #define Max(a,b) ((a)>(b)?(a):(b))

 #define Min(a,b) ((a)<(b)?(a):(b))

 #define Cmin(a,b) ((a)=(a)<(b)?(a):(b))

 #define Cmax(a,b) ((a)=(a)>(b)?(a):(b))

 #define Fill(a,b) memset((a),(b),sizeof((a)))

 #define D_e_Line printf("\n-------------\n");

 #define D_e(x) printf("\n______%d_______\n",x)

 #define Pause system("pause")

 using namespace std;

 const int N=;

 Ii read(){

     int s=,f=;char c;

     for(c=getchar();c>''||c<'';c=getchar())if(c=='-')f=-;

     while(c>=''&&c<='')s=s*+(c^''),c=getchar();

     return s*f;

 }

 Iv print(int x){

     if(x<)putchar('-'),x=-x;

     if(x>)print(x/);

     putchar(x%^'');

 }

 Ii dfs(int u){

 }

 Iv Topsort(){

     int h=,t=;

     R(i,,n)

         if(in[i]==)

             q.push(i),

             f[i][str[i]^'a']=;

     while(h<t){

         int u=q.top();

         for(vector<int>::iterator v=V[u].begin();v!=V[u].end();++v){

             R(j,,)

                 Cmax(f[*v][j],f[u][j]);

             int c=str[b]^'a';

             Cmax(f[*v][c],f[u][c]+);

             if(--in[*v]==)

                 q.push(*v);

         }

     }

 }

 #define ON_JUDGE

 char s[N];

 int main(){

 #ifdef ON_JUDGE

     freopen("path.in","r",stdin),freopen("path.out","w",stdout);

 #endif

     int n=read(),m=read();

     scanf("%s",str+);

     R(i,,m){

         int u=read(),v=read();

         V[u].push_back(v);

     }

     R(i,,n)

         if(!vis[i]&&dfs(i)==-){

             printf("-1\n");return ;

         }

     Toposort();

     int ans=;

     R(i,,n)

         R(j,,)

             Cmax(ans,f[i][j]);

     print(ans);

     return ;

 }

 /*

 4 2

 1 2 4

 2 4 1

 */

path_Unfinished.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

最新文章

热门文章