题解归档 - cf2228C1

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

• 本地编号：cf2228C1
• 本地来源：problems/cf2228C1/idea.md
• 题目链接：https://codeforces.com/contest/2228/problem/C1
• 原始标题：cf2228C1 - Cirno and Number

思路

cf2228C1 - Cirno and Number

pattern: digit construction / nearest lower and nearest upper.

claim: The closest valid number is either the maximum valid decimal representation not larger than a, or the minimum valid decimal representation not smaller than a.

necessary: For a fixed length, lexicographic order is numeric order if the first digit is nonzero. A normal decimal representation cannot have a leading zero unless it is exactly 0.

sufficient: To build the lower candidate, keep equal digits while possible; at the first impossible position, put the largest allowed smaller digit and fill the suffix with the maximum allowed digit. If that is impossible, decrease the nearest previous chosen digit and fill the suffix by maximum digits, or use the best shorter length. The upper candidate is symmetric with larger digit and minimum suffix.

brute/check: brute.cpp enumerates small non-negative integers and checks whether their decimal digits are allowed. gen.cpp generates random small C1 cases with exactly two allowed digits. Stress compares the construction against brute.

edge: a=0, digit set only contains 0, digit set contains 0 plus nonzero digits, no same-length lower/upper candidate, and powers of ten.

代码

来源：problems/cf2228C1/solution.cpp

#include<bits/stdc++.h>
#define ll long long
using namespace std;
vector<int>d;
int ok[10];
const __int128 inf=((__int128)1<<120);
__int128 val(string s){
    __int128 x=0;
    for(char c:s) x=x*10+c-'0';
    return x;
}
void print(__int128 x){
    if(x==0){
        cout<<"0\n";
        return;
    }
    string s;
    while(x){
        s.push_back(char('0'+x%10));
        x/=10;
    }
    reverse(s.begin(),s.end());
    cout<<s<<"\n";
}
pair<int,string> mxstr(int len){
    if(len<=0) return {0,""};
    if(len==1) return {1,string(1,char('0'+d.back()))};
    int fst=-1;
    for(int x:d) if(x>0) fst=x;
    if(fst==-1) return {0,""};
    string s(1,char('0'+fst));
    for(int i=1;i<len;i++) s.push_back(char('0'+d.back()));
    return {1,s};
}
pair<int,string> mnstr(int len){
    if(len<=0) return {0,""};
    if(len==1) return {1,string(1,char('0'+d[0]))};
    int fst=-1;
    for(int x:d) if(x>0&&fst==-1) fst=x;
    if(fst==-1) return {0,""};
    string s(1,char('0'+fst));
    for(int i=1;i<len;i++) s.push_back(char('0'+d[0]));
    return {1,s};
}
pair<int,string> getle(string s){
    int n=s.size();
    string r;
    for(int i=0;i<n;i++){
        int cur=s[i]-'0';
        if(ok[cur]&&(i||n==1||cur>0)){
            r.push_back(s[i]);
            continue;
        }
        int best=-1;
        for(int x=0;x<cur;x++) if(ok[x]&&(i||n==1||x>0)) best=x;
        if(best!=-1){
            r.push_back(char('0'+best));
            for(int j=i+1;j<n;j++) r.push_back(char('0'+d.back()));
            return {1,r};
        }
        for(int j=i-1;j>=0;j--){
            int y=r[j]-'0';
            best=-1;
            for(int x=0;x<y;x++) if(ok[x]&&(j||n==1||x>0)) best=x;
            if(best!=-1){
                r[j]=char('0'+best);
                r.resize(j+1);
                for(int k=j+1;k<n;k++) r.push_back(char('0'+d.back()));
                return {1,r};
            }
        }
        return mxstr(n-1);
    }
    return {1,r};
}
pair<int,string> getge(string s){
    int n=s.size();
    string r;
    for(int i=0;i<n;i++){
        int cur=s[i]-'0';
        if(ok[cur]&&(i||n==1||cur>0)){
            r.push_back(s[i]);
            continue;
        }
        int best=10;
        for(int x=cur+1;x<=9;x++) if(ok[x]&&(i||n==1||x>0)){
            best=x;
            break;
        }
        if(best!=10){
            r.push_back(char('0'+best));
            for(int j=i+1;j<n;j++) r.push_back(char('0'+d[0]));
            return {1,r};
        }
        for(int j=i-1;j>=0;j--){
            int y=r[j]-'0';
            best=10;
            for(int x=y+1;x<=9;x++) if(ok[x]&&(j||n==1||x>0)){
                best=x;
                break;
            }
            if(best!=10){
                r[j]=char('0'+best);
                r.resize(j+1);
                for(int k=j+1;k<n;k++) r.push_back(char('0'+d[0]));
                return {1,r};
            }
        }
        return mnstr(n+1);
    }
    return {1,r};
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t,n,i,x;
    string s;
    cin>>t;
    while(t--){
        cin>>s>>n;
        d.clear();
        memset(ok,0,sizeof(ok));
        for(i=1;i<=n;i++){
            cin>>x;
            d.push_back(x);
            ok[x]=1;
        }
        __int128 a=val(s),ans=inf;
        auto add=[&](pair<int,string> p){
            if(!p.first) return;
            __int128 v=val(p.second);
            if(v>a) ans=min(ans,v-a);
            else ans=min(ans,a-v);
        };
        if(ok[0]) add({1,"0"});
        add(getle(s));
        add(getge(s));
        print(ans);
    }
    return 0;
}