1
DP #1题目名称 题目名称匹配块路径染色输入文件名 输入文件名match.in.in.inblock.inpath.inpaint.in输出文件名 输出文件名match.out.out.out.outblock.outpath.outpaint.out每个测试点时 每个测试点时 每个测试点时 每个测试点时 每个测试点时 每个测试点时 限1s1s1s1.5 s测试点数目 测试点数目10101010每个测试点分 每个测试点分 每个测试点分 每个测试点分 每个测试点分 每个测试点分 值10101010内存限制 内存限制256 M256M256 M256 M是否有部分 是否有部分 是否有部分否否否否题目类型 题目类型传统传统传统传统注意：代码长度限制均为 注意：代码长度限制均为 注意：代码长度限制均为 注意：代码长度限制均为 注意：代码长度限制均为 注意：代码长度限制均为 64K ，不开 ，不开 O2 。21 匹配(match.c/cpp/pas)1.1 题目描述现在有一排花和一排花盆，每株花有互不相同的标号，花盆也有互不相同的标号，标号均为1~n，也就是有 n 株花和 n 个花盆。花与花盆共排成了上下两排，现在希望为尽可能多的花匹配一个对应的花盆，匹配时将为其连上一条直线。要求匹配所产生的直线互不相交，并且为了和谐，匹配的花与花盆标号应当相同。问最多能匹配的对数。1.2 输入格式第一行为一个整数n ，分别表示 A、B 的序列长度。接下来一行 n 个数，表示序列 A。接下来一行 n 个数，表示序列 B。1.3 输出格式输出一行一个整数，表示最多能匹配的对数。1.4 样例输入31 2 31 3 21.5 样例输出21.6 数据范围与约定对于20％的数据，n <= 300。对于40％的数据，n <= 1000。对于100％的数据，n <= 100000。32 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 61 21 21 31 31 41 41 51 52 62 62 72 72 82 84 94 94 104 10 4 104 114 11 4 112.5 .5 .5 样例输出 样例输出22.6 .6 .6 数据范围与约定 数据范围与约定 数据范围与约定 数据范围与约定对于 20％的数据，保证 ％的数据，保证 ％的数据，保证 ％的数据，保证 1 <= n <= 18。对于 50％的数据，保证 ％的数据，保证 ％的数据，保证 ％的数据，保证 1 <= n <= 200。对于 100％的数据，保证 ％的数据，保证 ％的数据，保证 ％的数据，保证 1 <= n <= 1000，1<=K<=n。43 路径 (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 4abaca abaca1 21 21 31 33 43 44 54 53.5 .5 .5 样例输出 样例输出33 .6 .6 .6 数据范围 与约定对于 20％的数据，保证 ％的数据，保证 ％的数据，保证 ％的数据，保证 1 <= n, m <= 10。对于 50％的数据 ，保证 1<=n, m<=5000。对于 100％的数据，保证 ％的数据，保证 ％的数据，保证 ％的数据，保证 1<=n, m<=300000 。54 染色 (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 21 2 42 4 14.5 .5 .5 样例输出 样例输出4 1 1 14.6 .6 .6 数据范围与约定 数据范围与约定 数据范围与约定 数据范围与约定对于 10％的数据，保证 ％的数据，保证 ％的数据，保证 ％的数据，保证 n <= 100。对于 40％的数据 ，保证 n, K<=100000。对于 100％的数据，保证 ％的数据，保证 ％的数据，保证 ％的数据，保证 1<=n, K<=1000000 ，1<=ci<=1000000。
1 #include2 #include 3 #include 4 #include 5 #include 6 #include 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 int10 #define Iv inline void11 #define Il inline long long12 #define Ib inline bool13 #define INF 0x7ffffff14 #define re register15 #define ll long long16 #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(){27 int s=0,f=1;char c;28 for(c=getchar();c>'9'||c<'0';c=getchar())if(c=='-')f=-1;29 while(c>='0'&&c<='9')s=s*10+(c^'0'),c=getchar();30 return s*f;31 }32 Iv print(int x){33 if(x<0)putchar('-'),x=-x;34 if(x>9)print(x/10);35 putchar(x%10^'0');36 }37 int a[N],f[N];38 #define ON_JUDGE39 int main(){40 #ifdef ON_JUDGE41 freopen("match.in","r",stdin),freopen("match.out","w",stdout);42 #endif43 int n=read();44 R(i,1,n)45 a[read()]=i;46 int len=0;47 R(i,1,n){48 int x=a[read()];49 if(x>=f[len])50 f[++len]=x;51 else{52 int l=0,r=len;53 while(l<=r){54 int mid=l+r>>1;55 f[mid]>=x?56 r=mid-1: 57 l=mid+1;58 }59 f[l]=x;60 }61 }62 print(len);63 return 0;64 }65 /*66 467 1 0 9 768 1 9 7 069 70 571 1 1 1 0 272 1 1 0 1 273 74 675 2 3 9 7 5 776 3 4 7 8 5 777 78 779 4 5 2 3 6 7 180 1 3 4 2 5 6 181 82 783 1 3 2 4 5 6 784 3 1 4 2 6 5 785 */
1 #include2 #include 3 #include 4 #include 5 #include 6 #include 7 #include 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(){ 28 int s=0,f=1;char c; 29 for(c=getchar();c>'9'||c<'0';c=getchar())if(c=='-')f=-1; 30 while(c>='0'&&c<='9')s=s*10+(c^'0'),c=getchar(); 31 return s*f; 32 } 33 Iv print(int x){ 34 if(x<0)putchar('-'),x=-x; 35 if(x>9)print(x/10); 36 putchar(x%10^'0'); 37 } 38 int w[N],f[N][26]; 39 vector V[N]; 40 //bitset vis; 41 int ans=1; 42 Iv dfs(int u){ 43 //vis[u]=1; 44 for(vector ::iterator v=V[u].begin();v!=V[u].end();++v){ 45 R(col,0,25) 46 f[*v][col]+=f[u][col]; 47 dfs(*v); 48 } 49 Cmax(ans,f[u][w[u]]); 50 } 51 char s[N]; 52 #define ON_JUDGE 53 int main(){ 54 #ifdef ON_JUDGE 55 freopen("path.in","r",stdin),freopen("path.out","w",stdout); 56 #endif 57 int n=read(),m=read(); 58 if(n<=500){ 59 scanf("%s",s+1); 60 R(i,1,n) 61 w[i]=(s[i]^'a'); 62 R(i,1,m){ 63 int u=read(),v=read(); 64 V[u].push_back(v); 65 } 66 R(i,1,n) 67 { 68 R(j,1,n){ 69 R(col,0,25) 70 f[j][col]=0; 71 f[j][w[j]]=1; 72 } 73 dfs(i); 74 } 75 print(ans); 76 } 77 else 78 printf("-1"); 79 return 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 3100 3 4101 4 5102 5 6103 104 7 6105 abacaaa106 1 2107 1 3108 3 4109 4 5110 5 6111 6 7112 113 8 8114 acacacaa115 2 1116 1 4117 3 1118 5 3119 6 5120 6 4121 3 7122 7 8123 */
1 #include2 #include 3 #include 4 #include 5 #include 6 #include 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 int10 #define Iv inline void11 #define Il inline long long12 #define Ib inline bool13 #define INF 0x7ffffff14 #define re register15 #define ll long long16 #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(){27 int s=0,f=1;char c;28 for(c=getchar();c>'9'||c<'0';c=getchar())if(c=='-')f=-1;29 while(c>='0'&&c<='9')s=s*10+(c^'0'),c=getchar();30 return s*f;31 }32 Iv print(ll x){33 if(x<0)putchar('-'),x=-x;34 if(x>9)print(x/10);35 putchar(x%10^'0');36 }37 //#define ON_JUDGE38 struct Question{39 int l,r,w;40 void Init(){l=read(),r=read(),w=read();}41 };42 int fa[N],ans[N];43 vector V;44 Ii Find(int x){45 return x==fa[x]?x:fa[x]=Find(fa[x]);46 }47 Iv Union(int x,int y){48 x=Find(x),y=Find(y);49 if(x!=y)50 fa[x]=y;51 }52 int n;53 Iv Paint(int x,int w){54 ans[x]=w;55 if(x!=1&&ans[x-1])Union(x-1,x);56 if(x!=n&&ans[x+1])Union(x,x+1);57 }58 #define ON_JUDGE59 int main(){60 #ifdef ON_JUDGE61 freopen("paint.in","r",stdin),freopen("paint.out","w",stdout);62 #endif63 n=read();64 int m=read();65 R(i,1,m){66 Question ques;67 ques.Init(),68 V.push_back(ques);69 //V.push_back((Question){read(),read(),read()});70 }71 R(i,1,n)fa[i]=i;72 //for(vector ::iterator it=V.rbegin();it!=V.rend();++it){ 73 nR(i,m-1,0){74 int x=V[i].l;75 while(x<=V[i].r){76 if(!ans[x])77 Paint(x,V[i].w) ;78 x=Find(x)+1;79 }80 }81 R(i,1,n)82 printf("%d ",ans[i]);83 return 0;84 }85 /*86 4 287 1 2 488 2 4 189 */
1 #include2 #include 3 #include 4 #include 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){14 nexts[++egnum]=first[a], first[a]=egnum , to[egnum]=b , inDeg[b]++ ;15 }16 17 int dfs(int a){18 inStack[a] = vis[a] = true ;19 for(int i=first[a];i;i=nexts[i]){20 int b=to[i] ;21 if(inStack[b]) return -1 ;22 if(!vis[b]) {23 if(dfs(b)==-1) return -1 ;24 }25 }26 inStack[a] = false ;27 return 0 ;28 }29 30 int que[MAXN] , head , tail , dp[MAXN][26] ;31 32 void topoSort(){33 head=tail=0 ;34 for(int i=1;i<=n;++i) if(inDeg[i]==0){35 que[tail++]=i;36 dp[i][str[i]-'a'] = 1 ;37 }38 while(head
1 #include2 #include 3 #include 4 #include 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){12 nexts[++egnum] = first[a] ;13 first[a] = egnum ;14 to[egnum]=b;15 }16 17 void dfs(int a,int fa){18 int cnt=0 ;19 size[a]=1 ;20 for(int i=first[a];i;i=nexts[i]) if(to[i]!=fa) ++cnt ;21 dp[a][1] = cnt ;22 for(int i=first[a];i;i=nexts[i]){23 int b=to[i];24 if(b==fa) continue ;25 dfs(b,a) ;26 int lj = min(K, size[a]+size[b]) ;27 for(int j=lj; j>=1; --j){28 int lk1 = max(1, j-size[a]) , lk2 = min(K, size[b]) ;29 for(int k=lk1; k<=lk2; ++k){30 dp[a][j] = min(dp[a][j-k]+dp[b][k]-1, dp[a][j]) ;31 }32 }33 size[a] += size[b] ;34 }35 }36 37 int main(){38 freopen("block.in","r",stdin) ;39 freopen("block.out","w",stdout) ;40 scanf("%d%d",&n, &K) ;41 for(int i=1;i
1 #include2 #include 3 #include 4 #include 5 #include 6 #include 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 int10 #define Iv inline void11 #define Il inline long long12 #define Ib inline bool13 #define INF 0x7ffffff14 #define re register15 #define ll long long16 #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=300005;26 Ii read(){27 int s=0,f=1;char c;28 for(c=getchar();c>'9'||c<'0';c=getchar())if(c=='-')f=-1;29 while(c>='0'&&c<='9')s=s*10+(c^'0'),c=getchar();30 return s*f;31 }32 Iv print(int x){33 if(x<0)putchar('-'),x=-x;34 if(x>9)print(x/10);35 putchar(x%10^'0');36 }37 Ii dfs(int u){38 39 }40 Iv Topsort(){41 int h=0,t=0;42 R(i,1,n)43 if(in[i]==0)44 q.push(i),45 f[i][str[i]^'a']=1;46 while(h
