首页 > 搜索 > DFS搜索 > HDU 1755 A Number Puzzle-哈希表-[解题报告] C++
2013
12-23

HDU 1755 A Number Puzzle-哈希表-[解题报告] C++

A Number Puzzle

问题描述 :

Lele 最近上课的时候都很无聊,所以他发明了一个数字游戏来打发时间。

这个游戏是这样的,首先,他拿出几张纸片,分别写上0到9之间的任意数字(可重复写某个数字),然后,他叫同学随便写两个数字X和K。Lele要做的事情就是重新拼这些纸牌,组成数字 T ,并且 T + X 是 K 的正整数倍。

有时候,当纸片很多的时候,Lele经常不能在一节课之内拼出来,但是他又想知道答案,所以,他想请你帮忙写一个程序来计算答案。

输入:

本题目包含多组测试数据,请处理到文件结束。
每组数据第一行包含两个整数 N和M(0<N<9,0<M<2000),分别代表纸片的数目和询问的数目。
第二行包含N个整数分别代表纸片上写的数字,每个数字可能取0~9。
接下来有M行询问,每个询问给出两个整数X和K(0<=x<10^9,0<K<100)。

注意:在拼纸片的时候,每张纸片都必须用上,且T首位不能为0

输出:

对于每次询问,如果能够用这些纸片拼出符合答案的T,就输出结果T。如果有多个结果,就输出符合要求的最小的T。
如果不能拼出,就输出"None"。

样例输入:

4 3
1 2 3 4
5 7
33 6
12 8

样例输出:

1234
None
1324

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1755

        刚开始看到这个题的时候,看到这个8,于是想到的是8!很小才4万多,不过加上询问次数,就很不乐观了。。。。这个题有点水,可以用暴力过,这个题没有极限数据。。。也就是复杂度为O(8!*2000)。如果我们这么想的话,那么题目中给出K的范围就没有实际意义了(有时候我就喜欢看数据范围,证明我的想法是对的)。。。那么我们可以用一个HASH数组记录所有的数对K去余的数的,那么我们询问的时间复杂度就降下来了,时间复杂度可以降到O(8!*100)+O(m),那么时间复杂度和空间复杂度都可以达到要求。。。。。。我们还可以注意到T+x是K的整数倍,那么(T%k+x%k==k)(除非T==0
&& x==0)这个题不要考虑这个情况。。。。

我的代码:

#include<cstdio>
#include<cstring>
#include<algorithm>
#define N 50005
#define LL __int64

using namespace std;

LL st[N],total,h[15],n,flag[15];
LL Dp[105][105],m;

void Dfs(int x,LL num)//递归求所有的组合
{
    if(x>=n)
    {
        st[total++]=num;
        return;
    }
    int i,k=-1;
    if(num==0)k=0;
    for(i=0;i<n;i++)
    {
        if(!flag[i] && h[i]!=k)
        {
            flag[i]=1;
            Dfs(x+1,num*10+h[i]);
            flag[i]=0;
            k=h[i];
        }
    }
}

void make()
{
    int i,j,k;
    for(i=0;i<n;i++)
    {
        flag[i]=0;
        scanf("%I64d",&h[i]);
    }
    sort(h,h+n);//排序
    total=0;
    Dfs(0,0);
    memset(Dp,-1,sizeof(Dp));//初始化
    for(i=0;i<total;i++)
    {
        for(j=1;j<=100;j++)
        {
            k=st[i]%j;
            if(Dp[j][k]==-1 || Dp[j][k]>st[i])
            {
                Dp[j][k]=st[i];//预处理
            }
        }
    }
    LL x,y;
    while(m--)//询问
    {
        scanf("%I64d%I64d",&x,&y);
        if(y==1)printf("%I64d\n",Dp[1][0]);
        else
        {
            x%=y;
            x=y-x;//互补
            if(x==y)x=0;
            if(Dp[y][x]==-1)printf("None\n");
            else printf("%I64d\n",Dp[y][x]);
        }
    }
}
int main()
{
    while(scanf("%I64d%I64d",&n,&m)==2)
    {
        make();
    }
    return 0;
}

解题报告转自:http://blog.csdn.net/sujian19900703/article/details/8159489


,
  1. if(j){
    int ans=a ;
    for(int x=j-1;x>=0;x–){
    if(!a ) break;
    ans=min(ans,a );
    sum+=ans;
    }
    }
    求解释,,dp的思路是什么呢?

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

  3. Thanks for taking the time to examine this, I really feel strongly about it and love studying a lot more on this topic. If possible, as you acquire experience

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