（简单枚举）UVa 725 - Division （小紫P182）

传送门：UVa 725 - Division

目录

代码1

代码2 

---

枚举所有没必要，只需枚举其中的五位就可以计算出另一部分了，如果总位数超过10位，就可以终止枚举了。

我的第一个代码是枚举每一位上的数从0-9逐一枚举（其中涉及到标记的回溯），第二个代码直接从组成的最小数到最大数开始枚举。最后只需判断是否所有数字都不相同。

显然第二个代码显然效率更高。

代码1

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
typedef long long ll;

int vis[10];

int main(){
	int n,a1,b1,c1,d1,e1,tmp=-1;
	while(~scanf("%d",&n)){
		if(n==0) break;
		
		if(tmp!=-1&&n!=tmp)	printf("\n");
		tmp=n;
		
		ll x,y;
		bool flag=false;
		memset(vis,0,sizeof(vis));
		for(int a=0;a<10;a++){
			vis[a]=1;
			for(int b=0;b<10;b++){
				if(vis[b]==1) continue;
				vis[b]=1;
				for(int c=0;c<10;c++){
					if(vis[c]==1) continue;
					vis[c]=1;
					for(int d=0;d<10;d++){
						if(vis[d]==1) continue;
						vis[d]=1;
						for(int e=0;e<10;e++){
							if(vis[e]==1) continue;
							vis[e]=1;
							y=e+d*10+c*100+b*1000+a*10000;
							x=y*n;
							if(x>=100000){
								vis[e]=0;
								break;    //continue;
							}else{
								a1=x/10000;
								b1=(x%10000)/1000;
								c1=(x%1000)/100;
								d1=(x%100)/10;
								e1=x%10;
								if(vis[a1]==1){
									vis[e]=0;
									continue;
								}else vis[a1]=1;
								
								if(vis[b1]==1){
									vis[e]=0;
									vis[a1]=0;
									continue;
								}else vis[b1]=1;
								
								if(vis[c1]==1){
									vis[e]=0;
									vis[a1]=0;
									vis[b1]=0;
									continue;
								}else vis[c1]=1;
								
								if(vis[d1]==1){
									vis[e]=0;
									vis[a1]=0;
									vis[b1]=0;
									vis[c1]=0;
									continue;
								}else vis[d1]=1;
								
								if(vis[e1]==1){
									vis[e]=0;
									vis[a1]=0;
									vis[b1]=0;
									vis[c1]=0;
									vis[d1]=0;
									continue;
								}else vis[e1]=1;
								
								flag=true;
								printf("%05ld / %05ld = %d\n",x,y,n);
							
								vis[a1]=0;
								vis[b1]=0;
								vis[c1]=0;
								vis[d1]=0;
								vis[e1]=0;
							}
							vis[e]=0;
						}
						vis[d]=0;
					}
					vis[c]=0;
				}
				vis[b]=0;
			}
			vis[a]=0;
		}
		if(!flag) printf("There are no solutions for %d.\n",n);
		
	}
	return 0;
}

代码2 

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
typedef long long ll;

int vis[10];

int main(){
	int n,a1,b1,c1,d1,e1,tmp=-1;
	while(~scanf("%d",&n)){
		if(n==0) break;
		
		if(tmp!=-1&&n!=tmp)	printf("\n");
		tmp=n;
		
		ll x,y;
		bool flag=false;
		
		for(int i=1234;i<=98765;i++){
			y=i;
			x=y*n;
			if(x>98765) continue;
			memset(vis,0,sizeof(vis));
			vis[y/10000]=1;
			if(vis[(y%10000)/1000]==1) continue;
			vis[(y%10000)/1000]=1;
			if(vis[(y%1000)/100]==1) continue;
			vis[(y%1000)/100]=1;
			if(vis[(y%100)/10]==1) continue;
			vis[(y%100)/10]=1;
			if(vis[y%10]==1) continue;
			vis[y%10]=1;
			if(vis[x/10000]==1) continue;
			vis[x/10000]=1;
			if(vis[(x%10000)/1000]==1) continue;
			vis[(x%10000)/1000]=1;
			if(vis[(x%1000)/100]==1) continue;
			vis[(x%1000)/100]=1;
			if(vis[(x%100)/10]==1) continue;
			vis[(x%100)/10]=1;
			if(vis[x%10]==1) continue;
			vis[x%10]=1;
			flag=true;
			printf("%05ld / %05ld = %d\n",x,y,n);
		}
			
		if(!flag) printf("There are no solutions for %d.\n",n);
		
	}
	return 0;
}