【Luogu】P1602Sramoc问题（堆）

　　题目链接

　　很巧妙的想法。一开始将1~k-1加入堆中，然后每次从堆里取出一个最小的，判断是不是答案，如果不是，那么就枚举新数的末一位加上。

　　代码如下

　　

#include<cstdio>
#include<cstdlib>
#include<cctype>
#include<cstring>
#include<algorithm>

inline long long read(){
    long long num=0,f=1;
    char ch=getchar();
    while(!isdigit(ch)){
        if(ch=='-')    f=-1;
        ch=getchar();
    }
    while(isdigit(ch)){
        num=num*10+ch-'0';
        ch=getchar();
    }
    return num*f;
}

long long heap[2000100];
long long size;
inline void push(long long x){
    heap[++size]=x;
    long long i=size,k;
    while(i>1){
        k=i>>1;
        if(heap[k]<=heap[i])    return;
        std::swap(heap[k],heap[i]);
        i=k;
    }
}

inline long long pop(){
    long long ans=heap[1];
    heap[1]=heap[size--];
    long long i=1,k;
    while(i<<1<=size){
        k=i<<1;
        if(k<size&&heap[k]>heap[k|1])    k|=1;
        if(heap[i]<=heap[k])    return ans;
        std::swap(heap[i],heap[k]);
        i=k;
    }
    return ans;
}

int main(){
    long long k=read(),m=read();
    for(long long i=1;i<k;++i)    push(i);
    while(size){
        long long s=pop();
        if(s%m==0&&s){
            printf("%lld",s);
            return 0;
        }
        for(register long long i=0;i<k;++i)    push(s*10+i);
    }
    return 0;
}