首页 > 代码库 > 2014CSUACM小组练习赛1

2014CSUACM小组练习赛1

2024-07-12 21:33:06   219人阅读

  就一道中文题，就先看这道，是一道迷宫题，BFS可以解答，路径输出部分正好昨天看最长公共子序列遇到到过。然后做题过程中发现好多人

都把第一题第二题做完了，这时候正好感觉D题有些代码量，就做A B，A题是水题，B题其实也是水题，一开始没看懂题，写了一大坨代码，结果

time limited!然后就沉下心去做D题，1A，继续看B题，同样还是time limited!然后时间就到了，结束重新看了一下题目才恍然大悟。

B题代码CodeForce 230A

 1 #include<stdio.h> 2 #include<string.h> 3 #include<algorithm> 4 const int maxn=1000+5; 5 int a[maxn],b[maxn],vis[maxn]; 6 int main() 7 { 8     int s,n; 9     while(scanf("%d%d",&s,&n)==2){10         for(int i=0;i<n;i++)11             scanf("%d%d",&a[i],&b[i]);12         memset(vis,0,sizeof(vis));13         for(int i=0;i<n;i++)14         for(int j=i+1;j<n;j++){15             if(a[i]>a[j]){16                 int t1=a[i],t2=b[i];17                 a[i]=a[j];18                 a[j]=t1;19                 b[i]=b[j];20                 b[j]=t2;21             }22         }23         for(int i=0;i<n;i++){24             if(s>a[i] && !vis[i]){25                 s+=b[i];26                 vis[i]=1;27             }28         }29         int flag=1;30         for(int i=0;i<n;i++)31             if(!vis[i])32             flag=0;33        if(flag)34             printf("YES\n");35         else36             printf("NO\n");37     }38     return 0;39 }

 

下面附上D题BFS代码。POJ3984

 1 #include<stdio.h> 2 #include<string.h> 3 #include<queue> 4 int maze[8][8],vis[8][8],foot[8][8]; 5 int dir[5][3]={{1,0},{0,-1},{-1,0},{0,1}}; 6 struct node{ 7     int xpos; 8     int ypos; 9     void init(int x,int y)10     {11         xpos=x;12         ypos=y;13     }14 }fa[30];15 void bfs(node source,node target)16 {17     vis[source.xpos][source.ypos]=1;18     std::queue<node>q;19     q.push(source);20     foot[0][0]=1;21     while(!q.empty()){22         node a=q.front();23         q.pop();24         for(int i=0;i<4;i++){25         int nx=a.xpos+dir[i][0];26         int ny=a.ypos+dir[i][1];27              if(nx<0 || ny<0 || nx>=5 || ny>=5)28                   continue;29              if(nx==target.xpos && ny==target.ypos){30                     node c;31                     c.xpos=nx;32                     c.ypos=ny;33                     q.push(c);34                     vis[nx][ny]=1;35                     fa[nx*5+ny]=a;36                     foot[nx][ny]=1;37                     return;38              }39              if(maze[nx][ny])40                 continue;41              if(vis[nx][ny])42                 continue;43                     node c;44                     c.xpos=nx;45                     c.ypos=ny;46                     q.push(c);47                     vis[nx][ny]=1;48                     fa[nx*5+ny]=a;49                     foot[nx][ny]=1;50         }51     }52 }53 void printfoot(int i,int j)54 {55     if(i==0 && j==0)56         return;57     if(foot[i][j]){58         node p=fa[i*5+j];59         int ni=p.xpos;60         int nj=p.ypos;61         printfoot(ni,nj);62         printf("(%d, %d)\n",i,j);63     }64 }65 int main()66 {67     while(scanf("%d",&maze[0][0])!=EOF){68         for(int i=0;i<5;i++)69         for(int j=0;j<5;j++){70             if(i==0 && j==0)71             continue;72             scanf("%d",&maze[i][j]);73         }74         memset(vis,0,sizeof(vis));75         memset(foot,0,sizeof(foot));76         node source,target;77         source.init(0,0);78         target.init(4,4);79         bfs(source,target);80         printf("(0, 0)\n");81         printfoot(4,4);82     }83     return 0;84 }


联系
我们