首页 > 代码库 > 山东省第一届acm程序设计竞赛题解
山东省第一届acm程序设计竞赛题解
缺c 计算几何没看 f一个模拟，不想写，难度不大，J，因为时间挺早的，题目都比较简单，没什么难度，组队出个8题还是轻松的
A:水题
1 #include<bits/stdc++.h> 2 using namespace std; 3 const int maxn=1e3+5; 4 string s[maxn]; 5 6 bool judge(string s1,string s2){ 7 if(s1.length()>s2.length())return 1; 8 int len=s1.length(); 9 for(int i=0;i<len;i++)10 if(s1[i]!=s2[i])11 return true;12 return false;13 }14 15 int main(){16 int n;17 while(cin>>n,n){18 bool ok=1;19 for(int i=0;i<n;i++)cin>>s[i];20 21 for(int i=0;i<n;i++)22 for(int j=i+1;j<n;j++)23 if(judge(s[i],s[j])&&judge(s[j],s[i]))24 continue;25 else {26 ok=0;break;27 }28 29 if(ok)puts("YES");30 else puts("NO");31 32 }33 return 0;34 }
b:输出4联通和8联通的联通快数，水题
1 #include<bits/stdc++.h> 2 using namespace std; 3 const int maxn=105; 4 const int dx[]={0,0,1,-1,-1,1,-1,1}; 5 const int dy[]={1,-1,0,0,1,1,-1,-1}; 6 char g[maxn][maxn]; 7 int v[maxn][maxn],n; 8 9 inline bool judge(int x,int y){10 if(x<0||x>=n||y<0||y>=n||g[x][y]==‘0‘)return true;11 return false;12 }13 14 void dfs(int x,int y,int t){15 if(v[x][y])return ;16 v[x][y]=1;17 for(int i=0;i<t;i++){18 int nx=x+dx[i];19 int ny=y+dy[i];20 if(judge(nx,ny))continue;21 dfs(nx,ny,t);22 }23 }24 25 26 int main(){27 int cas=1;28 while(~scanf("%d",&n),n){29 for(int i=0;i<n;i++)scanf("%s",g[i]);30 memset(v,0,sizeof(v));31 32 int res1=0,res2=0;33 for(int i=0;i<n;i++)for(int j=0;j<n;j++){34 if(g[i][j]==‘0‘)continue;35 if(!v[i][j])res1++;36 dfs(i,j,4);37 }38 memset(v,0,sizeof(v));39 for(int i=0;i<n;i++)for(int j=0;j<n;j++){40 if(g[i][j]==‘0‘)continue;41 if(!v[i][j])res2++;42 dfs(i,j,8);43 }44 printf("Case %d: %d %d\n",cas++,res1,res2);45 puts("");46 }47 return 0;48 }
d.排下序，水题
1 #include<bits/stdc++.h> 2 using namespace std; 3 typedef long long ll; 4 const int maxn=1e5+5; 5 int d[maxn]; 6 7 int main(){ 8 int n; 9 while(cin>>n,n){10 for(int i=0;i<n;i++)cin>>d[i];11 sort(d,d+n);12 ll res=d[n-1]-d[0];13 14 for(int i=1;i<n;i++)res+=d[i]-d[i-1];15 cout<<res<<endl;16 }17 return 0;18 }
E：n个城市都沦陷了，有两种操作0 x占领x,1 x y，输出x y的最短路
因为每个点只会被占领一次，只要用这个点来更新其他点就好
1 #include<iostream> 2 #include<cmath> 3 #include<string.h> 4 #include<stdio.h> 5 #define INT_MAX 100000 6 using namespace std; 7 int n,m,q; 8 int map[310][310],vis[310]; 9 void floyd(int k){10 int i,j;11 for(i=0;i<n;i++)12 for(j=0;j<n;j++)13 {14 if((map[i][k]!=INT_MAX) && (map[k][j]!=INT_MAX))15 if(map[i][j]>map[i][k]+map[k][j])16 map[i][j]=map[i][k]+map[k][j];17 }18 }19 void init()20 {21 int i,j;22 for(i=0;i<310;i++){23 for(j=0;j<310;j++)24 map[i][j]=INT_MAX;25 map[i][i]=0;26 }27 }28 int main()29 {30 int i,j,k,l,x,y,z,d,c=0;31 while(cin>>n>>m>>q&&(n||m||q))32 {33 init();34 memset(vis,0,sizeof(vis));35 for(int i=0;i<m;i++){36 cin>>x>>y>>z;37 if(map[x][y]>z)38 map[x][y]=z;39 }40 printf("Case %d:\n",++c);41 for(j=0;j<q;j++){42 cin>>d;43 if(!d){44 cin>>x;45 if(!vis[x]){46 vis[x]=1;47 floyd(x);48 }49 else printf("City %d is already recaptured.\n",x);50 }51 else{52 cin>>x>>y;53 if(!vis[x]||!vis[y])54 printf("City %d or %d is not available.\n",x,y);55 else if(map[x][y]==INT_MAX)56 cout<<"No such path."<<endl;57 else cout<<map[x][y]<<endl;58 }59 }60 cout<<endl;61 }62 return 0;63 }
F:模拟题，题意难读，不过好写，110行就差不多能写完
G:n个数，从中取四个数，每个数可以重复取，输出小于等于M的最大值
先把两个数和的存下来，排个序，然后双指针就Ok
1 #include<bits/stdc++.h> 2 using namespace std; 3 typedef long long ll; 4 const int maxn=1e3+5; 5 int d[maxn],c[maxn*maxn]; 6 int n,m; 7 8 int main(){ 9 int cas=1;10 while(cin>>n>>m,n){11 for(int i=0;i<n;i++)cin>>d[i];12 int cnt=0;13 for(int i=0;i<n;i++)for(int j=0;j<n;j++)14 c[cnt++]=d[i]+d[j];15 16 sort(c,c+cnt);17 18 int l=0,r=cnt-1;19 ll res=0;20 while(c[r]>m)r--;21 22 while(l<=r){23 if((ll)c[l]+c[r]>m)r--;24 else {25 res=max(res,(ll)c[l]+c[r]);26 l++;27 }28 if(res==m)break;29 }30 printf("Case %d: %lld\n\n",cas++,res);31 }32 return 0;33 }
H:输出在(x,y)右边以及下面的第一个点，具体要求看题目
n只有300，直接爆
1 #include<bits/stdc++.h> 2 using namespace std; 3 const int maxn=1005; 4 int x[maxn],y[maxn],z[maxn]; 5 6 int main(){ 7 int n,cas=1; 8 while(cin>>n,n){ 9 for(int i=0;i<n;i++)cin>>x[i]>>y[i],z[i];10 11 int nx,ny;12 printf("Case %d:\n",cas++);13 for(int i=0;i<n;i++){14 nx=ny=-1;15 for(int j=0;j<n;j++)16 if(x[j]>x[i]&&y[j]>y[i]){17 if(nx==-1)nx=x[j],ny=y[j];18 else if(x[j]<nx)nx=x[j],ny=y[j];19 else if(x[j]==nx&&y[j]<ny)ny=y[j];20 }21 printf("%d %d\n",nx,ny);22 }23 puts("");24 }25 return 0;26 }
I:上一题的加强版，可以加入一个点，删除一个点，然后查询一个点的右下方点，要求和上面一样
分析：讲道理写了个AVL插入两个元素应该没问题，迷之超时，set套pair,找到第然后二分找一下点，然后符合要求的肯定在后面，找到第一个点就好了
J:题目太长，没看
山东省第一届acm程序设计竞赛题解
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。