HDU1664 BFS + 数论 + 剪枝

　　题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1664 , 一道比较蛋疼的搜索题。

　　这道题有很多坑点，一点处理不好就要TLE。

 

---

 

　　题意很简单，就是找到一个n的倍数m，要求m里包含的不同数字最少。

　　做这道题要有数论的知识：对于任意的整数n，必然存在一个由不多于两个的数来组成的一个倍数。

　　所以这里就比较好入手了，就是先搜一个数的情况，没找到的话再搜两个数的情况。

具体解法：

　　用BFS来搜索，注意要有两个剪枝：如果当前队列里的结点的字符串的长度要比已经得到的结果的最小长度要长，则退出这次搜索；只有搜到的结点的数模n的余数未出现过，该节点才能入队，不然的话就会造成重复。还有不能在结点里直接保存字符串，所以要用一个前向指针来标记，需要得到字符串的时候进行一遍递归即可。

　　用一个结构体来保存结点信息：当前结点模n的余数、前向指针、结点的字符、到该结点的字符串长度。由于数据量比较大，所以要自己手动维护一个队列。

　　还有要注意的是，用string生成字符串的时候，ans = c + ans要比ans += c慢很多。

 

#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>
#include <stack>
#include <cmath>
#include <string>
#include <string.h>
#include <algorithm>
using namespace std;
const int maxn = 65536 + 5;
bool vis[maxn];
int MinLen , n , a[5];
struct Node {
    char ch;
    int mod , len , pre;    //余数 ， 当前长度 ， 前指针
} u , v , que[maxn];        
string ans , curans;

void GetStr(int k) {        //用递归来得到字符串信息，注意这里的写法
    if(k == -1)    return;
    GetStr(que[k].pre);
    curans += que[k].ch;
}
bool cmp(string a , string b) {        //比较两个串表示的十进制的大小
    if(a.size() > b.size())        return true;
    if(a.size() == b.size() && a > b)    return true;
    return false;
}
bool bfs(int k)
{
    memset(vis , 0 , sizeof(vis));
    int head = 0 , tail = -1;    //队列的首尾指针
    for(int i = 1 ; i <= k ; i++) {
        if(a[i] != 0) {        //这里是保证第一个数字不为0
            u.pre = -1;
            u.ch = a[i] + '0';
            u.mod = a[i] % n;
            u.len = 1;
            vis[u.mod] = 1;
            que[++tail] = u;
        }
    }
    while(head <= tail) {
        u = que[head];
        if(u.len > MinLen)    break;    //这里有一个剪枝
        for(int i = 1 ; i <= k ; i++) {
            v.mod = (u.mod * 10 + a[i]) % n;
            v.ch = a[i] + '0';
            v.len = u.len + 1;
            v.pre = head;
            if(!vis[v.mod]) {        //同余判重
                que[++tail] = v;
                vis[v.mod] = 1;
                if(v.mod == 0) {    //搜到了结果
                    curans = "";
                    GetStr(tail);    //获得字符串
                    return true;
                }
            }
        }
        head++;
    }
    return false;
}
int main()
{
    while(~scanf("%d" , &n) && n)
    {
        if(n <= 11) {
            cout << n << endl;
            continue;
        }
        bool flag = false;
        MinLen = maxn;
        ans = "";
        for(int i = 1 ; i <= 9 ; i++) {
            a[1] = i;
            if(bfs(1)) {
                if(!flag || cmp(ans , curans)) {
                    flag = true;
                    ans = curans;
                    MinLen = ans.size();
                } 
            }
        }
        if(flag) {
            cout << ans << endl;
            continue;
        }
        for(int i = 0 ; i <= 9 ; i++) {
            for(int j = i + 1 ; j <= 9 ; j++) {
                a[1] = i;    a[2] = j;
                if(bfs(2)) {
                    if(!flag || cmp(ans , curans)) {
                        flag = true;
                        ans = curans;
                        MinLen = ans.size();
                    }
                }
            }
        }
        cout << ans << endl;
    }
    return 0;
}