CF1157B Long Number 题解

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

题意

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

解析

已有的题解也都提到了,遇到第一个 $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;
}

琐记

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

本文作者:water_tomato
暂无评论

发送评论 编辑评论

|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇