CF1157B Long Number 题解

发布于 2020-09-26  659 次阅读


已有的题解或是说的太麻烦了,或是一笔带过,本篇题解决定简明扼要地好好讲一讲。

题意

题目链接 大体题意不再阐述,注意你只能根据给出的规则更换一段数而不能隔开来换就好了。

解析

已有的题解也都提到了,遇到第一个 $b_{num_i}>num_i$ ( $b$ 数组为更换规则,$num$ 数组为每一位的数字)时开始更换,一直更换到 $b_{num_i}<num_i$ 为止。

那么,为什么呢?

首先我们知道,越是高位增大,效益就越大, 因此我们要尽早开始更换,也就是从第一个可以变大的最高位开始,而又由于题目中要求更换的是一段数,同样的,越是高位变小,亏损就越大,因此我们要在找到第一个会变小的数时就及时止损,即停止更换并退出。

至于为什么是 $>$ 而不是 $\ge$ 呢?

显然的,我们找到第一个 $b_{num_i}\ge num_i$ 的数时,我们如果直接进行更换,那就容易过早碰壁,且这个行为时毫无意义的,这样还不如放到后面换。

例:样例一中的数若改为 $1733$ 则采用 $\ge$ 在替换了第一个数后,碰到 $7$ 就会停止,而实际上应该把这次更换的机会留下来,从第三位开始更换。

代码

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5;
int n,num[N],b[N];
char a[N];
bool flag;
int main(){
    scanf("%d",&n);
    scanf("%s",a+1);
    for(int i=1;i<=n;i++)
        num[i]=a[i]-'0';
    for(int i=1;i<=9;i++)
        scanf("%d",&b[i]);
    for(int i=1;i<=n;i++){
        if(b[num[i]]>num[i]){
            if(!flag) flag=true;//flag 判断有无开始更换 
            num[i]=b[num[i]];
        }
        else if(b[num[i]]<num[i])
            if(flag) break; //若开始更换后碰到会亏损的数,就退出 
    }
    for(int i=1;i<=n;i++)
        printf("%d",num[i]);
    return 0;
}

琐记

这题恶意评分了吧,实际难度橙或黄差不多了吧。


月流华 岁遗沙 万古吴钩出玉匣