题解：P14287 [ICPC 2025 WF] Score Values

Little_Crocodile · 2026-10-20 09:48:34 · 题解

前言

改题解写法参考了 apple365 和 GPT 的写法。

题意

你初始有一个整数 0，每次将该数加上一个给定的得分，若该数大于 m 变成 m，然后你要知道对于每个数字，在可能的得分中出现的最大次数。

思路

第一步：考虑哪些分数可以到达

我们先取 p 数组中最小值的记为 minn。

我们可以考虑建造 minn 个点，值域为 [0, minn - 1]。对于所有的 p 我们可以建边 x 到 (x + p) \bmod minn，边权为 p，跑同余最短路。

则 dis_x 表示凑出余数 x 的最小得分，因此对于任意一个 y 如果可以得到，当且仅当如下条件：

dis_{y \bmod minn} \le y

因为我们如果 y 得的到他肯定比到达他除 minn 模数的点的可能的最大得分一样或更大。（显然）

其次由于我们是同余最短路，很明显 y 和 y \bmod minn 是同余的，那么 y = y \bmod minn + k \times minn。

所以这个条件是充要条件。

第二步分类讨论

我们设 maxx 为可达余数对应的 dis 的最大值。

对于 x \le maxx 的数我们直接暴力枚举判断（易得 maxx 不会特别大）
对于 maxx < x \le m 的点可以用数位 DP 后面会详细讲。
对于 x > m 那他会变成 m 所以需要提前处理 0 和 m。

第三步数位 DP

其实只要会模板就行了。

我们可以考虑暴力遍历每个数字（[0, 9]）分别处理答案。

在数位 DP 的时候我们依然要满足他的 dis[x \bmod minn] 合法，由于我们钦定了 x > maxx 所以只要 dis[x \bmod minn] 不是正无穷即可。

我们定义 dp[x][limit][flag][vis][w][now] 表示对于当前填了 x 位是否有上界下界前导零和已经出现了 w 个目标数且当前除以 minn 的模数为 now 的可能最大目标数字出现次数。

然后就是模板了。

复杂度显然合理。

总结

本人自认为该题难点在于转图论变成求同余最短路后的转变限制求得答案。

代码

码风比较猎奇

#include<bits/stdc++.h>
#define int long long
#define PII pair<int,int>

using namespace std;

const int MAXX = 1e3 + 5, MAXK = 1e2 + 5;

int n, m, ans[MAXX], p[MAXX], minn, maxx, cnt[MAXX], dp[20][2][2][2][20][MAXX], a[MAXX], b[MAXX], tot1, tot2, dis[MAXX], vis[MAXX];
priority_queue<PII, vector<PII>, greater<PII> > q;

void add_answer(int x){
  memset(cnt, 0, sizeof cnt);
  while(x) cnt[x % 10]++, x /= 10; cnt[6] += cnt[9];
  for(int i = 0; i <= 9; i++) ans[i] = max(ans[i], cnt[i]);
}

int dfs(int x, int limit, int flag, int vis, int w, int now, int id){
  if(x == 0) return (dis[now] != dis[minn + 1]) * w; //需满足可达到条件
  if(dp[x][limit][flag][vis][w][now] != -1) return dp[x][limit][flag][vis][w][now];
  int num = 0;
  for(int i = (flag ? b[x] : 0); i <= (limit ? a[x] : 9); i++){
    int tmp = w;
    if(id == 0) tmp += (!vis && (i == 0));
    else if(id == 6) tmp += (i == 6 || i == 9);
    else tmp += (i == id);
    num = max(num, dfs(x - 1, limit & (i == a[x]), flag & (i == b[x]), vis & (i == 0), tmp, (now * 10 + i) % minn, id));
  } dp[x][limit][flag][vis][w][now] = num;
  return num;
}

signed main(){
  cin >> m >> n; ans[0] = 1, add_answer(m); minn = LLONG_MAX;
  for(int i = 1; i <= n; i++) cin >> p[i], minn = min(minn, p[i]);
  memset(dis, 0x3f, sizeof dis), dis[0] = 0, q.push({0, 0});
  while(!q.empty()){
    int x = q.top().second; q.pop();
    if(vis[x]) continue; vis[x] = 1;
    for(int i = 1; i <= n; i++){
      int y = (x + p[i]) % minn;
      if(dis[y] > dis[x] + p[i]) dis[y] = dis[x] + p[i], q.push({dis[y], y});
    }
  } for(int i = 0; i < minn; i++) if(dis[i] != dis[minn + 1]) maxx = max(maxx, dis[i]);
  for(int i = 1; i <= min(maxx, m); i++) if(dis[i % minn] <= i) add_answer(i);
  if(maxx < m){
    int tmp1 = m, tmp2 = maxx + 1;
    while(tmp1) a[++tot1] = tmp1 % 10, tmp1 /= 10;
    while(tmp2) b[++tot2] = tmp2 % 10, tmp2 /= 10;
    for(int k = 0; k <= 8; k++) memset(dp, -1, sizeof dp), ans[k] = max(ans[k], dfs(tot1, 1, 1, 1, 0, 0, k));
  } for(int i = 0; i <= 8; i++) if(ans[i]) cout << i << " " << ans[i] << '\n';
  return 0;
}