首页 > 代码库 > UVALive 6163(暴力枚举)
UVALive 6163(暴力枚举)
这道题我的做法就是枚举这四个数的所有排列所有运算所有计算顺序。
略有考验代码能力，不能漏掉情况，注意模块化的思想，一些功能写成函数调试的时候结构清晰好分析。
比赛时没有AC是对next_permutation()函数理解的不透，根本没有想到是没有从最小字典序开始枚举的问题。
就是next_permutation()函数是从当前顺序枚举到字典序最大的，而我开始时do里面的a数组不一定是字典序最小的，但是next_permutation()函数一定是从当前字典序往最大的枚举，所以漏掉了字典序很小的那些情况。所以我在do里面第一步加一个sort排序就AC了。
next_permutation()函数是从当前顺序一直枚举到字典序最大的（按字典序递增的顺序），没有更大的排列了就返回false，否则改了排列顺序以后返回true。
prev_permutation()函数是从当前顺序一直枚举到字典序最小的（按字典序递减的顺序），没有更小的排列了就返回false，否则改了排列顺序以后返回true。
这也是next和prev的意思，所谓“下一个”和“上一个”，就是字典序刚好比它大一点的排列和刚好比它小一点的排列。
平时学知识一知半解，比赛时就遭报应了。。。。。。
#include<iostream>#include<cstdio>#include<cstdlib>#include<cstring>#include<cmath>#include<map>#include<set>#include<vector>#include<algorithm>#include<stack>#include<queue>using namespace std;#define INF 1000000000#define eps 1e-8#define pii pair<int,int>#define LL long long intint n,a[4];char in[4];bool deal();bool cal(int i,int j,int k);int g(int x,int y,int d);int main(){ //freopen("in1.txt","r",stdin); //freopen("out.txt","w",stdout); while(scanf("%d",&n)==1&&n) { bool ans=true; for(int i=1; i<=n; i++) { scanf("%s",in); if(ans==false) continue; else { a[0]=in[0]-‘0‘; a[1]=in[1]-‘0‘; a[2]=in[2]-‘0‘; a[3]=in[3]-‘0‘; if(deal()==false)//这四个数弄不出10 { ans=false; } } } if(ans==true) printf("TRUE\n"); else printf("BUSTED\n"); } //fclose(stdin); //fclose(stdout); return 0;}bool deal(){ sort(a,a+4);//没有这句就WA了 do { for(int i=0; i<4; i++) { for(int j=0; j<4; j++) { for(int k=0; k<4; k++) { //三个for枚举所有运算符的组合 if(cal(i,j,k)) { return true; } } } } } while(next_permutation(a,a+4));//枚举四个数的所有排列 return false;}bool cal(int i,int j,int k){ int t1=g(a[0],a[1],i); int t2=g(a[1],a[2],j); int t3=g(a[2],a[3],k); //接下来枚举所有运算次序 if(g(t1,t3,j)==10)//k,i,j return 1; else if( g( g(a[0],t2,i),a[3],k)==10 )//j,i,k return 1; else if( g( g(t1,a[2],j),a[3],k)==10 )//i,j,k return 1; /*else if( g( g(a[0],a[1],i),t3,j)==10 )//i,k,j return 1;*/ else if( g( a[0],g(t2,a[3],k),i)==10 )//j,k,i return 1; else if( g( a[0],g(a[1],t3,j),i)==10 )//k,j,i return 1; else return 0;}int g(int x,int y,int d){ if(d==0) return x+y; else if(d==1) return x-y; else if(d==2) return x*y; else { if(y) return x/y; else return 0;//分母为0不能进行除法，那这种情况肯定不行，那我就看成乘以0返回。 }}
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。