题解：CF720E Cipher

· · 题解

CF720E Cipher 题解

博客园链接：CF720E Cipher 题解 - Add_Catalyst - 博客园 (cnblogs.com)。

知识点

进制，模拟，贪心。

分析

发现我们想要确定一位数时，只有两种方法：

  1. 该位数字自己加 1，从变化顺序可以看出它是哪一位。
  2. 该位数字加 1，导致高位数字出现变化，看出它现在变成了 0。这种情况包括整个数字达到了 n+1 位的情况。

那么我们从高位开始遍历，记一个答案为 ans，最小进位且变化的值为 len，初始时设为 1。

每次想要确定这一位数是否可行，就要和别的数进行比较，直到能够把两个数区分开。假设此位为 c，比较的为 j，那么比较的方法有两种：

  1. 循环串最长公共前缀长度 +1。
  2. 如果 j 能够引起高位进位，且进位能够看出来。

我们对于同一个 j，在这两种中取 \min，得到这一位的答案 lim，最后再整个答案 ans 中取 \max。

当我们从高一位到低一位的时候，我们需要更新 ans,len，不过根据定义，也不难实现。

时间复杂度 O(nw^2),w=10。

代码

constexpr int N(18+10);

char s[N],t[N];
int Cas,n;
ll ans,len;

int Cmain() {
    /*DE("Input");*/
    I(n),scanf("%s",s),ans=0,len=1;
    /*DE("Solve");*/
    FOR(i,0,n-1) {
        const int c(s[i]^48);
        scanf("%s",t),ans=ans*10-c;
        FOR(j,0,9)if(j!=c) {
            ll lim(len*10-max(j,c)); //上一位进位带来的影响
            FOR(k,0,min(lim-1,9ll))if(t[(c+k)%10]!=t[(j+k)%10]&&(lim=k,true))break;
            tomax(ans,lim);
        }
        len=len*10-c;
        FOR(j,1,9)if(t[c]!=t[(c+j)%10]&&(tomin(len,(ll)j),true))break;
    }
    /*DE("Output");*/
    O(ans,'\n');
    return 0;
}

signed main() {
#ifdef Plus_Cat
    freopen(Plus_Cat ".in","r",stdin),freopen(Plus_Cat ".out","w",stdout);
#endif
    for(I(Cas); Cas; --Cas)Cmain();
    return 0;
}