Codeforce 1144 E. Median String 解析(思維、大數運算)
今天我們來看看CF1144E
題目連結
題目
給你兩個長度為\(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
