周赛题解
1 #include<stdio.h> 2 #include<string.h> 3 char m[210],s[210]; 4 int p[210],len; 5 void fn(){ 6 int i=0,j=-1; 7 p[0]=-1; 8 while(i<len){ 9 if(j==-1||s[i]==s[j]){ 10 i++;j++; 11 p[i]=j; 12 } 13 else j=p[j]; 14 } 15 } 16 int main(){ 17 while(~scanf("%s",m)){ 18 int i=0,j,k; 19 while(m[i]!='.')i++; 20 for(j=i+1,k=0;m[j];j++,k++){ 21 s[k]=m[j]; 22 } 23 s[k]='/0'; 24 //printf("%s/n",s); 25 len=strlen(s); 26 fn(); 27 //for(i=0;i<len;i++)printf("%d ",p[i]);puts(""); 28 printf("%d ",len-p[len]); 29 for(j=p[len];j<len;j++)printf("%c",s[j]); 30 printf(" %d/n",len/(len-p[len])); 31 } 32 return 0; 33 }View Code
问题 B: MZY寻宝
时间限制: 1 Sec内存限制: 128 MB
提交: 157
解决: 49
[提交][状态][讨论版]
题目描述
贪心的MZY去一个迷宫寻宝。已知：若MZY在位置(x, y)，他下一次只能移动到(x-1, y)、(x+1, y)、(x, y-1)、(x, y+1)四个位置中的任一个(前提不能越界)。毕竟他不是我，我可以直接飞到宝物那里去。由于MZY比较笨拙，他移动一步需要1分钟。请你帮他算出找到宝物所需要花费的最少时间。
迷宫是一个N*M的地图，图中只有四个数字。
0：此处是空的，可以走
1：此处有障碍，不可以走
2：MZY起点
3：宝物位置（只有一个宝物）
题目保证CZY至少有一条路可以到达宝物位置。
输入
输入数据有多组。
每组以两个整数N和M开始，分别表示迷宫的行数和列数，接下来N行每行有M个数。（1 <= N, M <= 10）
输出
输出MZY找到宝物的最少需要花费的时间。（以秒为单位）
样例输入
2 2 0 2 1 3
样例输出
60
题解：错了12次终于交对了，尝试了各种方法，刚开始广搜，wa然后再用深搜还是wa换了种深搜写法不用数组了，然后就一直运行错误，跟魔王那题一样老是运行错误
都无奈了，然后又用广搜，换了种写法，用优先队列重新写也不管超内存了，然后就过了。。。曲折淋漓啊； dfs代码：
1 #include<stdio.h> 2 #define MIN(x,y) x<y?x:y 3 int map[15][15]; 4 int nx,ny,minstep,N,M,sx,sy; 5 void dfs(int x,int y,int step){ 6 if(x<0||y<0||x>=N||y>=M||map[x][y]==1)return; 7 if(step>minstep)return; 8 if(map[x][y]==3){ 9 minstep=MIN(minstep,step); 10 return; 11 } 12 map[x][y]==1; 13 dfs(x+1,y,step+1); 14 dfs(x-1,y,step+1); 15 dfs(x,y+1,step+1); 16 dfs(x+1,y-1,step+1); 17 map[x][y]=0; 18 return; 19 } 20 int main(){ 21 while(~scanf("%d%d",&N,&M)){minstep=0xfffffff; 22 for(int i=0;i<N;i++){ 23 for(int j=0;j<M;j++){ 24 scanf("%d",&map[i][j]); 25 if(map[i][j]==2)sx=i,sy=j; 26 } 27 } 28 dfs(sx,sy,0); 29 printf("%d/n",minstep*60); 30 } 31 return 0; 32 }View Code
bfs代码：
1 #include<stdio.h> 2 #include<string.h> 3 #include<queue> 4 using namespace std; 5 struct Node{ 6 int nx,ny; 7 int step; 8 friend bool operator < (Node a,Node b){ 9 return a.step>b.step; 10 } 11 }; 12 Node a,b; 13 int map[11][11],N,M; 14 int visit[11][11]; 15 int disx[4]={0,0,1,-1}; 16 int disy[4]={1,-1,0,0}; 17 int st,sx,sy,flot; 18 void bfs(){int t; 19 priority_queue<Node>dl; 20 a.nx=sx;a.ny=sy;a.step=0; 21 dl.push(a); 22 visit[sx][sy]=1; 23 while(!dl.empty()){ 24 a=dl.top(); 25 dl.pop(); 26 if(map[a.nx][a.ny]==3){ 27 st=a.step; 28 return; 29 } 30 visit[a.nx][a.ny]=1; 31 for(int i=0;i<4;i++){ 32 b.nx=a.nx+disx[i];b.ny=a.ny+disy[i];b.step=a.step+1; 33 if(b.nx<0||b.ny<0||b.nx>=N||b.ny>=M||visit[b.nx][b.ny])continue; 34 if(map[b.nx][b.ny]==1)continue; 35 if(map[b.nx][b.ny]==0||map[b.nx][b.ny]==3){ 36 dl.push(b); 37 } 38 } 39 } 40 } 41 int main(){int x,y; 42 while(~scanf("%d%d",&N,&M)){st=0; 43 memset(map,0,sizeof(map)); 44 memset(visit,0,sizeof(visit)); 45 for(x=0;x<N;x++)for(y=0;y<M;y++){ 46 scanf("%d",&map[x][y]); 47 if(map[x][y]==2)sx=x,sy=y; 48 } 49 bfs(); 50 printf("%d/n",st*60); 51 } 52 return 0; 53 }View Code
问题 C: CZY的组合数烦恼
时间限制: 3 Sec内存限制: 128 MB
提交: 46
解决: 21
[提交][状态][讨论版]
题目描述
czy最近对组合数产生了浓厚的兴趣，一天他心血来潮，想排n个数字，但是很快他发现种类太多了，于是他决定从中随机找出m个数排，但还是太多了，所以他想请聪明的你写个程序帮助他找到所有种类的排列
输入
输入包括多组测试数据，每组包括一行整数n（1<=n<10）,m(1<=m<=n)，空格间隔
输出
按特定顺序输出所有组合。特定顺序：每一个组合中的值从大到小排列，组合之间按逆字典序排列。
样例输入
样例输出
543 542 541 532 531 521 432 431 421 321
题解：不多说南阳组合数；
正文到此结束
热门推荐
相关文章
Loading...
![[HBLOG]公众号](http://www.liuhaihua.cn/img/qrcode_gzh.jpg)
