Codeforces 1144 E. Median String

原题链接：https://codeforces.com/problemset/problem/1144/E

tag：字符串模拟，大整数。

题意：给定两个字符串，求字典序中间串。

思路：可以把这个题当做一个26进制数的模拟。a~z分别代表0~25，然后求平均，在通过数字反求字符串。

然后写出这么个代码

 #include<bits/stdc++.h>

 using namespace std;

 typedef unsigned long long ll;

 ll _input(ll);

 void _output(ll,ll);

 int main()

 {

     ll n;

     cin>>n;

     ll num1,num2;

     num1=_input(n);

     num2=_input(n);

     ll res=;

     res=(num1+num2)/;

     _output(res,n);

     cout<<endl;

     return ;

 }

 ll _input(ll n)

 {

     ll re=;

     char a;

     for(ll i=;i<n;i++)

     {

         cin>>a;

         re=re*+(a-'a');

     }

     return re;

 }

 void _output(ll res,ll n)

 {

     stack<char> qq;

     while(n--)

     {

         qq.push('a'+res%);

         res/=;

     }

     while(qq.size())

     {

         cout<<qq.top();

         qq.pop();

     }

 }

然后你就可以很快的wa了。

？？？

好吧，想着总不能爆掉我的unsigh long long 吧，然后打脸了。 26^10000,,,,随便爆。。

于是乎只能用数组模拟，一来可以方便的表示26进制，二来也可以表示很大的数据，爆不掉（除非非常非常变态了）

代码如下

 #include<bits/stdc++.h>

 using namespace std;

 int a[];

 int main()

 {

     int n;

     cin>>n;

     string c,b;//储存字符串

     cin>>c;

     cin>>b;

     for(int i=n-;i>=;i--)　　　　　　　//模拟加法

     {

         a[i+]+=c[i]-'a'+b[i]-'a';　　//从a[1]开始存，a[0]留着进位用。

         a[i]+=a[i+]/;　　　　　　　　//给高一位先进位

         a[i+]%=;　　　　　　　　　　　//当前位对26取模。

     }

     char e;
//模拟除法

     e='a';

     if(a[]>=)cout<<char(e+a[]/);　　

     if(a[]%!=)a[]+=;　　　　　　//看最高位是否存在进位的，如果存在，退回来。

     for(int i=;i<=n;i++)

     {

         e='a';

         cout<<char(e+a[i]/);　　　　//输出当前位除2所表示的数。

         if(a[i]%!=)a[i+]+=;　　//剩下的退回下一位。

     }

     cout<<endl;

     return ;

 }

Codeforces 1144 E. Median String的相关教程结束。