原题链接：https://codeforces.com/problemset/problem/1144/E
tag：字符串模拟，大整数。
题意：给定两个字符串，求字典序中间串。
思路：可以把这个题当做一个26进制数的模拟。a~z分别代表0~25，然后求平均，在通过数字反求字符串。
然后写出这么个代码
1 #include<bits/stdc++.h> 2 using namespace std; 3 typedef unsigned long long ll; 4 ll _input(ll); 5 void _output(ll,ll); 6 int main() 7 { 8 ll n; 9 cin>>n; 10 ll num1,num2; 11 num1=_input(n); 12 num2=_input(n); 13 ll res=0; 14 res=(num1+num2)/2; 15 _output(res,n); 16 cout<<endl; 17 return 0; 18 } 19 ll _input(ll n) 20 { 21 ll re=0; 22 char a; 23 for(ll i=0;i<n;i++) 24 { 25 cin>>a; 26 re=re*26+(a-‘a‘); 27 } 28 return re; 29 } 30 void _output(ll res,ll n) 31 { 32 stack<char> qq; 33 while(n--) 34 { 35 qq.push(‘a‘+res%26); 36 res/=26; 37 } 38 while(qq.size()) 39 { 40 cout<<qq.top(); 41 qq.pop(); 42 } 43 }
然后你就可以很快的wa了。
？？？
好吧，想着总不能爆掉我的unsigh long long 吧，然后打脸了。 26^10000,,,,随便爆。。
于是乎只能用数组模拟，一来可以方便的表示26进制，二来也可以表示很大的数据，爆不掉（除非非常非常变态了）
代码如下
1 #include<bits/stdc++.h> 2 using namespace std; 3 int a[1000005]; 4 int main() 5 { 6 int n; 7 cin>>n; 8 string c,b;//储存字符串 9 cin>>c; 10 cin>>b; 11 for(int i=n-1;i>=0;i--) //模拟加法 12 { 13 a[i+1]+=c[i]-‘a‘+b[i]-‘a‘; //从a[1]开始存，a[0]留着进位用。 14 a[i]+=a[i+1]/26; //给高一位先进位 15 a[i+1]%=26; //当前位对26取模。 16 } 17 char e;
//模拟除法 18 e=‘a‘; 19 if(a[0]>=2)cout<<char(e+a[0]/2); 20 if(a[0]%2!=0)a[1]+=26; //看最高位是否存在进位的，如果存在，退回来。 21 for(int i=1;i<=n;i++) 22 { 23 e=‘a‘; 24 cout<<char(e+a[i]/2); //输出当前位除2所表示的数。 25 if(a[i]%2!=0)a[i+1]+=26; //剩下的退回下一位。 26 } 27 cout<<endl; 28 return 0; 29 }
Codeforces 1144 E. Median String
原文：https://www.cnblogs.com/greenpepper/p/10645298.html
