题解归档 - cf1202B

本文由 cf-code 本地题解库自动归档；公开内容以本地 AC/验证版本为准。

• 本地编号：cf1202B
• 本地来源：problems/cf1202B/idea.md
• 题目链接：https://codeforces.com/contest/1202/problem/B
• 原始标题：cf1202B — You Are Given a Decimal String...

思路

cf1202B — You Are Given a Decimal String...

题意

x-y 计数器从 0 出发，每次打印当前值个位，再加 x 或 y。给定残缺串 s（首位为 0），对每个 (x,y) 求最少插入多少数字使 s 成为某条合法输出子序列。

做法

预处理相邻数字对频次 cf[a][b]。固定 (x,y) 时，枚举从 digit a 到 b 最少步数 ds[a][b]：用至多 9 次 +x 和 9 次 +y 组合（模 10 周期为 10）。答案 sum (ds[a][b]-1)*cf[a][b]，不可达则 -1。

验证

样例 AC；WSL 对拍 200 组（Floyd 暴力交叉验证）。

代码

来源：problems/cf1202B/solution.cpp

/* Author: likely
 * Time: 2026-06-08 03:08:42
**/
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll inf=1000000000;
const ll bad=1000000007;
string s;
ll cf[10][10],ds[10][10],i,j,k,x,y,cx,cy,v,to,zc,pd,cur,dq,cnt,ans,res;
int main(){
    cin>>s;
    for(i=1;i<(ll)s.size();i++) cf[s[i-1]-'0'][s[i]-'0']++;
    for(x=0;x<10;x++){
        for(y=0;y<10;y++){
            for(i=0;i<10;i++) for(j=0;j<10;j++) ds[i][j]=bad;
            for(v=0;v<10;v++){
                for(cx=0;cx<10;cx++){
                    for(cy=0;cy<10;cy++){
                        if(cx+cy==0) continue;
                        to=(v+cx*x+cy*y)%10;
                        ds[v][to]=min(ds[v][to],cx+cy);
                    }
                }
            }
            res=0,pd=0;
            for(v=0;v<10;v++){
                for(to=0;to<10;to++){
                    if(ds[v][to]>inf and cf[v][to]>0){
                        res=-1,pd=1;
                        break;
                    }
                    res+=(ds[v][to]-1)*cf[v][to];
                }
                if(pd) break;
            }
            cout<<res;
            if(y==9) cout<<"\n";
            else cout<<" ";
        }
    }
    return 0;
}