1. 给定 $d,k$, 求最小的被 $d$ 整除, 且各数位仅有 $k$ 和 $0$ 组成的数.
从高位到低位 $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$.
- #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\n", vis[0]?dis[0]:-1);
- }
来源: http://www.bubuko.com/infodetail-3110754.html