hdu1226

 hdu1226 ：點選打開題目連結

本題目由于題目意思，容易得知是一道廣搜的題目。

首先。 我們需要知道 ，大數取模，比如 如何判斷1234567 對15 取模的數為多少？答案是7，但是如果他是大數怎麼辦，

 假設num數組存一個大數；左邊為高位，右邊為低位

int temp=0;

for(int i=最高位；i<=個位；i++)

temp=（temp * 某進制+num[i]）%N；

return temp；   //  最終的temp就是bignumber  mod N 的值。

如果該餘數出現過就沒必要再次進隊列了，因為此次模一樣代表着下次的模也一樣當這個數的模為0，那麼前面的數模早已經為0，是以，後者沒必要進隊列。

  .12

#include<iostream>
#include<stdio.h>
#include<algorithm>
#include<vector>
#include<string>
#include<string.h>
#include<queue>


using namespace std;
const int INF=~(1<<31);
const int MM=1005;

int N,C,M;
bool digit[18],vis[5005];

int mod(string& a)
{
    int temp=0;
    for(int i=0; i<a.size(); i++)
    {
        temp=(temp*C+(int)a[i])%N;
    }
    return temp;
}
void print(string& a)
{
    for(int i=0; i<a.size(); i++)
    {
        printf("%X",(int)a[i]);
    }
    cout<<endl;
}
bool bfs()
{
    queue<string>q;
    string a,b;
    for(int i=1; i<=15; i++)
    {
        if(digit[i])
        {
            a=(char)i;
            if(mod(a)==0)
            {
                print(a);
                return false;
            }
            q.push(a);
        }
    }
    while(!q.empty())
    {
        a=q.front();
        q.pop();
        for(int i=0; i<=15; i++)
        {
            if(digit[i]&&a.size()+1<=500)
            {
                b=a+(char)i;
                int mood=mod(b);
                if(mood==0)
                {
                    print(b);
                    return false;
                }
                else
                {
                    if(vis[mood]==0)
                    {
                        vis[mood]=1;
                        q.push(b);
                    }
                }
            }
        }
    }
    return true;
}
int main(void)
{
    int ncase;
    scanf("%d",&ncase);
    while(ncase--)
    {
        memset(digit,0,sizeof(digit));
        memset(vis,0,sizeof(vis));
        scanf("%d%d%d",&N,&C,&M);
        for(int i=0; i<M; i++)
        {
            int val;
            scanf("%x",&val);
            digit[val]=true;
        }
        if(N==0)
        {
            if(digit[0]) cout<<"0"<<endl;
            else cout<<"give me the bomb please"<<endl;
            continue;
        }
        if(bfs()) cout<<"give me the bomb please"<<endl;
    }
    return 0;
}
           

轉載于:https://www.cnblogs.com/coded-ream/p/7207975.html