https://codeforces.com/contest/1202/problem/B
题目大意
给出一个 $0 \sim 9$ 字符组成的序列 $S \ (1 \le |S| \le 2 \times 10^6)$ 且 $S$ 总以 $0$ 开始，这个序列是由 $x, y \ (0 \le x, y \le 9)$ 由以下规则生成出来的。
- 最初数字 $a$ 为 $0$。输出这个数
- 随机的从 $x, y$ 中选出一个数加到 $a$ 上并输出 $a$ 的个位数字。重复这个过程若干次
- 删除生成的序列中的若干数字得到 $S$。
对于所有的 $x, y \ (0 \le x, y \le 9)$ 对，$S$ 至少删掉了某个生成序列中的多少数。如果 $x, y$ 对无法得到序列，输出 $-1$。
简要题解
序列中数字个位从 $a$ 变为 $b$，相当于我们希望知道模 $10$ 意义下 $ix + jy + a = b$ 最小的 $i + j$ 是多少。注意到 $i, j > 10$ 是没意义的。因此我们只要暴力枚举 $i, j$ 就可以得出每种 $a$ 变成 $b$ 的最小代价。
注意原串很长，所以需要把所有的转化统计出来。
复杂度
$T$：$O(n + 10^5)$
对于下面的代码，如果我们先维护所有 $diff$ 的最优值，可以省掉一个 $10$。但是这题复杂度瓶颈其实不在这里，所以无所谓了。
$S$：$O(n + 10^2)$
代码实现
#include <bits/stdc++.h>
using namespace std;
int io_=[](){ ios::sync_with_stdio(false); cin.tie(nullptr); return 0; }();
using LL = long long;
using ULL = unsigned long long;
using LD = long double;
using PII = pair<int, int>;
using VI = vector<int>;
using MII = map<int, int>;
template<typename T> void cmin(T &x,const T &y) { if(y<x) x=y; }
template<typename T> void cmax(T &x,const T &y) { if(x<y) x=y; }
template<typename T> bool ckmin(T &x,const T &y) {
return y<x ? (x=y, true) : false; }
template<typename T> bool ckmax(T &x,const T &y) {
return x<y ? (x=y, true) : false; }
template<typename T> void cmin(T &x,T &y,const T &z) {// x<=y<=z
if(z<x) { y=x; x=z; } else if(z<y) y=z; }
template<typename T> void cmax(T &x,T &y,const T &z) {// x>=y>=z
if(x<z) { y=x; x=z; } else if(y<z) y=z; }
// mt19937 rnd(chrono::system_clock::now().time_since_epoch().count());
// mt19937_64 rnd_64(chrono::system_clock::now().time_since_epoch().count());
/*
---------1---------2---------3---------4---------5---------6---------7---------
1234567890123456789012345678901234567890123456789012345678901234567890123456789
*/
void solve() {
string s; cin >> s;
int n = s.length();
vector<vector<int>> cnt(10, vector<int>(10));
for (int i = 1; i < n; i++) {
cnt[s[i - 1] - '0'][s[i] - '0']++;
}
vector<vector<int>> mi(10, vector<int>(10));
for (int x = 0; x < 10; x++) {
for (int y = 0; y < 10; y++) {
for (int i = 0; i < 10; i++) {
for (int j = 0; j < 10; j++) {
mi[i][j] = -1;
}
}
for (int i = 0; i <= 10; i++) {
for (int j = 0; j <= 10; j++) {
if (i + j == 0) continue;
int diff = (i * x + j * y) % 10;
for (int fr = 0; fr < 10; fr++) {
int to = (fr + diff) % 10;
if (mi[fr][to] == -1 || mi[fr][to] > i + j - 1) {
mi[fr][to] = i + j - 1;
}
}
}
}
int ans = 0;
for (int i = 0; ans != -1 && i < 10; i++) {
for (int j = 0; j < 10; j++) {
if (!cnt[i][j]) continue;
if (mi[i][j] == -1) {
ans = -1;
break;
}
ans += mi[i][j] * cnt[i][j];
}
}
cout << ans << (" \n"[y == 9]);
}
}
}
int main() {
int t = 1;
// cin >> t;
while (t--) {
solve();
}
return 0;
}
Next: [LC] 3420. Count Non-Decreasing Subarrays After K Operations - Weekly Contest 432