You are given a long decimal number aa consisting of nn digits from 11 to 99. You also have a function ff that maps every digit from 11 to 99 to some (possibly the same) digit from 11 to 99.
You can perform the following operation no more than once: choose a non-empty contiguous subsegment of digits in aa, and replace each digit xx from this segment with f(x)f(x). For example, if a=1337a=1337, f(1)=1f(1)=1, f(3)=5f(3)=5, f(7)=3f(7)=3, and you choose the segment consisting of three rightmost digits, you get 15531553 as the result.
What is the maximum possible number you can obtain applying this operation no more than once?
The first line contains one integer nn (1≤n≤2⋅1051≤n≤2⋅105) — the number of digits in aa.
The second line contains a string of nn characters, denoting the number aa. Each character is a decimal digit from 11 to 99.
The third line contains exactly 99 integers f(1)f(1), f(2)f(2), ..., f(9)f(9) (1≤f(i)≤91≤f(i)≤9).
Print the maximum number you can get after applying the operation described in the statement no more than once.
1 #include<bits/stdc++.h> 2 #include<cstring> 3 #include <stdlib.h> 4 using namespace std; 5 typedef long long ll; 6 const int N=200000+10; 7 int main() { 8 char c[N]; 9 ll c1[N],n; 10 string b; 11 int a[15],cnt=0; 12 cin>>n>>c; 13 bool flag=true; 14 for(int i=1; i<=9; i++) { 15 cin>>a[i]; 16 } 17 for(int i=0; i<n; i++) { 18 c1[i]=c[i]-'0'; 19 } 20 for(int i=0; i<n; i++) { 21 if((c1[i])<a[c1[i]]) { 22 c1[i]=(a[c1[i]]); 23 cnt++; 24 } else if((c1[i])>a[c1[i]]&&cnt!=0) { 25 break; 26 } 27 } 28 for(int i=0; i<n; i++) { 29 cout<<c1[i]; 30 } 31 }
思路分析：将输入的字符数组转换成整数，根据数据整数值为所给9个数序列的下标进行替换，要是所换序列大于原字符就进行替换，同时确保替换字符是连续的。