http://acm.sdut.edu.cn/sdutoj/problem.php?action=showproblem&problemid=2417
找峰值点 从小到大输出
View Code
1 #include<stdio.h> 2 #include<string.h> 3 int a[50001],b[50001]; 4 int main() 5 { 6 int i,j,k,n,m; 7 while(scanf("%d", &n)!=EOF) 8 { 9 int g = 0; 10 for(i = 1; i <= n ; i++) 11 scanf("%d", &a[i]); 12 if(n==1) 13 { 14 printf("1\n"); 15 continue; 16 } 17 if(a[1]>=a[2]) 18 b[g++] = 1; 19 for(i = 2 ; i < n ; i++) 20 { 21 if(a[i-1]<=a[i]&&a[i]>=a[i+1]) 22 b[g++] = i; 23 } 24 if(a[n]>=a[n-1]) 25 b[g++] = n; 26 for(i = 0 ;i < g ; i++) 27 printf("%d\n",b[i]); 28 } 29 return 0; 30 }
http://acm.sdut.edu.cn/sdutoj/problem.php?action=showproblem&problemid=2418
并查集 注意是多组
View Code
1 #include<stdio.h> 2 #include<string.h> 3 #include<math.h> 4 struct node 5 { 6 int u,v; 7 }q[10011]; 8 int father[10011],r[10011],w[111][111]; 9 int find(int x) 10 { 11 if(x!=father[x]) 12 father[x] = find(father[x]); 13 return father[x]; 14 } 15 int main() 16 { 17 int n,m,k,i,j,a,b,g = 0; 18 while(scanf("%d%d%d", &n,&m,&k)!=EOF) 19 { 20 memset(w,0,sizeof(w)); 21 g = 0; 22 for(i = 1; i <= k ; i++) 23 { 24 father[i] = i; 25 r[i] = 1; 26 } 27 for(i = 1; i <= k ; i++) 28 { 29 scanf("%d%d", &a,&b); 30 if(w[a][b]==0&&a>=1&&a<=n&&b>=1&&b<=m) 31 { 32 q[++g].u = a; 33 q[g].v = b; 34 w[a][b] =1; 35 } 36 } 37 for(i = 1; i < g ; i++) 38 { 39 for(j = i+1; j <= g ; j++) 40 { 41 if((abs(q[i].u-q[j].u)==1&&q[i].v==q[j].v)||(q[i].u==q[j].u&&abs(q[i].v-q[j].v)==1)) 42 { 43 int px = find(i); 44 int py = find(j); 45 if(px!=py) 46 { 47 father[px] = py; 48 r[py]+=r[px]; 49 } 50 } 51 } 52 } 53 int max = 0; 54 for(i = 1; i <= g ; i++) 55 if(max<r[i]) 56 max= r[i]; 57 printf("%d\n",max); 58 } 59 return 0; 60 }
http://acm.sdut.edu.cn/sdutoj/problem.php?action=showproblem&problemid=2420
记录每个1前面2的个数 和每个1后面1的个数 找min{d[i][1]+d[i][2]}
View Code
1 #include<stdio.h> 2 #include<string.h> 3 int a[30001],b[30001],d[30001][3]; 4 int main() 5 { 6 int i,j,k,n,m,min; 7 while(scanf("%d", &n)!=EOF) 8 { 9 memset(d,0,sizeof(d)); 10 min = 50000; 11 int f = 0; 12 for(i =1; i <= n ; i++) 13 { 14 scanf("%d", &a[i]); 15 } 16 for(i = 1; i <= n ; i++) 17 { 18 if(a[i]==1) 19 d[i][2] = d[i-1][2]; 20 else 21 d[i][2] = d[i-1][2]+1; 22 } 23 for(i = n ; i >= 1; i--) 24 { 25 if(a[i]==2) 26 d[i][1] = d[i+1][1]; 27 else 28 d[i][1] = d[i+1][1]+1; 29 } 30 for(i = 1 ; i <= n ; i++) 31 { 32 if(a[i]==1) 33 { 34 if(min>d[i][1]+d[i][2]-1) 35 min = d[i][1]+d[i][2]-1; 36 f = 1; 37 } 38 } 39 if(!f) 40 min = 0; 41 printf("%d\n",min); 42 } 43 return 0; 44 }
http://acm.sdut.edu.cn/sdutoj/problem.php?action=showproblem&problemid=2421
这题描述的太不清楚了 n值并不表示 最多就有n个点 从输入里面找一个最大值
因为走到头要返回 而只有最后一次走不用返回 所以最后走那一条最长的
最小生成树 求出和S 用S-生成树中最长的那一条
View Code
1 #include <iostream> 2 #include<cstdio> 3 #include<string.h> 4 using namespace std; 5 #define INF 100000000 6 int w[501][501],d[501],vis[501],dis[501]; 7 void prime(int n) 8 { 9 int i,j,k,s = 0; 10 memset(vis,0,sizeof(vis)); 11 vis[0] = 1; 12 for(i = 0; i <= n ; i++) 13 { 14 d[i] = w[0][i]; 15 if(w[0][i]!=INF) 16 dis[i] = w[0][i]; 17 else 18 dis[i]= 0; 19 } 20 for(i = 0; i <= n ;i++) 21 { 22 int min = INF; 23 for(j = 0; j <= n ;j++) 24 if(!vis[j]&&d[j]<min) 25 min = d[k= j]; 26 if(min == INF) 27 break; 28 s+=min; 29 vis[k] = 1; 30 for(j = 0; j <= n ;j++) 31 if(!vis[j]&&d[j]>w[k][j]) 32 { 33 d[j] = w[k][j]; 34 dis[j] = dis[k]+w[k][j]; 35 } 36 } 37 int mi = -1; 38 for(i = 1; i <= n ; i++) 39 { 40 41 if(dis[i]>mi) 42 mi = dis[i]; 43 } 44 printf("%d\n",s*2-mi); 45 } 46 int main() 47 { 48 int i,j,k,n,m,a,b,c; 49 while(scanf("%d", &n)!=EOF) 50 { 51 for(i = 0 ;i <= 100; i++) 52 { 53 for(j = 0 ; j <= 100; j++) 54 w[i][j] = INF; 55 w[i][i] = 0; 56 } 57 m = 0; 58 for(i = 1; i <= n ; i++) 59 { 60 scanf("%d%d%d",&a,&b,&c); 61 if(w[a][b]>c) 62 { 63 w[a][b] = c; 64 w[b][a] = c; 65 } 66 if(a>m) 67 m = a; 68 if(b>m) 69 m = b; 70 } 71 prime(m); 72 } 73 return 0; 74 }