首页 > 搜索 > BFS搜索 > HDU 1664 Different Digits-数论-[解题报告] C++
2013
12-21

HDU 1664 Different Digits-数论-[解题报告] C++

Different Digits

问题描述 :

Given a positive integer n, your task is to find a positive integer m, which is a multiple of n, and that m contains the least number of different digits when represented in decimal. For example, number 1334 contains three different digits 1, 3 and 4.

输入:

The input consists of no more than 50 test cases. Each test case has only one line, which contains a positive integer n ( 1<=n < 65536). There are no blank lines between cases. A line with a single `0′ terminates the input.

输出:

For each test case, you should output one line, which contains m. If there are several possible results, you should output the smallest one. Do not output blank lines between cases.

样例输入:

7 
15 
16 
101 
0

样例输出:

7
555
16
1111

bfs.给出一个数n,求n的最小的一个倍数,且包含尽量少的数字种类。语死早啊。。。用人话讲就是找个m来整除n,其中,m的各个位数字使用的种类应该最少,多种答案的话输出最小的m。

用dfs来枚举每次可用的数字,然后bfs通过余数判重,求得的答案中选最小的。用cmp来比较一下。

后来百度发现:对于任意的整数n,必然存在一个由不多于两种数字来组成的n的倍数。不明觉利啊,看来我的dfs没啥用了。。。

#pragma comment(linker, "/STACK:1024000000,1024000000")
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<vector>
#include<string>
#include<queue>
#include<cmath>
#include<map>
///LOOP
#define REP(i, n) for(int i = 0; i < n; i++)
#define FF(i, a, b) for(int i = a; i < b; i++)
#define FFF(i, a, b) for(int i = a; i <= b; i++)
#define FD(i, a, b) for(int i = a - 1; i >= b; i--)
#define FDD(i, a, b) for(int i = a; i >= b; i--)
///INPUT
#define RI(n) scanf("%d", &n)
#define RII(n, m) scanf("%d%d", &n, &m)
#define RIII(n, m, k) scanf("%d%d%d", &n, &m, &k)
#define RIV(n, m, k, p) scanf("%d%d%d%d", &n, &m, &k, &p)
#define RV(n, m, k, p, q) scanf("%d%d%d%d%d", &n, &m, &k, &p, &q)
#define RFI(n) scanf("%lf", &n)
#define RFII(n, m) scanf("%lf%lf", &n, &m)
#define RFIII(n, m, k) scanf("%lf%lf%lf", &n, &m, &k)
#define RFIV(n, m, k, p) scanf("%lf%lf%lf%lf", &n, &m, &k, &p)
#define RS(s) scanf("%s", s)
///OUTPUT
#define PN printf("\n")
#define PI(n) printf("%d\n", n)
#define PIS(n) printf("%d ", n)
#define PS(s) printf("%s\n", s)
#define PSS(s) printf("%s ", s)
#define PC(n) printf("Case %d: ", n)
///OTHER
#define PB(x) push_back(x)
#define CLR(a, b) memset(a, b, sizeof(a))
#define CPY(a, b) memcpy(a, b, sizeof(b))
#define display(A, n, m) {REP(i, n){REP(j, m)PIS(A[i][j]);PN;}}
#define lson l, m, rt << 1
#define rson m + 1, r, rt << 1 | 1

using namespace std;
typedef long long LL;
typedef pair<int, int> P;
const int MOD = 9901;
const int INFI = 1e9 * 2;
const LL LINFI = 1e17;
const double eps = 1e-6;
const double pi = acos(-1.0);
const int N = 66666;
const int M = 66;
const int move[8][2] = {0, 1, 0, -1, 1, 0, -1, 0, 1, 1, 1, -1, -1, 1, -1, -1};

int a[10], pre[N], val[N], a1[N], a2[N];
int na, n, n1, n2;
bool use[10];

void print(int x)
{
    if(pre[x])print(pre[x]);
    a2[n2++] = val[x];
}

void cmp()
{
    if(n1)
    {
        if(n1 < n2)return;
        else if(n1 == n2)
        {
            REP(i, n2)
            {
                if(a1[i] < a2[i])return;
                if(a1[i] == a2[i])continue;
                break;
            }
        }
    }
    n1 = n2;
    REP(i, n2)a1[i] = a2[i];
}

void bfs()
{
    int p, t;
    queue<int> q;
    CLR(pre, -1);
    REP(i, na)
    {
        if(!a[i])continue;
        t = a[i] % n;
        if(!t)
        {
            a2[0] = a[i];
            n2 = 1;
            cmp();
            return;
        }
        pre[t] = 0;
        val[t] = a[i];
        q.push(t);
    }
    while(!q.empty())
    {
        p = q.front();
        q.pop();
        REP(i, na)
        {
            t = ((p * 10) + a[i]) % n;
            if(!t)
            {
                n2 = 0;
                print(p);
                a2[n2++] = a[i];
                cmp();
                return ;
            }
            if(pre[t] == -1)
            {
                pre[t] = p;
                val[t] = a[i];
                q.push(t);
            }
        }
    }
    return ;
}

void dfs(int x)
{
    if(x == na)
    {
        bfs();
        return;
    }
    REP(i, 10)
    {
        if(use[i])continue;
        a[x] = i;
        use[i] = 1;
        dfs(x + 1);
        use[i] = 0;
    }
}

int main()
{
    //freopen("input.txt", "r", stdin);
    while(RI(n), n)
    {
        FFF(i, 1, 10)
        {
            na = i;
            n1 = 0;
            CLR(use, 0);
            dfs(0);
            if(n1)break;
        }
        REP(i, n1)printf("%d", a1[i]);
        puts("");
    }
    return 0;
}

解题报告转自:http://blog.csdn.net/dotacm/article/details/11174301


  1. 约瑟夫也用说这么长……很成熟的一个问题了,分治的方法解起来o(n)就可以了,有兴趣可以看看具体数学的第一章,关于约瑟夫问题推导出了一系列的结论,很漂亮

  2. Excellent Web-site! I required to ask if I might webpages and use a component of the net web website and use a number of factors for just about any faculty process. Please notify me through email regardless of whether that would be excellent. Many thanks