HDU 1226(bfs,大数求余)

清疚 2022-09-20 11:28 156阅读 0赞

题意：如题。。

这道题注意如何求余，如何剪枝。

#include <stdio.h>
    #include <string.h>
    #include <algorithm>
    #include <queue>
    using namespace std;
    
    int num[20],vis[5005];
    int n,c,m;
    
    struct node
    {
        int s[505];//将每一位的字符压入此数组
        int len;
    };
    
    int print(node a)//输出函数
    {
        int i;
        for(i = 0; i<a.len; i++)
        {
            if(a.s[i]<=9)
                printf("%d",a.s[i]);
            else
                printf("%c",a.s[i]+'A'-10);
        }
        printf("\n");
        return 1;
    }
    
    int mod(node a)//由于数字大，采用这种大数取模方式
    {
        int i,tem = 0;
        for(i = 0; i<a.len; i++)
        {
            tem = (tem*c+a.s[i])%n;//由于是n进制，tem在前面的基础上乘以进制数c在加上下一位，如果能整除n，那必定是n的倍数，则成立
        }
        return tem;
    }
    
    int BFS()
    {
        memset(vis,0,sizeof(vis));
        node a;
        a.len = 0;
        queue<node> Q;
        int i,r;
        for(i = 1; i<16; i++)//由于第一位不能为0，所以从1开始
        {
            if(num[i])//这个数是给出的样例
            {
                a.s[0] = i;//压入数组
                a.len = 1;//长度变化
                r = mod(a);
                if(!r)//模为0，则肯定是n的倍数，输出
                {
                    print(a);
                    return 1;
                }
                else
                {
                    if(!vis[r])//余数不能与之前出现过的余数相同，因为前面出现过的序列，肯定包含同样余数却在后面出现的序列
                    {
                        vis[r] = 1;//标记该余数已被访问
                        Q.push(a);
                    }
                }
            }
        }
        while(!Q.empty())
        {
            a = Q.front();
            Q.pop();
            for(i = 0; i<16; i++)
            {
                if(num[i])
                {
                    a.s[a.len] = i;
                    a.len++;
                    r = mod(a);
                    if(!r)//一直找到能整除n的方案
                    {
                        print(a);
                        return 1;
                    }
                    else
                    {
                        if(!vis[r] && a.len<499)
                        {
                            vis[r] = 1;
                            Q.push(a);
                        }
                    }
                    a.len--;//是不是觉得这里与a.len++这句话会无限重复，导致a.len一直为1？错了！要注意，在r与之前出现过的余数相同是，这次的a是没有压入队列的，也就是这次的a.len减少了，但是在队列中的a.len却没有减少！
                }
            }
        }
        return 0;
    }
    
    int main()
    {
        int t,i;
        char str[2];
        scanf("%d",&t);
        while(t--)
        {
            scanf("%d%d%d",&n,&c,&m);
            memset(num,0,sizeof(num));
            for(i = 0; i<m; i++)
            {
                scanf("%s",str);
                if(str[0]>='0' && str[0]<='9')
                    num[str[0]-'0'] = 1;
                else
                    num[str[0]-'A'+10] = 1;
            }
            if(n)
            {
                int flag;
                flag = BFS();
                if(!flag)
                    printf("give me the bomb please\n");
            }
            else
            {
                if(num[0])
                    printf("0\n");
                else
                    printf("give me the bomb please\n");
            }
        }
        return 0;
    }