1. 给定$d,k$, 求最小的被$d$整除, 且各数位仅有$k$和$0$组成的数. $(1le kle 9,1le nle 1e6)$
从高位到低位$BFS$, BFS求出字典序最小的方案.
#include <iostream>
#include <cstdio>
#include <queue>
#define REP(i,a,n) for(int i=a;i<=n;++i)
#define x first
#define y second
using namespace std;
typedef pair<int,int> pii;
const int N = 1e6+10;
queue<int> q;
int d, k, vis[N];
pii pre[N];
void dfs(int x) {
if (pre[x].x!=-1) dfs(pre[x].x);
printf("%d", pre[x].y);
}
int main() {
scanf("%d%d", &d, &k);
q.push(k%d);
vis[k%d] = 1;
pre[k%d] = pii(-1,k);
while (q.size()) {
int u = q.front(); q.pop();
for (int i=0; i<=k; i+=k) {
int v = (u*10+i)%d;
if (!vis[v]) {
vis[v] = 1;
pre[v] = pii(u,i);
q.push(v);
}
}
}
dfs(0),puts("");
}
2. 被$d$整除, 数位和为$s$的数. (CF 1070A)
#include <iostream>
#include <cstdio>
#include <queue>
#define REP(i,a,n) for(int i=a;i<=n;++i)
#define x first
#define y second
using namespace std;
typedef pair<int,int> pii;
queue<pii> q;
int d, s, vis[555][5050];
pii pre[555][5050];
void dfs(int x, int y) {
if (x||y) {
dfs(pre[x][y].x,pre[x][y].y);
printf("%d",y-pre[x][y].y);
}
}
int main() {
scanf("%d%d", &d, &s);
q.push(pii(0,0));
vis[0][0] = 1;
while (q.size()) {
pii u = q.front(); q.pop();
REP(i,0,9) {
pii v((u.x*10+i)%d,u.y+i);
if (v.y<=s&&!vis[v.x][v.y]) {
q.push(v);
pre[v.x][v.y] = u;
vis[v.x][v.y] = 1;
}
}
}
if (!vis[0][s]) return puts("-1"),0;
dfs(0,s),puts("");
}
3. 给定$k$种浓度的水, 每种数量无限, 求混合为浓度$n$最少要多少杯.
容易发现答案序列$a_i$满足$sum (a_i-n)=0$, 从而转化为$BFS$求最小环.
但是有一个问题是$sum (a_i-n)$的范围, 测试一下发现只要保证每步都在$[-1000,1000]$一定最优, 考虑证明.
只需要证明 任意一个最优解均可通过重排, 使得每一步的和都在$[-1000,1000]$即可.
考虑一个最优方案, 假设当前的$s>0$, 考虑添加一个数$t>0$.
不合法当且仅当$s+t>1000$, 考虑调整后面负数的位置, 使得方案合法.
若剩余负数存在一个$x$,有$-xge t$, 那么直接转移为$s+x+t$即可.
否则剩余负数全在范围$[-t+1,0)$内.
并且剩余负数总和绝对值一定不少于$s+t$(合法方案保证总和为$0$).
这样的话不断选负数, 直到$s+sum x + t le 1000$, 这样一定合法.
这是因为调整过程中, 最坏情况是和变为$s+sum x=1001-t$, 然后添加一个最小数得到$s+sum x=1002-2t>-1000$, 满足条件.
所以结论成立.
#include <iostream>
#include <cstdio>
#include <queue>
#define REP(i,a,n) for(int i=a;i<=n;++i)
using namespace std;
const int N = 1e5+10;
int n, k, a[N];
int v[N], d[N], *dis = d+5010, *vis = v+5010;
queue<int> q;
int main() {
scanf("%d%d", &n, &k);
REP(i,1,k) {
scanf("%d", a+i);
a[i] -= n;
if (vis[a[i]]) {
--i, --k;
continue;
}
vis[a[i]] = 1;
dis[a[i]] = 1;
q.push(a[i]);
}
while (q.size()) {
int u = q.front(); q.pop();
REP(i,1,k) {
int v = u+a[i];
if (abs(v)>1000) continue;
if (!vis[v]) {
vis[v] = 1;
dis[v] = dis[u]+1;
q.push(v);
}
}
}
printf("%d
", vis[0]?dis[0]:-1);
}