ID | Title | Hint |
---|---|---|
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<iostream>
#include<stdio.h>
#include<string>
using namespace std; int main(){ int N;
string phNum[];
int i;
bool flag;
int j;
int len1,len2;
int k; while(cin>>N){
if(N==){
break;
} for(i=;i<N;++i){
cin>>phNum[i];
} flag=false;
for(i=;i<N&&(flag==false);++i){
len1=phNum[i].length();
for(j=i+;j<N&&(flag==false);++j){
len2=phNum[j].length(); if(len1<len2){
for(k=;k<len1;++k){
if(phNum[i][k]!=phNum[j][k]){
break;
}
}
if(k==len1){
flag=true;
}
}
else{
for(k=;k<len2;++k){
if(phNum[i][k]!=phNum[j][k]){
break;
}
}
if(k==len2){
flag=true;
}
} }
} if(flag){
cout<<"NO"<<endl;
}
else{
cout<<"YES"<<endl;
} } return ;
}
C.
d.所有给出的矩阵坐标中,求大于当前的矩阵坐标的当中最小的,没有解输出-1 -1
例.
输入:
3
1 2
2 3
2 3
输出:
Case 1:
2 3
-1 -1
-1 -1
s.
最多1000个坐标,直接枚举找最小的,O(10^6)
法2.
先排序,然后从后向前找到这个数,输出下一个数即可。可是为什么wa?
c.
#include<iostream>
#include<stdio.h>
using namespace std; struct node{
int r,c;
}e[]; int main(){ int N;
int i;
int j;
int ca=; while(~scanf("%d",&N)){
if(N==){
break;
}
for(i=;i<N;++i){
scanf("%d%d",&e[i].r,&e[i].c);
}
printf("Case %d:\n",++ca);
for(i=;i<N;++i){
int r,c;
r=-;
c=-;
for(j=;j<N;++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==-&&j==-){
printf("%d %d\n",r,c);
}
else{
for(++j;j<N;++j){
if(e[j].r>e[i].r&&e[j].c>e[i].c){
if(e[j].r<r){
r=e[j].r;
c=e[j].c;
}
else if(e[j].r==r&&e[j].c<c){
c=e[j].c;
}
}
}
printf("%d %d\n",r,c);
}
} printf("\n");
} return ;
}
c2.不知道为啥wa了
#include<iostream>
#include<stdio.h>
#include<algorithm>
using namespace std; struct node{
int r,c;
}e[],e2[]; bool cmp(node a,node b){
if(a.r!=b.r)return a.r<b.r;//r升
return a.c<b.c;//c升
} int main(){
int N;
int i;
int j;
int ca=; while(~scanf("%d",&N)){ if(N==){
break;
}
for(i=;i<N;++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=;i<N;++i){
bool flag=false;
for(j=N-;j>=;--j){
if((e2[i].r==e[j].r)&&(e2[i].c==e[j].c)){
break;
}
}
if(j==N-){
printf("-1 -1\n");
}
else{
printf("%d %d\n",e[j+].r,e[j+].c);
}
} printf("\n"); } return ;
}
c2'.法2,用set来写,因为set是自动排序。同样wa
#include<iostream>
#include<stdio.h>
#include<set>
using namespace std; set<pair<int,int> > myset;
int e[][]; int main(){
int N;
int i;
int ca=; while(~scanf("%d",&N)){
if(N==){
break;
}
for(i=;i<N;++i){
scanf("%d%d",&e[i][],&e[i][]);
myset.insert(make_pair(e[i][],e[i][]));
} printf("Case %d:\n",++ca);
for(i=;i<N;++i){
set<pair<int,int> >::iterator it=myset.end(); for(--it;it!=myset.begin();--it){
if((*it).first==e[i][]&&(*it).second==e[i][]){
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 ;
}
F.
d.最短路径
s.多源最短路径。用单源的话求的太多,会超时。
/*
多源最短路径
floyd
*/
#include<iostream>
#include<stdio.h>
#include<string.h>
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=;
int k; while(~scanf("%d%d%d",&N,&M,&Q)){
if(N==&&M==&&Q==){
break;
}
for(i=;i<N;++i){
for(j=;j<N;++j){
lowcost[i][j]=cost[i][j]=INF;
}
lowcost[i][i]=cost[i][i]=;//注意这个,,
}
memset(flag,false,sizeof(flag)); for(i=;i<M;++i){
scanf("%d%d%d",&x,&y,&z);
if(z<cost[x][y]){//注意这个。。
lowcost[x][y]=cost[x][y]=z;
}
} printf("Case %d:\n",++ca);
for(i=;i<Q;++i){
scanf("%d",&op); if(op==){
scanf("%d",&x); if(flag[x]==true){
printf("City %d is already recaptured.\n",x);
}
else{
flag[x]=true;
for(j=;j<N;++j){
for(k=;k<N;++k){
if(lowcost[j][x]+lowcost[x][k]<lowcost[j][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 ;
}
G.
d.求最大值、最小值
#include<iostream>
#include<stdio.h>
using namespace std; int main(){ int N;
int a,b;
int t;
int i; while(~scanf("%d",&N)){
if(N==){
break;
} scanf("%d",&t);
a=b=t;
for(i=;i<N;++i){
scanf("%d",&t);
if(t<a){
a=t;
}
else if(t>b){
b=t;
}
} printf("%d\n",*(b-a));
} return ;
}
I.
d.求有几个连通块
s.对每个点进行bfs。
当然也可以dfs。
c.bfs
#include<iostream>
#include<stdio.h>
#include<queue>
#include<string.h>
using namespace std; int d[][];
bool vis[][];
int N;
int act[][]={{-,},
{,-}, {,},
{,}};
int act2[][]={{-,-},{-,},{-,},
{,-}, {,},
{,-},{,},{,}}; int bfs(){
memset(vis,false,sizeof(vis));
int sum=;
int i,j;
int t;
int a,b;
int a2,b2;
int k; for(i=;i<N;++i){
for(j=;j<N;++j){
if(d[i][j]==&&!vis[i][j]){
++sum;
queue<int> myqueue;
myqueue.push(i*N+j); while(!myqueue.empty()){
t=myqueue.front();
a=t/N;
b=t%N;
myqueue.pop(); for(k=;k<;++k){
a2=a+act[k][];
b2=b+act[k][];
if(<=a2&&a2<N && <=b2&&b2<N){
if(d[a2][b2]==&&!vis[a2][b2]){
myqueue.push(a2*N+b2);
vis[a2][b2]=true;
}
}
} } }
}
} return sum;
} int bfs2(){
memset(vis,false,sizeof(vis));
int sum=;
int i,j;
int t;
int a,b;
int a2,b2;
int k; for(i=;i<N;++i){
for(j=;j<N;++j){
if(d[i][j]==&&!vis[i][j]){
++sum;
queue<int> myqueue;
myqueue.push(i*N+j); while(!myqueue.empty()){
t=myqueue.front();
a=t/N;
b=t%N;
myqueue.pop(); for(k=;k<;++k){
a2=a+act2[k][];
b2=b+act2[k][];
if(<=a2&&a2<N && <=b2&&b2<N){
if(d[a2][b2]==&&!vis[a2][b2]){
myqueue.push(a2*N+b2);
vis[a2][b2]=true;
}
}
} } }
}
} return sum;
} int main(){
int i,j;
char str[];
int ca=; while(~scanf("%d",&N)){ if(N==){
break;
} for(i=;i<N;++i){
for(j=;j<N;++j){
scanf("%1s",str);
d[i][j]=str[]-'';
}
} printf("Case %d: %d %d\n",++ca,bfs(),bfs2());
printf("\n");
} return ;
}
c2.dfs
#include<iostream>
#include<stdio.h>
#include<string.h>
using namespace std; int d[][];
bool vis[][];
int N;
int act[][]={{-,},
{,-}, {,},
{,}};
int act2[][]={{-,-},{-,},{-,},
{,-}, {,},
{,-},{,},{,}}; void dfs(int a,int b){ int i;
int a2,b2; for(i=;i<;++i){
a2=a+act[i][];
b2=b+act[i][];
if(<=a2&&a2<N && <=b2&&b2<=N){
if(d[a2][b2]==&&!vis[a2][b2]){
vis[a2][b2]=true;
dfs(a2,b2);
}
}
} } void dfs2(int a,int b){ int i;
int a2,b2; for(i=;i<;++i){
a2=a+act2[i][];
b2=b+act2[i][];
if(<=a2&&a2<N && <=b2&&b2<=N){
if(d[a2][b2]==&&!vis[a2][b2]){
vis[a2][b2]=true;
dfs2(a2,b2);
}
}
} } int main(){
int i,j;
char str[];
int ca=;
int sum,sum2; while(~scanf("%d",&N)){ if(N==){
break;
} for(i=;i<N;++i){
for(j=;j<N;++j){
scanf("%1s",str);
d[i][j]=str[]-'';
}
} sum=;
memset(vis,,sizeof(vis));
for(i=;i<N;++i){
for(j=;j<N;++j){
if(d[i][j]==&&!vis[i][j]){
++sum;
dfs(i,j);
}
}
} sum2=;
memset(vis,,sizeof(vis));
for(i=;i<N;++i){
for(j=;j<N;++j){
if(d[i][j]==&&!vis[i][j]){
++sum2;
dfs2(i,j);
}
}
} printf("Case %d: %d %d\n",++ca,sum,sum2);
printf("\n");
} return ;
}