题意:给你两个字符串\(s\)和\(t\),保证\(t\)的字典序大于\(s\),求他们字典序中间的字符串.
题解:我们假设题目给的不是字符串,而是两个10禁止的正整数,那么输出他们之间的数只要把他两加起来除\(2\)就行了,那么对于字符串又为何不可呢?我们可以将每个字母看成\(26\)进制的数,像高精度那样模拟加法运算的过程,然后再模拟除\(2\)的过程即可.
代码:
int k;
string s,t;
int c[N];
int d[N];
int main() {
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
cin>>k;
cin>>s>>t;
int cur=0;
per(i,k-1,0){
c[i+1]=(s[i]-'a'+t[i]-'a'+cur)%26;
cur=(s[i]-'a'+t[i]-'a'+cur)/26;
}
if(cur) c[0]=cur;
cur=0;
rep(i,0,k){
d[i]=(cur*26+c[i])/2;
cur=c[i]%2;
}
rep(i,1 ,k){
char c=d[i]+'a';
cout<<c;
}
return 0;
}