题解：P11386 [POI 2024/2025 R1] Zamek cykliczny

· · 题解

先让我们考虑一个贪心。

想要得到 1，就只能是通过将 100\dots 0 循环右移一次，而得到 100\dots 0 只能是将 99\dots 9+1 或者原本的 n 就是这个样子。

那么对于给定的 n，若其最低位 0<c<9，那么增加 9-c 次，然后位移；若 c=0 就直接位移。

执行上述操作直到 n 全部变为 9，然后再花费两次变成 1。

这个贪心可以通过子任务 1,2。

这个贪心显然是错的，比如当 n=\underbrace{99\dots 9}_{10^6-2\text{ 个}}89 时，进行 10 次增加操作要优于 10^6-1 次位移操作。

问题在于我们并不能够确定位移操作的执行次数，在某些情况下使用增加操作去代替位移操作可能是更优的。

假设要进行 k 次位移操作，我们将 n 分成两段：一段包含前 k 个非零数位以及在其之后接上的 0；另一段包含剩下的数位。分别记作前缀 p 和后缀 s。

例如在 n=120030005607 和 k=3 时 p=12003000,s=5607。

我们的策略是，先对后缀 s 进行增加操作，直到后缀全变成 9，需要做 \underbrace{99\dots 9}_{s\text{ 的长度个}}-s 次。

之后再按照最开始的贪心来处理前缀 p，这部分要 k+\sum9-c_i 次。

同时先进行位移操作再将后缀 s 全部变为 9 是不优的，因为你进行位移操作过后，将 s 变为 9 的代价会增加 10 倍。

令 n 的长度为 m，那么时间复杂度为 O(m^2)。

可以发现，对后缀 s 进行很多次增加操作是不会优于直接贪心的。

贪心最多只会耗费 10^7 次操作，因此我们只需要枚举使得后缀 s 增加的次数不超过 10^7 次的情况。

令 t 表示 n 中非零数位的数量，那么只需要 t-7\le k\le t。

还存在一种情况就是存在一种后缀形如 99\dots 9ABCDEFG，这种后缀的增加次数也不会超过 10^7。

所以总共需要考虑的情况只有 O(1) 种，时间复杂度 O(m)。

#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
const int N = 1e6 + 5;
int n, k;
string s;
ll solve(int r) {
    ll sum = r, i, j, tot = 0, tmp = 0;
    for(i = 1, j = 0; i <= n && j < r; i++) if(s[i] > '0') sum += '9' - s[i], j++;
    while(i <= n && s[i] == '0') i++;
    while(i <= n && s[i] == '9') i++;
    if(n - i + 1 > 7) return 0x3f3f3f3f3f3f3f3f;
    for(; i <= n; i++) tot = tot * 10 + 9, tmp = tmp * 10 + s[i] - '0';
    return sum + tot - tmp;
}
int main() {
#ifdef ddxrS
    freopen("sample.in", "r", stdin);
    freopen("sample.out", "w", stdout);
#endif
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    cin>>s; n = s.length(), s = '#' + s;
    for(int i = 1; i <= n; i++) k += (s[i] != '0');
    if(k == 1 && s[1] == '1' && n == 1) return cout<<0<<'\n', 0;
    if(k == 1 && s[1] == '1') return cout<<1<<'\n', 0;
    ll ans = 0x3f3f3f3f3f3f3f3f, lst = n;
    for(int i = n - 7; i >= 0; i--) if(s[i] != '9') {lst = i; break;} 
    for(int i = max(0, k - 7); i <= k; i++) ans = min(ans, solve(i));
    cout<<min(ans, solve(lst)) + 2<<'\n';
    return 0;
}