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

青旅半醒 2022-04-15 06:52 177阅读 0赞

传送门：[UVa 725 - Division][]

**目录**

代码1

代码2

代码3 （借助sprintf进行枚举，省时又省力）

--------------------

枚举所有没必要，只需枚举其中的五位就可以计算出另一部分了，如果总位数超过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 ###

### 代码3 （借助sprintf进行枚举，省时又省力） ###

**sprintf用于将格式化的数据写入字符串，头文件：\#include<stdio.h>。**

**sprintf将求的数转化成字符串，然后进行排序，和"9876543210"进行比较，从而判断所有数字都各不相同。**

#include <cstdio>
    #include <cstring>
    #include <algorithm>
    using namespace std;
    
    bool cmp(char a, char b)
    {
        return a>b;
    }
    
    char ans[11]="9876543210";
    char s[11];
    
    int main()
    {
        int n,y,tmp=-1;
        bool flag=false;
        while(~scanf("%d", &n))
        {
        	if(n==0) break;
        	
            if(tmp!=-1&&n!=tmp)	printf("\n");
    		tmp=n;
    		
            flag=false;
            for(int i=1234; i<=98765; i++)
            {
                y=n*i;
                if(y>98765)  break;
                if(i<10000)
                    sprintf(s, "%d%d%d", 0, i,y);
                else
                    sprintf(s, "%d%d", i,y);
                sort(s,s+10,cmp);
                if(strcmp(s,ans)==0)
                {
                    printf("%05d / %05d = %d\n",y,i,n);
                    flag=true;
                }
            }
            if(!flag)
                printf("There are no solutions for %d.\n", n);
        }
        return 0;
    }

代码3参考[https://www.cnblogs.com/nbalive2001/p/5417216.html][https_www.cnblogs.com_nbalive2001_p_5417216.html]

[UVa 725 - Division]: https://vjudge.net/problem/UVA-725
[https_www.cnblogs.com_nbalive2001_p_5417216.html]: https://www.cnblogs.com/nbalive2001/p/5417216.html