POJ 1465 Multiple(BFS+同余剪枝)

POJ 1465 Multiple(BFS+同余剪枝)

http://poj.org/problem?id=1465

题意:给你一个属于[0,4999]的数n和多个十进制单数字.现在要求你输出一个m,这个m是n的最小倍数,且仅有我们之前给出的数字构成.

分析:

首先我们要知道如果存在由m个数位组成且是n的最小倍数的数,那么这个数一定每一位都是指定的数位.所以我们用BFS从0开始扩展.

假设指定数位为1,2,7. 那么我们从0开始扩展可以得到,1,2,7,11,12,17,21,22,27,71,72,77,111,…等等.即按长度扩展即可,但是保证我们扩展的数字得到的每一位都只从被指定的数位中选取即可.

但是如上方法还是会有很多后续可行节点,我们需要去除明显不可行的.假设我们现在遍历到了数字a,且我们扩展了a后面所有的节点.现在我们遍历到了数字b,且b%N==a%N,那么我们应该不扩展b的所有后续节点.为什么呢?
首先a<b(因为我们从数位值小到大扩展的), 假设(b*10+i)%N==0,那么肯定也有(a*10+i)%N==0.(a与b同余,所以这样.仔细想想).所以如果a的一级子孙节点不行的话,b的一级子孙节点也不行.a的x级子孙节点不行的话,b的x级子孙节点也不行.(想想是不是)也就是说a的每一个特定的子孙%N所产生的余数与 b的每一个特定的子孙%N产生的余数一一对应且相同.

所以我用flag[x]=true表示对N求余==x的数已经产生了,以后如果还有这种数生成,直接放弃即可.

还有一个需要注意的点是,我们如何表示BFS扩展的每个状态?由于数可能上千位,如果我们每个节点保存int [1000]肯定不行.我们用下面的方式来:

struct Node

{

int digit;//当前状态的个位值

int r;//当前状态值%N的余数

int pre;//当前状态的个位值的连接指针,用来找到所有当前状态的位

}Q[maxn];

这样就可以极大的节省空间.具体代码体会.

注意原题中的digit特指单位数字,如果是多位数字的话.a应该*100或1000 再加上digit.这样就有点不明确题意了.

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=5000+50;
int n,m;
int digit[10];
bool flag[maxn];
struct Node
{
    int digit;
    int r;
    int pre;
}Q[maxn];
int BFS()
{
    memset(flag,0,sizeof(flag));
    int front=0,tail=1;
    Q[front].digit=0;
    Q[front].r=0;
    Q[front].pre=-1;
    while(front<tail)
    {
        Node node=Q[front];
        int r=node.r;                   //老余数
        for(int i=0;i<m;i++)
        {
            int nr=(r*10+digit[i])%n;   //新余数
            if(!flag[nr] && (node.pre!=-1 || digit[i]!=0))//错误,忘写了后面这段,我们要保证后继不能生成0
            {
                flag[nr]=true;
                node.r=nr;
                node.digit=digit[i];
                node.pre=front;
                Q[tail++]=node;
                if(nr==0) return tail-1;
            }
        }
        front++;
    }
    return -1;
}
void print(int ans)
{
    if(ans>0)
    {
        print(Q[ans].pre);
        printf("%d",Q[ans].digit);
    }
}
int main()
{
    while(scanf("%d",&n)==1)
    {
        scanf("%d",&m);
        for(int i=0;i<m;i++) scanf("%d",&digit[i]);
        sort(digit,digit+m);                        //错误,忘写这句了
        if(n==0){printf("0\n"); continue;}
        int ans=BFS();
        if(ans==-1) printf("0\n");
        else {print(ans); puts("");}
    }
    return 0;
}