柚子快报邀请码778899分享：山东省第一届ACM省赛
ID TitleHint
A
Phone Number
串
B
Ivan comes again!
C
Hello World!
枚举
D
Greatest Number
E
Fairy tale
F
Emergency
最短路径
G
Shopping
无
H
Clockwise
I
Balloons
bfs/dfs
J
Jerry Mouse
A.
d.判断一个串是否是另一个串的前缀
#include
#include
#include
using namespace std;
int main(){
int N;
string phNum[1005];
int i;
bool flag;
int j;
int len1,len2;
int k;
while(cin>>N){
if(N==0){
break;
}
for(i=0;i cin>>phNum[i]; } flag=false; for(i=0;i len1=phNum[i].length(); for(j=i+1;j len2=phNum[j].length(); if(len1 for(k=0;k if(phNum[i][k]!=phNum[j][k]){ break; } } if(k==len1){ flag=true; } } else{ for(k=0;k if(phNum[i][k]!=phNum[j][k]){ break; } } if(k==len2){ flag=true; } } } } if(flag){ cout<<"NO"< } else{ cout<<"YES"< } } return 0; } View Code C. d.所有给出的矩阵坐标中，求大于当前的矩阵坐标的当中最小的，没有解输出-1 -1 例.输入：31 22 32 3输出：Case 1:2 3-1 -1-1 -1 s. 最多1000个坐标，直接枚举找最小的，O(10^6) 法2. 先排序，然后从后向前找到这个数，输出下一个数即可。可是为什么wa？ c. #include #include using namespace std; struct node{ int r,c; }e[1005]; int main(){ int N; int i; int j; int ca=0; while(~scanf("%d",&N)){ if(N==0){ break; } for(i=0;i scanf("%d%d",&e[i].r,&e[i].c); } printf("Case %d:\n",++ca); for(i=0;i int r,c; r=-1; c=-1; for(j=0;j if(e[j].r>e[i].r&&e[j].c>e[i].c){ r=e[j].r; c=e[j].c; break; } } if(r==-1&&j==-1){ printf("%d %d\n",r,c); } else{ for(++j;j if(e[j].r>e[i].r&&e[j].c>e[i].c){ if(e[j].r r=e[j].r; c=e[j].c; } else if(e[j].r==r&&e[j].c c=e[j].c; } } } printf("%d %d\n",r,c); } } printf("\n"); } return 0; } View Code c2.不知道为啥wa了 #include #include #include using namespace std; struct node{ int r,c; }e[1005],e2[1005]; bool cmp(node a,node b){ if(a.r!=b.r)return a.r return a.c } int main(){ int N; int i; int j; int ca=0; while(~scanf("%d",&N)){ if(N==0){ break; } for(i=0;i scanf("%d%d",&e[i].r,&e[i].c); e2[i].r=e[i].r; e2[i].c=e[i].c; } sort(e,e+N,cmp); printf("Case %d:\n",++ca); for(i=0;i bool flag=false; for(j=N-1;j>=0;--j){ if((e2[i].r==e[j].r)&&(e2[i].c==e[j].c)){ break; } } if(j==N-1){ printf("-1 -1\n"); } else{ printf("%d %d\n",e[j+1].r,e[j+1].c); } } printf("\n"); } return 0; } View Code c2'.法2，用set来写，因为set是自动排序。同样wa #include #include #include using namespace std; set int e[1005][2]; int main(){ int N; int i; int ca=0; while(~scanf("%d",&N)){ if(N==0){ break; } for(i=0;i scanf("%d%d",&e[i][0],&e[i][1]); myset.insert(make_pair(e[i][0],e[i][1])); } printf("Case %d:\n",++ca); for(i=0;i set for(--it;it!=myset.begin();--it){ if((*it).first==e[i][0]&&(*it).second==e[i][1]){ break; } } /* 这里myset.begin()并没有判断相等，但是由于这个数一定存在， 后面都不是的话，那么这个数一定就是myset.begin()了。 */ ++it; if(it==myset.end()){ printf("-1 -1\n"); } else{ printf("%d %d\n",(*it).first,(*it).second); } } printf("\n"); } return 0; } View Code F. d.最短路径 s.多源最短路径。用单源的话求的太多，会超时。 /* 多源最短路径 floyd */ #include #include #include using namespace std; #define MAXN 305 #define typec int #define INF 0x3f3f3f3f//防止后面溢出，这个不能太大 int path[MAXN][MAXN]; int cost[MAXN][MAXN],lowcost[MAXN][MAXN]; int main(){ int N,M,Q; int x,y,z; int i; int op; bool flag[MAXN]; int j; int ca=0; int k; while(~scanf("%d%d%d",&N,&M,&Q)){ if(N==0&&M==0&&Q==0){ break; } for(i=0;i for(j=0;j lowcost[i][j]=cost[i][j]=INF; } lowcost[i][i]=cost[i][i]=0;//注意这个，, } memset(flag,false,sizeof(flag)); for(i=0;i scanf("%d%d%d",&x,&y,&z); if(z lowcost[x][y]=cost[x][y]=z; } } printf("Case %d:\n",++ca); for(i=0;i scanf("%d",&op); if(op==0){ scanf("%d",&x); if(flag[x]==true){ printf("City %d is already recaptured.\n",x); } else{ flag[x]=true; for(j=0;j for(k=0;k if(lowcost[j][x]+lowcost[x][k] lowcost[j][k]=lowcost[j][x]+lowcost[x][k]; } } } } } else{//op==1 scanf("%d%d",&x,&y); if(flag[x]==false||flag[y]==false){ printf("City %d or %d is not available.\n",x,y); } else{ if(lowcost[x][y]==INF){ printf("No such path.\n"); } else{ printf("%d\n",lowcost[x][y]); } } } } printf("\n"); } return 0; } View Code G. d.求最大值、最小值 #include #include using namespace std; int main(){ int N; int a,b; int t; int i; while(~scanf("%d",&N)){ if(N==0){ break; } scanf("%d",&t); a=b=t; for(i=1;i scanf("%d",&t); if(t a=t; } else if(t>b){ b=t; } } printf("%d\n",2*(b-a)); } return 0; } View Code I. d.求有几个连通块 s.对每个点进行bfs。 当然也可以dfs。 c.bfs #include #include #include #include using namespace std; int d[105][105]; bool vis[105][105]; int N; int act[4][2]={{-1,0}, {0,-1}, {0,1}, {1,0}}; int act2[8][2]={{-1,-1},{-1,0},{-1,1}, {0,-1}, {0,1}, {1,-1},{1,0},{1,1}}; int bfs(){ memset(vis,false,sizeof(vis)); int sum=0; int i,j; int t; int a,b; int a2,b2; int k; for(i=0;i for(j=0;j if(d[i][j]==1&&!vis[i][j]){ ++sum; queue myqueue.push(i*N+j); while(!myqueue.empty()){ t=myqueue.front(); a=t/N; b=t%N; myqueue.pop(); for(k=0;k<4;++k){ a2=a+act[k][0]; b2=b+act[k][1]; if(0<=a2&&a2 if(d[a2][b2]==1&&!vis[a2][b2]){ myqueue.push(a2*N+b2); vis[a2][b2]=true; } } } } } } } return sum; } int bfs2(){ memset(vis,false,sizeof(vis)); int sum=0; int i,j; int t; int a,b; int a2,b2; int k; for(i=0;i for(j=0;j if(d[i][j]==1&&!vis[i][j]){ ++sum; queue myqueue.push(i*N+j); while(!myqueue.empty()){ t=myqueue.front(); a=t/N; b=t%N; myqueue.pop(); for(k=0;k<8;++k){ a2=a+act2[k][0]; b2=b+act2[k][1]; if(0<=a2&&a2 if(d[a2][b2]==1&&!vis[a2][b2]){ myqueue.push(a2*N+b2); vis[a2][b2]=true; } } } } } } } return sum; } int main(){ int i,j; char str[2]; int ca=0; while(~scanf("%d",&N)){ if(N==0){ break; } for(i=0;i for(j=0;j scanf("%1s",str); d[i][j]=str[0]-'0'; } } printf("Case %d: %d %d\n",++ca,bfs(),bfs2()); printf("\n"); } return 0; } View Code c2.dfs #include #include #include using namespace std; int d[105][105]; bool vis[105][105]; int N; int act[4][2]={{-1,0}, {0,-1}, {0,1}, {1,0}}; int act2[8][2]={{-1,-1},{-1,0},{-1,1}, {0,-1}, {0,1}, {1,-1},{1,0},{1,1}}; void dfs(int a,int b){ int i; int a2,b2; for(i=0;i<4;++i){ a2=a+act[i][0]; b2=b+act[i][1]; if(0<=a2&&a2 if(d[a2][b2]==1&&!vis[a2][b2]){ vis[a2][b2]=true; dfs(a2,b2); } } } } void dfs2(int a,int b){ int i; int a2,b2; for(i=0;i<8;++i){ a2=a+act2[i][0]; b2=b+act2[i][1]; if(0<=a2&&a2 if(d[a2][b2]==1&&!vis[a2][b2]){ vis[a2][b2]=true; dfs2(a2,b2); } } } } int main(){ int i,j; char str[2]; int ca=0; int sum,sum2; while(~scanf("%d",&N)){ if(N==0){ break; } for(i=0;i for(j=0;j scanf("%1s",str); d[i][j]=str[0]-'0'; } } sum=0; memset(vis,0,sizeof(vis)); for(i=0;i for(j=0;j if(d[i][j]==1&&!vis[i][j]){ ++sum; dfs(i,j); } } } sum2=0; memset(vis,0,sizeof(vis)); for(i=0;i for(j=0;j if(d[i][j]==1&&!vis[i][j]){ ++sum2; dfs2(i,j); } } } printf("Case %d: %d %d\n",++ca,sum,sum2); printf("\n"); } return 0; } View Code 柚子快报邀请码778899分享：山东省第一届ACM省赛 相关链接
发表评论