总结

T1做过 ，所以直接AC T2做了很久，没想到过直接用4维数组DP，只用单纯的2维数组答案一直错 T3想到了并查集，也想到了排序，但没有想到怎样得出答案，即循环边界 T4以为也要用并查集，不知道为什么判断0的答案n为什么错了

T1

a，b数组储存系统里已经有的数字，a数组便于删除、增加数字，b数组便于判断系统里有没有这个数字

#include<bits/stdc++.h> using namespace std; int m,n,ans; int a[1001]; bool b[1001]; int main() { // freopen("translate.in","r",stdin); // freopen("translate.out","w",stdout); scanf("%d %d",&m,&n); int x,l = 0,r = 0; while(n--){ scanf("%d",&x); if(b[x] == false){ ans++; b[x] = true; a[++r] = x; if(r == 1) l=1; } if(r - l + 1> m){ b[a[l]] = false; l++; } } printf("%d",ans); return 0; }

T2

地皮数组：f[a][b][c][d]:表示出了a张爬行牌1，b张爬行牌2，c张爬行牌3，d张爬行牌4时的得分

统计数组：s[x]:表示牌x一共有多少张

#include<bits/stdc++.h> using namespace std; int n,m; int x[400],y[200],s[5],f[45][45][45][45]; int main() { scanf("%d %d",&n,&m); for(int i = 1;i <= n;i++) scanf("%d",&x[i]); for(int i = 1;i <= m;i++) {scanf("%d",&y[i]);s[y[i]]++;} f[0][0][0][0] = x[1]; for(int a=0;a<=s[1];a++) for(int b=0;b<=s[2];b++) for(int c=0;c<=s[3];c++) for(int d=0;d<=s[4];d++) { int i=1+a+b*2+c*3+d*4; if(a!=0) f[a][b][c][d]=max(f[a][b][c][d],f[a-1][b][c][d]+x[i]); if(b!=0) f[a][b][c][d]=max(f[a][b][c][d],f[a][b-1][c][d]+x[i]); if(c!=0) f[a][b][c][d]=max(f[a][b][c][d],f[a][b][c-1][d]+x[i]); if(d!=0) f[a][b][c][d]=max(f[a][b][c][d],f[a][b][c][d-1]+x[i]); } printf("%d",f[s[1]][s[2]][s[3]][s[4]]); return 0; }

T3

并查集：按v降序排列，合并怨气大的：A和B怨气大，B和C有怨气，即合并A和C

#include<bits/stdc++.h> using namespace std; struct info{ int a,b,c; }s[100001]; int n,m; int fa[20001],b[20001]; bool Cmp(const info a,const info b){ return a.c > b.c; } int get(int x){ if(x == fa[x]) return x; return fa[x] = get(fa[x]); } int merge(int x,int y){ return fa[get(x)] = get(y); } int main() { scanf("%d %d",&n,&m); for(int i = 1;i <= n;i++) fa[i] = i; int x,y,c; for(int i = 1;i <= m;i++){ scanf("%d %d %d",&x,&y,&c); s[i].a = x; s[i].b = y; s[i].c = c; } sort(s+1,s+1+m,Cmp); for(int i = 1;i <= m;i++){ if(get(s[i].a) == get(s[i].b)){ printf("%d",s[i].c); return 0; }else{ if(!b[s[i].a]) b[s[i].a]=s[i].b; else merge(b[s[i].a],s[i].b); if(!b[s[i].b]) b[s[i].b]=s[i].a; else merge(b[s[i].b],s[i].a); } } printf("0"); return 0; }

T4

1.无解：直接dfs，用bool标记走过的，遍历没有标记的，输出 2.有解，能证明每个点覆盖的城市(线段)一定是连续的，所以只要求出每个点能到达的最左和最右的点就行了 方法：DP+线段覆盖 对于每个点（i，j） l[i][j]=min(l[k][l]) 点（k，l）是（i，j）能到的的所有点

#include<bits/stdc++.h> using namespace std; # define N 510 int n,m,ans; int h[N][N],l[N][N],r[N][N]; bool vis[N][N]; int fx[4][2]={{-1,0},{0,1},{1,0},{0,-1}}; void dfs(int x,int y){ vis[x][y] = true; for(int i = 0;i < 4;i++){ int tx = x + fx[i][0]; int ty = y + fx[i][1]; if(tx < 1 || tx > n || ty < 1 || ty > m) continue; if(h[tx][ty] >= h[x][y]) continue; if(vis[tx][ty] == false) dfs(tx,ty); l[x][y] = min(l[x][y],l[tx][ty]); r[x][y] = max(r[x][y],r[tx][ty]); printf("%d %d\n",tx,ty); printf("%d %d\n",l[x][y],r[x][y]); } } int main() { memset(l,0x3f,sizeof(l)); scanf("%d %d",&n,&m); for(int i = 1;i <= m;i++) l[n][i] = r[n][i] = i; for(int i = 1;i <= n;i++) for(int j = 1;j <= m;j++) scanf("%d",&h[i][j]); for(int i = 1;i <= m;i++) if(vis[1][i] == false) dfs(1,i); for(int i = 1;i <= m;i++) if(vis[n][i] == false) ans++; if(ans > 0 ) {printf("0\n%d",ans);return 0;} int left=1;ans=0; while (left <= m){ int maxr = 0; for (int i = 1;i <= m;i++) if (l[1][i] <= left) maxr = max(maxr,r[1][i]); ans++; left=maxr+1; } printf("1\n%d",ans); return 0; }