---
title: Codeforce 1144 E. Median String 解析(思維、大數運算)
description: "Codeforce 1144 E. Median String 解析(思維、大數運算)"
disqus: hackmd
---
<meta name="robots" content="Codeforce 1144 E. Median String 解析(思維、大數運算)">
<!-- toc -->

# Codeforce 1144 E. Median String 解析(思維、大數運算)
今天我們來看看CF1144E
[題目連結](https://codeforces.com/problemset/problem/1144/E)

> **題目**
給你兩個長度為$k$的字串$s$和$t$，求字典序排序的，$s,t$的中位字串。

### 前言

### 想法
觀察一下，發現我們可以把字串看成26進位的數字，所以我們只要計算$(s+t)/2$就好。

### 程式碼:

const int _n=2e5+10;
int tt,k,inc,z,left;
char s[_n],t[_n],res[_n];
main(void) {ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  cin>>k>>(s+1)>>(t+1); rep(i,1,k+1)s[i]-='a',t[i]-='a';
  per(i,1,k+1)res[i]=(s[i]+t[i]+inc)%26,inc=((s[i]+t[i]+inc)/26)?1:0;
  z=inc; res[0]=inc;
  rep(i,0,k+1){
    tt=res[i],res[i]=(left*26+res[i])/2,left=(left*26+tt)%2;
  }rep(i,1,k+1)cout<<(char)('a'+res[i]); cout<<'\n';
  return 0;
}

(才發現$z$這個變數其實沒用到)
標頭、模板請點Submission看
[Submission](https://codeforces.com/contest/1144/submission/90532896)