CF-[CF1841C] Ranom Numbers 题解

· · 题解

C: Ranom Numbers

C - Ranom Numbers

本题最暴力的方法就是将每一个位置都改变取最大值，此方法是 O(n^2) 的。

考虑是否可以只改变几个位置，答案是可以的。

定义：一个字母小是字典序小，大同理。

先给结论：

结论证明：

严谨证明较复杂，不过思路很清晰，只证结论 1 (A_1 那一列永远不劣于 A_2 那一列)，结论 2 同理可证。

证：

就以字母 A 为例：

设中间的字母的最大值为 X，A_1,A_2 可以变为以下几种情况：

先证 A_1 的情况 1 是不优于情况 2 的(以下都是简单文字描述)：首先明确一点：改变一个字母只会影响从第一个字母到其的贡献。不管 A 一开始对整个字符串的贡献是正是负，变为情况 2 贡献都是增加了，且左的贡献该是负还是负该是正还是正，所以 A_1 的情况 1 不优于情况 2，A_2 同理。

现在我们只需要知道 A_1,A_2 的后两种情况的关系即可。

为了阅读的方便，以下的“优于”和“更优”都是“不劣于”的意思，除“一定优于”外。

先证 A_1,A_2 的情况 2 是优于 A_2 的情况 2 的：很显然两个情况对左的贡献是相同的，并且两个 A 字母上升到 X 对整体的贡献也是相同的，意思只有中间是不同的，那么中间大于 A 小于 X 的字母的贡献就会变成负号，得证。A_1 的情况 3 是优于 A_2 的情况 3 同理。

再证如果 A_1 的情况 2 是比 A_1 的情况 3 更优的，那么 A_2 的情况 2 也比 A_2 的情况 3 更优：想象一下如果 A_1 的情况 2 是比 A_1 的情况 3 更优的，其实就是左中字母 X 较多(多多少？只需感性理解这个就行，其实就是从情况 2 到 3 多出来的 A_1 自身上升的贡献比不上左中字母 X 提供的负贡献)，同理若连 A_1 和中间的区域的负贡献都不看，A_2 的情况 2 也比 A_2 的情况 3 更优。

最后证 A_1 的情况 3 比 A_2 的情况 2 更优(也是本题较难证明的一部分)：首先证这个的条件是就 A_1 的情况 2，3 而言 3 更优和 A_2 的情况 2，3 而言 2 更优同时满足。由条件 1 可知(以下都是同上的感性理解)：左中字母 X 提供的负贡献比不上(或者说不大于)从情况 2 到 3 多出来的 A_1 自身上升的贡献。就先假设 X = B，则再假设 >X = C，你没看错就是 >X，易知 C = 10B = B+ 9B，B 是情况 2 的贡献，9B 可以形象的成为 \Delta。由条件 1 可知左中的 B 的个数小于等于 9，就设 A = 1,B = 10\cdots 以此类推。因此 A_1 的情况 3 的贡献 \ge B-A=10-1=9。先在考虑 A_2 的情况 2，因为中间部分可能会有小于 B 的，所以 A_2 的情况 2 的贡献 \le B-A=10-1=9，X 为其他字母的时候也同理。所以 A_1 的情况 3 比 A_2 的情况 2 更优。

整理上述 4 个证明可知：A_1,A_2 的情况 1 是不优于情况 2 的，所以只需要知道 A_1,A_2 的后两种情况的关系即可。又知道 A_1,A_2 的情况 2 和 3 是分别优于 A_2 的情况 2 和 3 的，又知道了如果 A_1 的情况 2 是比 A_1 的情况 3 更优的，那么 A_2 的情况 2 也比 A_2 的情况 3 更优，最后知道了 A_1 的情况 3 比 A_2 的情况 2 更优，就证毕了！

代码实现：

时间复杂度：O(n)。

核心代码：

const int N = 2e5 + 10;
char str[N];
int ch[5] = {1, 10, 100, 1000, 10000};
int ans, L[5], R[5];
void init(){
    ans = -inf;
    mms(L, 0), mms(R, 0);
}
int calc(int len){
    int res = 0;
    char maxc = 'A';
    pre(i, len, 1){
        int c = str[i] - 'A';
        if(maxc > str[i]) res += -ch[c];
        else{
            maxc = str[i];
            res += ch[c];
        }
    }
    return res;
}
int main(){
    int T; rd(T);
    while(T--){
        sf("%s", str + 1);
        int len = strlen(str + 1);
        init();
        rep(i, 1, len){
            if(!L[str[i] - 'A']) L[str[i] - 'A'] = i;
            R[str[i] - 'A'] = i;
        }
        rep(i, 0, 4){ //替换前 
            if(!R[i]) continue; //LR都行 
            rep(j, 0, 4){ //替换后 
                //替换L 
                char temp = str[L[i]];
                str[L[i]] = 'A' + j;
                ans = max(ans, calc(len));
                str[L[i]] = temp;
                //替换R 
                temp = str[R[i]];
                str[R[i]] = 'A' + j;
                ans = max(ans, calc(len));
                str[R[i]] = temp; 
            }
        }
        prf("%d\n", ans);
    }
    return 0;
}

完整代码