zjp 老师的第二套题。
讲题之前的经验分享内容整理：
在考模拟赛时，
1.不会的知识点：记下来，赛后看博客学习，做题。
2.考试策略。总结分为什么没了：
(1) 写挂了->总结，为什么会挂，错误点，是否需要练习对拍。在考试中一定不能挂分。平时保证不挂分。
(2)时间不够写，赛时调不出来：多练题。刷题也能培养调试能力。调不出来，也能说明代码能力不行。
(3)时间的分配。不可写的、码量大的不要写。每个题都要得分，不要死磕题目。只是为了取得高分。部分分很多很多。所以写部分分。
3.学习策略：
(1)考试与学习相促进。考试能发现：知识点缺陷，代码能力问题。然后刷题，学算法。考试，发现不足...
(2)做一系列的题。学透，套路。
4.赛后：
(1)尝试改题（补题）。
(2)不看 std。培养自己的思维。直接看没有经过思考的话，细节是想不到的。
(3)看题解，然后自己写一遍。
(4)接下来调试的过程，能培养调试能力，培养代码、调试能力，加深对题目的思考。再写不出来，再看 std。而不是抄。
赛时发现枚举倍数的话会爆炸，所以直接枚举位数，用 long long 可以存到这个 1e18，可能算或者不算数位 dp 吧（？），有 80pts。于是这是我赛时丑陋的码：
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=1e6+10;
ll ans;
int k,n;
int vis[12],a[12];
ll f[N][2];
int tot[2],flag;
void solve(){
for(int i=1;i<=n;i++) if(a[i])f[++tot[1]][1]=a[i];
for(int i=2;i<=18;i++){
int p=i&1;
for(int t=1;t<=tot[p^1];t++){
for(int j=1;j<=n;j++){
f[++tot[p]][p]=f[t][p^1]*10+a[j];
if(f[tot[p]][p]%k==0){
flag=1;
printf("%lld",f[tot[p]][p]);
return;
}
}
}
tot[p^1]=0;
}
}
int main(){
scanf("%d%d",&k,&n);
for(int i=1;i<=n;i++){
int x;
scanf("%d",&x);
vis[x]=1;
}
if(k==5&&vis[0]&&vis[5]){
puts("-1");
return 0;
}
n=0;
for(int i=0;i<=9;i++) if(!vis[i]) a[++n]=i;
solve();
if(!flag) puts("-1");
return 0;
}
赛时想了一阵子怎么写呢。
正解，考虑数位 dp，从低位到高位每一位从小到大放，判断是否可行，找第一个可行解。另 \(f_i\) 表示 \(mod \text{ } k=i\) 时最小的数。
80pts 的就是用 long long 存。
进一步优化，每次存下的都是这个同宇 k 的最小数，我们只需要保留这个数就行了。因为枚举添加哪个数，将原数 \(v*10+[0,9]\)，产生的新数模数若没出现过就加入队列。第一次找到的 \(mod\text{ k=0}\) 即为答案。
每次用 \(pre1_i\) 存一下 \(i\) 从哪个数转移过来、新加了 \(pre2_i\) 、最后倒序输出。O(k) 。
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=1e6+10;
int n,m;
int vis[N],mod[N];
int p1[N],p2[N];
queue<int> q;
void print(int x){
if(p2[x]) print(p2[x]);//倒序输出
printf("%d",p1[x]);//后加到数列尾部的
}
int main(){
scanf("%d%d",&m,&n);
for(int i=1;i<=n;i++){
int x;
scanf("%d",&x);
vis[x]=1;
}
for(int i=1;i<=9;i++){//0不能做首位
if(!vis[i]){
q.push(i);
mod[i]=1;
p1[i]=i;
}
}
while(q.size()){
int x=q.front();
q.pop();
for(int i=0;i<=9;i++){
int t=(x*10+i)%m;
if(mod[t]||vis[i]) continue;
q.push(t);
mod[t]=1;//新的余数
p1[t]=i,p2[t]=x;//新加入的数字、从哪转移来
}
if(mod[0]){
print(0);
return 0;
}
}
puts("-1");
}
类似于 01 BFS。这种，求某个条件最小的数，都可能会用 BFS 以及类似的方法来求解。
猜猜赛时是哪个傻逼调这个题调了两个半小时最后还爆零了？无论如何，这个题意，给的是有些问题的。我不好说。
正解是二份答案 + 优先队列优化 check。赛时贪错了 /kk。
C
猜猜是谁没学过数学！