周赛被虐的太惨了,加油吧!!!
http://acm.hdu.edu.cn/diy/contest_show.php?cid=18641
第一题:
题意:三维搜索,从(0,0,0)到(a-1,b-1,c-1).
思路:DFS+回溯写了很长时间,结果总超时,其实是用BFS加剪枝就可以过了。BFS写的过程中有个地方超内存了,找了老半天才发现。标记应该在没入队之前标记。开始还想用A*算法写的,感觉很麻烦,而且后来也没写出来。BFS和DFS之间还是有很大区别的,坐标范围不是很大最好用BFS,深度很大最好用DFS。
以下是AC代码:
#include<iostream> #include<cstring> #include<cstdio> #include<queue> using namespace std; struct p { int x,y,z,step; }; int map[55][55][55]; int vis[55][55][55]; int xx[]= {-1,1,0,0,0,0}; int yy[]= {0,0,-1,1,0,0}; int zz[]= {0,0,0,0,-1,1}; int tim,a,b,c,t,k; queue<p> q; bool inmap(p pp) { if(pp.x<0||pp.x>=a||pp.y<0||pp.y>=b||pp.z<0||pp.z>=c) return false; else return true; } int min(int x,int y) { return x>y?y:x; } void bfs() { p s; s.x=0,s.y=0,s.z=0,s.step=0; vis[0][0][0]=1; //map[0][0][0]=1; while(!q.empty()) q.pop(); q.push(s); p tp,np; while(!q.empty()) { tp=q.front(); q.pop(); //vis[tp.x][tp.y][tp.z]=1;//出队时才标记会使得以前重复进队 if(tp.x==(a-1)&&tp.y==(b-1)&&tp.z==(c-1)) { tim=min(tim,tp.step); continue; } for(int i=0; i<6; i++) { np.x=tp.x+xx[i],np.y=tp.y+yy[i],np.z=tp.z+zz[i]; if(inmap(np)&&!map[np.x][np.y][np.z]&&!vis[np.x][np.y][np.z]) { np.step=tp.step+1; //vis[np.x][np.y][np.z]=1;//入队之前标记 map[tp.x][tp.y][tp.z]=1; q.push(np); } } } } int main() { scanf("%d",&k); while(k--) { scanf("%d%d%d%d",&a,&b,&c,&t); for(int i=0; i<a; i++) //x for(int j=0; j<b; j++) //y for(int z=0; z<c; z++) //z { scanf("%d",&map[i][j][z]); } if(map[a-1][b-1][c-1]==1) { printf("-1\n"); continue; } if(a+b+c-3>t) { printf("-1\n"); continue; } tim=1005; memset(vis,0,sizeof(vis)); //vis[0][0][0]=1; bfs(); if(tim<=t) printf("%d\n",tim); else printf("-1\n"); } return 0; }
第二题:
题意:找一组满足条件的数,使得任意两个相邻的数的和为素数。
简单的DFS+回溯
AC代码:
#include<iostream> #include<cstdio> #include<cmath> int n; int vis[20]; int q[20]; bool prim(int ans) { for(int i=2; i<=sqrt(1.0*ans); i++) { if(ans%i==0) return 0; } return 1; } void dfs(int p,int st) { if(st==n&&prim(p+1)) { for(int i=1; i<n; ++i) { printf("%d ",q[i]); } printf("%d\n",q[n]); return ; } for(int j=2; j<=n; ++j) { if(!vis[j]&&prim(j+p)) { vis[j]=1; q[++st]=j; dfs(j,st); vis[j]=0; st--; } } } int main() { int count=1; while(scanf("%d",&n)!=EOF) { printf("Case %d:\n",count); q[1]=1; dfs(1,1); printf("\n"); count++; } return 0; }
第三题:
题意:有7种积木。每次按一定顺序输入10个积木,使得堆积成m*n的矩形。
思路:大模拟。用一个数组box【】存没列已经存在的方块数,每次dfs()满足两个条件:1从左到右,能放下。2.box【】.满足放的条件,box【i】之间存在一定的关系,横竖都要与n,m相比较。注意每种积木可能有多种放的形式。
写了两天了,最后还是没发现那里错了。
好像只有两处区别:
1.我用ans标记,比用dfs函数返回麻烦点。
2.每次在与m比较时,我只用一个比较。
别人AC的代码:
#include <cstdio> #include <cstring> #include <cstdlib> char tet[20]; //记录方块的下降次序 int box[45]; //把方块分成小格子,记录每列有多个小格子 int m, n; bool DFS( int cur ) { if ( cur == 10 ) return true; switch( tet[cur] ) { case 'I' : for ( int i = 0; i < n; i++ ) { if ( box[i] + 4 <= m ) //判断能不能竖着放 { box[i] += 4; if ( DFS( cur + 1 ) ) return true; box[i] -= 4; } if ( i + 3 < n && box[i] == box[i + 1] && box[i + 1] == box[i + 2] && box[i + 2] == box[i + 3] && box[i] + 1 <= m ) //能不能横着放 { for ( int j = i; j < i + 4; j++ ) ++box[j]; if ( DFS( cur + 1 ) ) return true; for ( int j = i; j < i + 4; j++ ) --box[j]; } } break; case 'O': for ( int i = 0; i < n; i++ ) { if ( i + 1 < n && box[i] == box[i + 1] && box[i] + 2 <= m ) { box[i] += 2; box[i + 1] += 2; if ( DFS( cur + 1 ) ) return true; box[i] -= 2; box[i + 1] -= 2; } } break; case 'L' : for ( int i = 0; i < n; i++ ) { if ( i + 1 < n && box[i] + 3 <= m && box[i] == box[i + 1] ) //正着放L { box[i] += 3; box[i + 1] += 1; if ( DFS( cur + 1 ) ) return true; box[i] -= 3; box[i + 1] -= 1; } if (i + 2 < n && box[i] + 1 == box[i + 1] && box[i + 1] == box[i + 2] && box[i] + 2 <= m && box[i + 1] + 1 <= m ) //顺时针旋转90° { box[i] += 2; box[i + 1] += 1; box[i + 2] += 1; if ( DFS( cur + 1 ) ) return true; box[i] -= 2; box[i + 1] -= 1; box[i + 2] -= 1; } if (i + 1 < n && box[i] + 1 <= m && box[i + 1] + 3 <= m && box[i + 1] + 2 == box[i] ) //顺时针旋转180° { box[i] += 1; box[i + 1] += 3; if ( DFS( cur + 1 ) ) return true; box[i] -= 1; box[i + 1] -= 3; } if (i + 2 < n && box[i] == box[i + 1] && box[i + 1] == box[i + 2] && box[i + 2] + 2 <= m ) //顺时针旋转270° { box[i] += 1; box[i + 1] += 1; box[i + 2] += 2; if ( DFS(cur + 1) ) return true; box[i] -= 1; box[i + 1] -= 1; box[i + 2] -= 2; } } break; case 'J' : for ( int i = 0; i < n; i++ ) { if (i + 1 < n && box[i] == box[i + 1] && box[i + 1] + 3 <= m ) //0 { box[i] += 1; box[i + 1] += 3; if ( DFS(cur + 1) ) return true; box[i] -= 1; box[i + 1] -= 3; } if (i + 2 < n && box[i] == box[i + 1] && box[i + 1] == box[i + 2] && box[i] + 2 <= m) //90 { box[i] += 2; box[i + 1] += 1; box[i + 2] += 1; if ( DFS( cur + 1 ) ) return true; box[i] -= 2; box[i + 1] -= 1; box[i + 2] -= 1; } if (i + 1 < n && box[i] + 2 == box[i + 1] && box[i] + 3 <= m && box[i + 1] + 1 <= m ) //180 { box[i] += 3; box[i + 1] += 1; if ( DFS( cur + 1 ) ) return true; box[i] -= 3; box[i + 1] -= 1; } if (i + 2 < n && box[i] == box[i + 1] && box[i + 2] + 1 == box[i + 1] && box[i] + 1 <= m && box[i + 2] + 2 <= m) //270 { box[i] += 1; box[i + 1] += 1; box[i + 2] += 2; if ( DFS(cur + 1) ) return true; box[i] -= 1; box[i + 1] -= 1; box[i + 2] -= 2; } } break; case 'Z' : for ( int i = 0; i < n; i++ ) { if (i + 2 < n && box[i + 2] == box[i + 1] && box[i + 1] + 1 == box[i] && box[i] + 1 <= m && box[i + 1] + 2 <= m ) //0 { box[i] += 1; box[i + 1] += 2; box[i + 2] += 1; if ( DFS( cur + 1 ) ) return true; box[i] -= 1; box[i + 1] -= 2; box[i + 2] -= 1; } if (i + 1 < n && box[i] + 1 == box[i + 1] && box[i] + 2 <= m && box[i + 1] + 2 <= m) //90 { box[i] += 2; box[i + 1] += 2; if ( DFS( cur + 1 ) ) return true; box[i] -= 2; box[i + 1] -= 2; } } break; case 'S' : for ( int i = 0; i < n; i++ ) { if (i + 2 < n && box[i] == box[i + 1] && box[i + 1] + 1 == box[i + 2] && box[i + 1] + 2 <= m && box[i + 2] + 1 <= m ) //0 { box[i] += 1; box[i + 1] += 2; box[i + 2] += 1; if ( DFS(cur + 1) ) return true; box[i] -= 1; box[i + 1] -= 2; box[i + 2] -= 1; } if (i + 1 < n && box[i + 1] + 1 == box[i] && box[i] + 2 <= m && box[i + 1] + 2 <= m ) //90 { box[i] += 2; box[i + 1] += 2; if ( DFS(cur + 1) ) return true; box[i] -= 2; box[i + 1] -= 2; } } break; case 'T' : for ( int i = 0; i < n; i++ ) { if ( i + 2 < n && box[i] == box[i + 1] && box[i + 1] == box[i + 2] && box[i + 1] + 2 <= m ) //0 { box[i] += 1; box[i + 1] += 2; box[i + 2] += 1; if ( DFS( cur + 1 ) ) return true; box[i] -= 1; box[i + 1] -= 2; box[i + 2] -= 1; } if ( i + 1 < n && box[i] + 1 == box[i + 1] && box[i] + 3 <= m ) //90 { box[i] += 3; box[i + 1] += 1; if ( DFS( cur + 1 ) ) return true; box[i] -= 3; box[i + 1] -= 1; } if ( i + 2 < n && box[i] == box[i + 2] && box[i + 1] + 1 == box[i] && box[i + 1] + 2 <= m ) //180 { box[i] += 1; box[i + 1] += 2; box[i + 2] += 1; if ( DFS( cur + 1 ) ) return true; box[i] -= 1; box[i + 1] -= 2; box[i + 2] -= 1; } if ( i + 1 < n && box[i + 1] + 1 == box[i] && box[i + 1] + 3 <= m ) //270 { box[i] += 1; box[i + 1] += 3; if ( DFS( cur + 1 ) ) return true; box[i] -= 1; box[i + 1] -= 3; } } break; } return false; } int main() { while ( scanf( "%d%d", &n, &m ), n || m ) { for ( int i = 0; i < 10; i++ ) { getchar(); tet[i] = getchar(); } memset( box, 0, sizeof(box) ); if ( DFS(0) ) puts("Yes"); else puts("No"); } return 0; }
我的代码:
#include<cstdio> #include<cstring> #include<cstdlib> int n,m,ans; char sign[20]; int box[45]; void dfs(int st) { if(st==10) { ans=1;return ; } switch(sign[st]) { case 'I': for(int i=0;i<n;i++) { //竖着放 if(box[i]+4<=m) { box[i]+=4; dfs(++st); if(ans) return ; box[i]-=4; } //横着放 if((i+3<n)&&(box[i]+1<=m)&&(box[i]==box[i+1])&&(box[i+1]==box[i+2])&&(box[i+2]==box[i+3])) { box[i]++,box[i+1]++,box[i+2]++,box[i+3]++; dfs(++st); if(ans) return ; box[i]--,box[i+1]--,box[i+2]--,box[i+3]--; } } break; case 'J'://改到这里来了 for(int i=0;i<n;i++) { //0度 if((i+2)<n&&(box[i]==box[i+1])&&(box[i+1]==box[i+2])&&(box[i]+2<=m)) { box[i]+=2,box[i+1]++,box[i+2]++; dfs(++st); if(ans) return ; box[i]-=2,box[i+1]--,box[i+2]--; } //90度 if((i+1)<n&&(box[i]+3<=m)&&(box[i]+2==box[i+1])) { box[i]+=3,box[i+1]++; dfs(++st); if(ans) return ; box[i]-=3,box[i+1]--; } //180度 if((i+2)<n&&(box[i]==box[i+1])&&(box[i+1]-1==box[i+2]&&(box[i]+1<=m))) { box[i]++,box[i+1]++,box[i+2]+=2; dfs(++st); if(ans) return ; box[i]--,box[i+1]--,box[i+2]-=2; } //270度 if((i+1)<n&&(box[i]==box[i+1])&&(box[i+1]+3<=m)) { box[i]+=1,box[i+1]+=3; dfs(++st); if(ans) return ; box[i]--,box[i+1]-=3; } } break; case 'L': for(int i=0;i<n;i++) { //0 if((i+1<n)&&(box[i]==box[i+1])&&(box[i]+3<=m)) { box[i]+=3,box[i+1]++; dfs(++st); if(ans) return ; box[i]-=3,box[i+1]--; } //90 if((i+2<n)&&(box[i]+1==box[i+1])&&(box[i+1]==box[i+2])&&(box[i]+2<=m)) { box[i]+=2,box[i+1]++,box[i+2]++; dfs(++st); if(ans) return ; box[i]-=2,box[i+1]--,box[i+2]--; } //180 if((i+1<n)&&(box[i+1]+2==box[i])&&(box[i]+1<=m)) { box[i]++,box[i+1]+=3; dfs(++st); if(ans) return ; box[i]--,box[i+1]-=3; } //270 if((i+2<n)&&(box[i]==box[i+1])&&box[i+1]==box[i+2]&&box[i+2]+2<=m) { box[i]++,box[i+1]++,box[i+2]+=2; dfs(++st); if(ans) return ; box[i]--,box[i+1]--,box[i+2]-=2; } } break; case 'O': for(int i=0;i<n;i++) { if((i+1)<n&&box[i]==box[i+1]&&box[i]+2<=m) { box[i]+=2,box[i+1]+=2; dfs(++st); if(ans) return ; box[i]-=2,box[i+1]-=2; } } break; case 'S': //0 for(int i=0;i<n;i++) { if(i+2<n&&box[i]==box[i+1]&&box[i+1]+1==box[i+2]&&box[i+1]+2<=m) { box[i]++,box[i+1]+=2,box[i+2]++; dfs(++st); if(ans) return ; box[i]--,box[i+1]-=2,box[i+2]--; } } //90 for(int i=0;i<n;i++) { if(i+1<n&&box[i+1]+1==box[i]&&box[i]+2<=m) { box[i]+=2,box[i+1]+=2; dfs(++st); if(ans) return ; box[i]-=2,box[i+1]-=2; } } break; case 'T': for(int i=0;i<n;i++) { //0 if(i+2<n&&box[i]==box[i+1]&&box[i+1]==box[i+2]&&box[i+1]+2<=m) { box[i]++,box[i+1]+=2,box[i+2]++; dfs(++st); if(ans) return ; box[i]--,box[i+1]-=2,box[i+2]--; } //90 if(i+1<n&&box[i]+1==box[i+1]&&box[i]+3<=m) { box[i]+=3,box[i+1]++; dfs(++st); if(ans) return ; box[i]-=3,box[i+1]--; } //180 if(i+2<n&&box[i]-1==box[i+1]&&box[i+1]+1==box[i+2]&&box[i]+1<=m) { box[i]++,box[i+1]+=2,box[i+2]++; dfs(++st); if(ans) return ; box[i]--,box[i+1]-=2,box[i+2]--; } //270 if(i+1<n&&box[i]-1==box[i+1]&&box[i+1]+3<=m) { box[i]++,box[i+1]+=3; dfs(++st); if(ans) return ; box[i]--,box[i+1]-=3; } } break; case 'Z': for(int i=0;i<n;i++) { //0 if(i+2<n&&box[i]-1==box[i+1]&&box[i+1]==box[i+2]&&box[i]+1<=m) { box[i]++,box[i+1]+=2,box[i+2]++; dfs(++st); if(ans) return ; box[i]--,box[i+1]-=2,box[i+2]--; } //90 if(i+1<n&&box[i]+1==box[i+1]&&box[i+1]+2<=m) { box[i]+=2,box[i+1]+=2; dfs(++st); if(ans) return ; box[i]-=2,box[i+1]-=2; } } break; } } int main() { while(scanf("%d%d",&n,&m)!=EOF) { if(m==0&&n==0) break; for(int i=0;i<10;i++) { getchar(); //scanf("%c",&sign[i]); sign[i]=getchar(); } //for(int i=0;i<10;i++) //putchar(sign[i]); memset(box,0,sizeof(box)); ans=0; dfs(0); if(ans==1) printf("Yes"); else printf("No"); } return 0; }
第四题:
题意:单源起点,终点分为两种,找最短路。
思路:最短路,n比较小,直接用三个for就OK了,貌似dijskal啥的都忘记了,看来得花时间复习下了。
AC代码:
#include<stdio.h> #define maxn 11 #define INF 0x7fffffff int p[maxn]; int road[maxn][maxn]; int n,m,s,l; int fmin(int x,int y) { return x>y?y:x; } void init() { for(int ii=0; ii<n; ii++) { for(int jj=0; jj<n; jj++) { if(ii==jj) { road[ii][jj]=0; //road[jj][ii]=0; } else { road[ii][jj]=INF; //road[jj][ii]=INF; } } } } void prim() { for(int i=0; i<n; i++) for(int j=0; j<n; j++) { for(int k=0; k<n; k++) { if(road[i][k]!=INF&&road[k][j]!=INF) { road[i][j]=fmin(road[i][j],road[i][k]+road[k][j]); } } } } int main() { while(scanf("%d",&n)!=EOF) { init(); for(int i=0; i<n; i++) { scanf("%d%d",&m,&p[i]); for(int j=0; j<m; j++) { scanf("%d%d",&s,&l); road[i][s]=l; road[s][i]=l; } } prim(); int min=INF; for(int i=0; i<n; i++) { //printf("%d\n",p[i]); if(p[i]==1&&road[0][i]!=INF) { //printf("%d\n",road[0][i]); min=fmin(road[0][i],min); } } printf("%d\n",min); } return 0; }
第五题:
题意:从一堆数中找出最多的一组数,是得任意的两个数互相不被整除。
思路:看了很多人写的,有用二分图匹配的,不过想在还不会。也有用暴力写的,其实应该早就想到暴力,因为数据不是很大。遍历一次,找出以每个数开头的与它相互乘除的数个总个数,并标记这些数,用个二维数组就行了。然后每次找最小的以某个数开头的数组,标记这些数,并且ans++。直到所有的数都被标记完。
AC代码:
#include<iostream> using namespace std; #define MAXN 1001 __int64 a[MAXN]; int map[MAXN][MAXN]; bool flag[MAXN];//标记使用 int n; int main () { int t; scanf("%d",&t); while(t--) { scanf("%d",&n); for(int i = 1;i <= n;++i) scanf("%I64d",&a[i]); memset(map,0,sizeof(map)); for(int i = 1;i <= n;++i) for(int j = 1;j <= n;++j) if (a[i] % a[j] == 0 || a[j] % a[i] == 0) { map[i][j] = 1; map[i][0]++; } int cnt = 0; for(int i = 1;i <= n;++i) flag[i] = true; while(1) { int pos = -1,minvalue = 100000; for(int i = 1;i <= n;++i) { if(map[i][0] < minvalue && flag[i]) { pos = i; minvalue = map[i][0]; } } if (pos == -1) break; cnt++; //cout<<"pos:"<<pos<<endl; flag[pos] = 0; for(int i = 1;i <= n;++i) if (map[pos][i] == 1) flag[i] = 0; } printf("%d\n",cnt); } return 0; }
第六题:
题意:找规律,模拟题。
思路:其实就是输入一个16进制的数,然后按一定规律输出,比赛时想到了,但太紧张,写的不好,就没写了。
AC代码:
#include<cstdio> #define maxn 1000 int t,c,a; int map[maxn][maxn]; void init() { for(int i=0;i<c;i++) { for(int j=0;j<5;j++) { scanf("%x",&a); for(int k=0;k<8;k++) { if(a%2==1) { map[k][6*i+j]=1; } else map[k][6*i+j]=0; a/=2; } } if(i!=(c-1)) for(int k=0;k<8;k++) map[k][5+6*i]=0; } } void output() { int flag=0; for(int i=0;i<8;i++) { for(int j=0;j<(6*c-1);j++) { if(i==7&&map[i][j]==0) { flag=1; break; } if(map[i][j]==1) printf("#"); else printf(" "); } if(flag==0) printf("\n"); } } int main() { scanf("%d",&t); for(int i=1;i<=t;i++) { scanf("%d",&c); init(); printf("Case %d:\n",i); printf("\n"); output(); printf("\n"); } return 0; }