首页 > 代码库 > ACM 暴力搜索题 题目整理
ACM 暴力搜索题 题目整理
UVa 129 Krypton Factor
注意输出格式，比较坑爹。
每次要进行处理去掉容易的串，统计困难串的个数。
#include<iostream>#include<vector>#include<cmath>#include<map>#include<algorithm>#include<cstring>#include<cstdio>#include<cstdlib>#include<string>#define INF 1000000000LL#define ll long longusing namespace std;char str[100];int cnt,K,L;bool check(int len){ int l=strlen(str); if(l==0||l==1) return false; for(int i=1; i<=len/2; ++i) { bool ok=true; for(int j=0; j<i&&ok; ++j) { if(str[len-1-j]!=str[len-1-i-j]) ok=false; } if(ok) return true; } return false;}void dfs(int pos){ if(cnt>=K) return ; else { for(int i=0; i<L; ++i) { str[pos]=‘A‘+i; str[pos+1]=0; if(!check(pos+1)) cnt++; else continue ; dfs(pos+1); if(cnt>=K) return ; } }}int main(){ while(scanf("%d%d",&K,&L)!=EOF) { if(!K&&!L) break; cnt=0; dfs(0); int L=strlen(str); for(int i=0; str[i]; ++i) { if(i&&i%4==0&&i%64) putchar(‘ ‘); putchar(str[i]); if((i+1)%64==0) putchar(‘\n‘); } if(L%64) putchar(‘\n‘); printf("%d\n",L); } return 0;}
SPOJ COMCB 1003
注意棋盘方格总数不会超过26。所以可以尝试dfs回溯寻找最优解。
怎么找字典序最小的，这个把棋盘画出来，然后指定一下每次跳的方向的顺序就行。如果第一个跳完全部棋盘的就是最优解。
这里要求输出最优解，每个位置是二维的，可以把它们压缩成一维，开一个数组，下标存第几步，内容存位置，这样就方便储存了。
实际上可行解并不多，可以打表。
View Code
HDU 4848 Wow! Such Conquering!
首先用fylod求最短路，然后搜索。时间复杂度大约是30！。肯定要剪枝。
有两个剪枝，一个是如果当前时刻有星球永远无法到达，则return，另一个是如果到该星球以后的时间花费比当前最优解要小则剪枝。这样就能过了。
#include <iostream>#include <string>#include <cstdio>#include <cstring>#include <algorithm>#define inf 100000000using namespace std;int dist[35][35],tim[35];int n;int ans;bool vis[35];void dfs(int now,int rest,int all,int sum){ if(all>=ans) return ; if(rest==0) { ans=min(ans,all); return ; } for(int i=1; i<n; ++i) if((!vis[i])&&(sum+dist[now][i]>tim[i])) return; for(int i=1; i<n; ++i) { if(!vis[i]) { int time=sum+dist[now][i]; if(time<=tim[i]) { if(ans<=all+rest*time) continue; vis[i]=true; dfs(i,rest-1,all+time,time); vis[i]=false; } } }}int main(){ while(scanf("%d",&n)!=EOF) { for(int i=0; i<n; ++i) for(int j=0; j<n; ++j) { scanf("%d",&dist[i][j]); } for(int k=0; k<n; ++k) for(int i=0; i<n; ++i) for(int j=0; j<n; ++j) dist[i][j]=min(dist[i][j],dist[i][k]+dist[k][j]); for(int i=1; i<n; ++i) { scanf("%d",&tim[i]); } ans=inf; memset(vis,0,sizeof(vis)); vis[0]=true; dfs(0,n-1,0,0); if(ans==inf) puts("-1"); else printf("%d\n",ans); } return 0;}
SGU 125 Shtirlits
给一个矩阵B，每个元素B[i][j]表示A[i][j]上下左右四周有多少个数大于自身。输出一个可能的矩阵A。
由于n<=3，完全可以暴力搜索解决。但是9^9肯定会超时的，考虑剪枝。对于每个A[i][j]枚举可能的元素，当枚举到第二行以上的时候，该元素上面的一个元素四周的元素都已经确定了，可以判断是否满足题意，不满足则剪枝。当枚举到最后一行的时候，还可以判断左边的元素是否满足题意。当所有元素都枚举完毕，要进行一次全体的判断，如果符合就是答案。
之前想到一个剪枝，以为每次枚举A[i][j]，可以从0枚举到9-B[i][j]。其实这是不对的，因为比A[i][j]大的元素可能是相同的。
#include<iostream>#include<cstdio>#include<algorithm>#include<cstring>using namespace std;int B[4][4];int A[4][4];int n;bool judge(int x,int y){ return 0<=x&&x<n&&0<=y&&y<n;}const int Move[4][2]= {{-1,0},{0,-1},{1,0},{0,1}};bool check(int x,int y){ int cnt=0; for(int i=0; i<4; ++i) { int nx=x+Move[i][0],ny=y+Move[i][1]; if(judge(nx,ny)) { if(A[x][y]<A[nx][ny]) cnt++; } } return cnt==B[x][y];}bool dfs(int cur){ if(cur==n*n) { for(int i=0;i<n;++i) for(int j=0;j<n;++j) if(!check(i,j)) return false; return true; } const int x=cur/n,y=cur%n; for(int i=0; i<=9; ++i) { A[x][y]=i; if((x>=1&&!check(x-1,y))||(x==n-1&&y>=1&&!check(x,y-1))) continue; if(dfs(cur+1)) return true; } return false;}int main(){ while(scanf("%d",&n)!=EOF) { for(int i=0; i<n; ++i) for(int j=0; j<n; ++j) scanf("%d",&B[i][j]); if(!dfs(0)) puts("NO SOLUTION"); else { for(int i=0; i<n; ++i) { for(int j=0; j<n; ++j) if(!j) printf("%d",A[i][j]); else printf(" %d",A[i][j]); printf("\n"); } } } return 0;}
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。