51NOD 1109 01组成的N的倍数

题目链接https://www.51nod.com/onlineJudge/questionCode.html#!problemId=1109

题意:略。

思路10分钟写完,DEBUG一天...最后竟发现是一个很玄学的错误。数位BFS搜索即可,根据题目的要求可能解是会很大的,甚至爆longlong,但根据题目条件我们可以规约到N个节点的图,跟atcoder那道题一样,对n取模即可,只要到达0这个节点即可停止搜索,但是...但是...我每次入队列的时候都是先考虑乘101然后再考虑乘100的,导致一直WA,交换了一下就过了。。。可能是因为要最小,然后我如果先考虑加一就有可能小的数本来可以到达但是已经被大的数占掉了,直接导致输出的解不优,算是一个需要注意的点了啊。

#include <bits/stdc++.h>
using namespace std;
const int maxn=5e6+10;
#define pii pair<string,int>
int n;
bool vis[maxn];
int main(){
    scanf("%d",&n);
    if (n==1) return puts("1")*0;
    queue<pii>Q;
    Q.push(make_pair("1",1));
    vis[1]=true;
    while (!Q.empty()){
        pii cur=Q.front();Q.pop();
        if (cur.second==0){
            cout<<cur.first<<endl;
            return 0;
        }
        int tmp=(cur.second*10)%n;
        if (!vis[tmp]){
            vis[tmp]=true;
            Q.push(make_pair(cur.first+"0",tmp));
        }
        tmp=(cur.second*10+1)%n;
        if (!vis[tmp]){
            vis[tmp]=true;
            Q.push(make_pair(cur.first+"1",tmp));
        }
    }
    return 0;
}