市赛 - 网页学习体会

比赛链接:http://acm.upc.edu.cn/problemset.php?page=22

E题：运送货物

题意：从1到n有很多道路，但是每条道路有上限，一张图，判断1到n的道路上的能通过的最小权值的最大值，

思路：并查集（其实就是最大生成树，改掉最小生成树的排序，按照从大到小排序即可）

结构体按从大到小排好序，然后遍历，不同集合合并，如果遍历到这条边，恰好1，n在一个集合里了，就停止，输出该条边的权值。因为向下的边更小了。

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<algorithm>
 4 #include<vector>
 5 
 6 using namespace std;
 7 
 8 const int maxn=1024;
 9 int T, n, m, a, b, l;
10 int p[maxn];
11 
12 int Find(int u)
13 {
14     return u==p[u]? u: p[u]=Find(p[u]);
15 }
16 
17 struct Edge
18 {
19     int x, y, l;
20     Edge(int x_, int y_, int l_) :x(x_), y(y_), l(l_) {}
21     bool operator <(const Edge& rhs) const
22     {
23         return l<rhs.l;
24     }
25 };
26 
27 vector<Edge> v;
28 
29 void init()
30 {
31     scanf("%d%d", &n, &m);
32     for(int i =0; i<maxn ; ++i) p[i]=i;
33     v.clear();
34 
35     for(int i =0; i<m; ++i)
36     {
37         scanf("%d%d%d", &a, &b, &l);
38         v.push_back(Edge(a, b, l));
39     }
40     sort(v.begin(), v.end());///按权值从大到小排序
41 }
42 
43 int solve()
44 {
45     int res=0;
46     for(int i=v.size(); --i>=0;)
47     {
48         Edge& t=v[i];
49         int pu=Find(t.x);
50         int pv=Find(t.y);
51         if(pu!=pv)///如果pu和pv不在一个集合，合并
52         {
53             p[pu]=pv;
54         }
55         if(Find(1) == Find(n))///如果1，n在一个集合就停,向下走的话，权值更小了
56         {
57             res=t.l;
58             break;
59         }
60     }
61     return res;
62 }
63 
64 int main()
65 {
66     scanf("%d", &T);
67     while(T--)
68     {
69         init();
70         printf("%d
", solve());
71     }
72     return 0;
73 }

View Code

题意：告诉你盘子的数目，求出移动M步后的三个柱子上的步数，1 <= M <= 2^100-1；

1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 using namespace std; 5 6 int ans[5],b[130]; 7 char str[130]; 8 9 void binary()///把M转化为2进制 10 { 11 int i,p=0,k=0,l,a[130]; 12 memset(b,0,sizeof(b)); 13 l=strlen(str); 14 for(i=0; i<l; i++) 15 a[i]=str[i]-'0'; 16 while(p < l) 17 { 18 int mod=0; 19 for(i=p; i<l; i++) 20 { 21 a[i]=mod*10+a[i]; 22 mod=a[i]&1; 23 a[i]>>=1; 24 } 25 b[k++] = mod; 26 if(!a[p]) 27 p++; 28 } 29 } 30 31 void hanoi(int A,int B,int C,int k)///移动第k个盘子 32 { 33 if(k<=0) return; 34 if(b[k-1])///如果该位置是1，移动的步数为。。。 35 { 36 ans[A] -= k; 37 ans[B] += k-1; 38 ans[C]++; 39 hanoi(B,A,C,k-1); 40 } 41 else 42 hanoi(A,C,B,k-1); 43 } 44 45 int main() 46 { 47 int N; 48 while(scanf("%d%s",&N,str),N||str[0]!='0') 49 { 50 binary(); 51 ans[0]=N;///初始化 52 ans[1]=0; 53 ans[2]=0; 54 hanoi(0,1,2,N); 55 printf(" %d %d %d ",ans[0],ans[1],ans[2]); 56 } 57 return 0; 58 }

1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <string> 5 #define repu(i,a,b) for(int i=a;i<b;i++) 6 #include <queue> 7 using namespace std; 8 int dx[4]= {1,0,-1,0}; 9 int dy[4]= {0,1,0,-1}; 10 int w,h; 11 char g[1200][1220]; 12 int vis[7]; 13 struct point 14 { 15 int x,y; 16 }; 17 void dfs(const point &t) 18 { 19 int x,y,a,b,i; 20 x=t.x; 21 y=t.y; 22 point tmp; 23 if (g[x][y]=='.') return ; 24 else if(g[x][y] == 'B') vis[0] = 1;///开全局担心有点浪费空间 25 else if(g[x][y] == 'G') vis[1] = 1; 26 else if(g[x][y] == 'W') vis[2] = 1; 27 else if(g[x][y] == 'R') vis[3] = 1; 28 else if(g[x][y] == 'Y') vis[4] = 1; 29 g[x][y]='.'; 30 repu(i,0,4) 31 { 32 a = x + dx[i]; 33 b = y + dy[i]; 34 if (a < 0||b < 0||a >= h||b >= w) 35 continue; 36 tmp.x = a; 37 tmp.y = b; 38 dfs(tmp); 39 } 40 return; 41 } 42 43 int main() 44 { 45 int t[7]; 46 //freopen("1.txt","r",stdin); 47 int kase; 48 cin>>kase; 49 while(kase--) 50 { 51 cin>>h>>w; 52 point tmp; 53 memset(t,0,sizeof(t)); 54 repu(i,0,h) 55 cin>>g[i]; 56 repu(i,0,h) 57 repu(j,0,w) 58 if(g[i][j]!='.') 59 { 60 tmp.x=i; 61 tmp.y=j; 62 dfs(tmp); 63 int v = 0; 64 repu(i,0,6)///而且还有循环，浪费时间 65 if(vis[i]) 66 v++; 67 t[v]++; 68 memset(vis,0,sizeof(vis)); 69 } 70 repu(i,1,5) 71 cout<<t[i]<<" "; 72 cout<<t[5]<<endl; 73 } 74 return 0; 75 }

市赛

相关推荐