Time Limit: 40000/20000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others) Total Submission(s): 3407 Accepted Submission(s): 825
题意转自:http://blog.csdn.net/yang_7_46/article/details/12356587
题意:0-9这十个数字里面的若干个数字组合出一个数,使这个数是N的倍数,求最小的这个这样的数,不存在的话输出-1。
按照数的位数BFS,从小向大枚举就可以保证构造出来的数是递增的,如果不加判断就直接搜索的话,复杂度非常高。因此需要剪枝。
优化方法:如果一个数%N==0,那么这个数就是N的倍数。在没有找到的前提下,如果A%N==B%N,而且A<B,那么其实我们就可以取A而不取B,因为如果在A末尾增加C可以使得AC%N==0,那么BC%N也等于0,易得:如果A和B追加数之后%N==0,那么最优条件下追加的数肯定相同。
因此我们只需要维护组合出来的数%N的值即可,如果在搜索的途中出现了相同的%N值,就可以直接忽略了,因为肯定没有前面的优秀。
#include<iostream> #include<cstring> #include<cstdlib> #include<cstdio> #include<algorithm> #include<cmath> #include<queue> #include<map> #include<string> //#include<pair> #define N 10005 #define M 10005 #define mod 10000007 //#define p 10000007 #define mod2 100000000 #define ll long long #define LL long long #define maxi(a,b) (a)>(b)? (a) : (b) #define mini(a,b) (a)<(b)? (a) : (b) using namespace std; int n,ans; int m; int vis[15]; int pre[N]; int val[N]; void ini() { int x; ans=-1; memset(vis,0,sizeof(vis)); memset(pre,-1,sizeof(pre)); while(m--){ scanf("%d",&x); vis[x]=1; } } void out(int x) { if(pre[x]){ out(pre[x]); } printf("%d",val[x]); } void solve() { int i; queue<int> q; for(i=1;i<=9;i++){ if(vis[i]==1) continue; if(i>=n && i%n==0){ printf("%d\n",i); return; } if(pre[i%n]!=-1) continue; pre[i%n]=0; val[i%n]=i; q.push(i); } while(q.size()>=1) { int te=q.front(); int nx; q.pop(); for(i=0;i<=9;i++){ if(vis[i]==1) continue; nx=(te*10+i)%n; if(nx%n==0){ out(te); printf("%d\n",i); return; } if(pre[nx]!=-1) continue; pre[nx]=te; val[nx]=i; q.push(nx); } } printf("-1\n"); return; } int main() { int cnt=1; // freopen("data.in","r",stdin); //freopen("data.out","w",stdout); // scanf("%d",&T); // for(int ccnt=1;ccnt<=T;ccnt++) // while(T--) while(scanf("%d%d",&n,&m)!=EOF) { //if(n==0 && k==0 ) break; //printf("Case %d: ",ccnt); printf("Case %d: ",cnt); ini(); solve(); cnt++; // out(); } return 0; }
HDU 4474 Yet Another Multiple Problem【2012成都regional K题】 【BFS+一个判断技巧】
原文:http://www.cnblogs.com/njczy2010/p/4008590.html