codeforces979B.TreasureHunt(模拟，字符替换)

题目&＃xff1a;http://codeforces.com/contest/979/problem/B

题意&＃xff1a;有三个字符串&＃xff0c;字符代表颜色&＃xff0c;要求分别对每个字符串必须修改字符n次&＃xff0c;使得最后自己串中相同的字符能达到最多。求经过n次修改&＃xff0c;这三个字符串中相同字符最多的是哪一串&＃xff1f;或是平局&＃xff08;最多的串>&＃61;2个&＃xff09;

思路&＃xff1a;字符串中的字符自然是最终都要往出现最多的那个字符的方向化的

直接从WA点开始讲&＃xff1a;

1. 修改的这n次是必须要用完的 "Every turn" "must change strictly one color"  (WA5)

2.等到所有字符都化成相同的以后&＃xff0c;还有剩余的次数时&＃xff0c;最佳方案并不一定是在一个字符上来回地变换(a->b->a->b...)&＃xff0c;偶数这样可以&＃xff0c;若奇数也是可以最后化到原来颜色的(如: a   ->b->c->a)   (WA6  (下面数据放的是86,95  都是同一种))

3.接第2条&＃xff0c;剩余次数是奇数时也有化不到原来颜色的情况&＃xff1a;字符串最初时就完全同色&＃xff0c;但修改次数n为1时

所以综合 2&＃xff0c;3条 也就有了

if(mx[i]else mx[i]&＃61;len-(n&＃61;&＃61;1); //这个else就是(只)指mx[i]&＃61;&＃61;len这种情况了

#include
#pragma GCC optimize(3)
//#pragma GCC optimize("unroll-loops")
//#pragma comment(linker, "/stack:200000000")
//#pragma GCC optimize("Ofast,no-stack-protector")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune&＃61;native")
#define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define pb push_back
#define mkp(a,b) make_pair(a,b)
#define PII pair
#define PLL pair
#define fi first
#define se second
#define lc (d<<1) //d*2
#define rc (d<<1|1) //d*2&＃43;1
#define eps 1e-9
#define dbg(x) cerr <<#x <<" &＃61; " <#define mst(a,val) memset(a,val,sizeof(a))
#define stn(a) setprecision(a)//小数总有效位数
#define stfl setiosflags(ios::fixed)//点后位数:cout<using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const double PI&＃61;3.1415926535897932;
const int MAXN&＃61;1e5&＃43;10;
const ll mod&＃61;1e9&＃43;7;
ll inline mpow(ll a,ll b){ll ans&＃61;1;a%&＃61;mod;while(b){if(b&1)ans&＃61;(ans*a)%mod;a&＃61;(a*a)%mod,b>>&＃61;1;}return ans;}
int inline sgn(double x){return (x>-eps)-(xpriority_queue,greater > qu; //up
priority_queue,less > qd; //dn
const int inf &＃61; 0x3f3f3f3f; //9
const ll inff &＃61; 0x3f3f3f3f3f3f3f3f; //18int n;
char s[10][100010];
mapmp[10];
int mx[10];int main()
{fio;cin>>n;for(int i&＃61;0;i<3;i&＃43;&＃43;) cin>>s[i];int len&＃61;strlen(s[0]);for(int i&＃61;0;i<3;i&＃43;&＃43;){int tmp&＃61;0;for(int j&＃61;0;jmx[1]&&mx[0]>mx[2]) {cout<<"Kuro"<mx[0]&&mx[1]>mx[2]) {cout<<"Shiro"<mx[0]&&mx[2]>mx[1]) {cout<<"Katie"<}/*
//5:
1
aaaaaaaaaa
AAAAAAcAAA
bbbbbbzzbb
//me: Draw
//answer:Shiro//86:
3
aaaaa
aaaaa
aaaab
//my:Katie
//answer:Draw//95:
4
aaaabcd
aaaabcd
aaaaaaa
//my:Katie
//answer:Draw
*/