CodeForces-1157-B Long Number

Topic link:Long Number
Description:
You are given a long decimal number a consisting of n digits from 1 to 9. You also have a function f that maps every digit from 1 to 9 to some (possibly the same) digit from 1 to 9.

You can perform the following operation no more than once: choose a non-empty contiguous subsegment of digits in a, and replace each digit x from this segment with f(x). For example, if a=1337, f(1)=1, f(3)=5, f(7)=3, and you choose the segment consisting of three rightmost digits, you get 1553 as the result.

What is the maximum possible number you can obtain applying this operation no more than once?

Input
The first line contains one integer n (1≤n≤2e5) — the number of digits in a.

The second line contains a string of n characters, denoting the number a. Each character is a decimal digit from 1 to 9.

The third line contains exactly 9 integers f(1), f(2), …, f(9) (1≤f(i)≤9).

Output
Print the maximum number you can get after applying the operation described in the statement no more than once.

Examples
input
4
1337
1 2 5 4 6 6 3 1 9
output
1557
input
5
11111
9 8 7 6 5 4 3 2 1
output
99999
input
2
33
1 1 1 1 1 1 1 1 1
output
33
Intentional analysis:
Through reading this questions,we can see that this question is a greedy type of problem.Each number will correspond to another number,and if the corresponding number is greater than this number,we need to use it instead of this number,and as long as such a number appears continuously,we can always change it,but we can only change it once,and To find the maximum number after the change,you only need to find a series of consecutive changeable changes from the front and then output.

Click to see Chinese Intentional analysis 这道题就是每一个数都对应着一个数,题目要求更换之后取得最大值,可是只能更换一次,每次更换可以更换任一个数但是必须是连续的。这时就体现出贪心的思想了,要想这个数变得更大,在这个数的越高的位置数就得越大,所以只需要从前往后看,只要发现对应的数比本身大就开始更换直到对应的数小于本身,就停止更换。

Code:

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n;string s;char x;
    cin>>n>>s;
    map<int,char> ma;
    for(int i=1;i<=9;i++)
    {
        cin>>x;
        ma[i]=x;
    }
    int flag;
    char mid;
    for(int i=0;i<s.size();i++)
    {
        if(s[i]<ma[s[i]-'0'])
        {
            flag=i;
            break;
        }
    }
    for(int i=0;i<flag;i++)
    {
        cout<<s[i];
    }
    bool flag2=1;
    for(int i=flag;i<s.size();i++)
    {
        if(s[i]>ma[s[i]-'0'])
            flag2=0;
        if(flag2)
            cout<<ma[s[i]-'0'];
        else
            cout<<s[i];
    }
    cout<<endl;
    return 0;
}

I didn’t understand the meaning of this question at first, which led to WA several times and wasted my time.

Now the result of hack has not come out yet, if my code was hacked.I will find the bug and correct it as soon as possible!(2019.4.27 1:03)


Accepted(2019.4.27 22:52)