首页 > 代码库 > HDU 4474 Yet Another Multiple Problem【2012成都regional K题】 【BFS+一个判断技巧】
HDU 4474 Yet Another Multiple Problem【2012成都regional K题】 【BFS+一个判断技巧】
Yet Another Multiple Problem
Time Limit: 40000/20000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others) Total Submission(s): 3407 Accepted Submission(s): 825
Problem Description
There are tons of problems about integer multiples. Despite the fact that the topic is not original, the content is highly challenging. That’s why we call it “Yet Another Multiple Problem”. In this problem, you’re asked to solve the following question: Given a positive integer n and m decimal digits, what is the minimal positive multiple of n whose decimal notation does not contain any of the given digits?
Input
There are several test cases. For each test case, there are two lines. The first line contains two integers n and m (1 ≤ n ≤ 104). The second line contains m decimal digits separated by spaces. Input is terminated by EOF.
Output
For each test case, output one line “Case X: Y” where X is the test case number (starting from 1) while Y is the minimal multiple satisfying the above-mentioned conditions or “-1” (without quotation marks) in case there does not exist such a multiple.
Sample Input
2345 3 7 8 9 100 1 0
Sample Output
Case 1: 2345 Case 2: -1
Source
2012 Asia Chengdu Regional Contest
Recommend
liuyiding
题意转自：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+一个判断技巧】
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。