Aizu 2543
题意：给三个长度相等的串A，B，C，已知他们与原串的海明距离不大于d，要求还原出字典序最小的原串。
贪心。
对于原串S的每一位来说，有四种可能性：
S[i]=A
S[i]=A[i]
S[i]=B[i]
S[i]=C[i]
除此之外，三个串在第i位上有五种可能的相同：
A[i]，B[i]，C[i]互不相等
A[i]=B[i]
A[i]=C[i]
B[i]=C[i]
A[i]=B[i]=C[i]
分别设这五种情况的个数为tp[0..4]。
针对五种情况我们开始从前往后贪心：
注意到每一位的取舍没有前效性，我们只需要记录后缀的tp即可，每次贪心的选取字典序最小的可行解。
初始状态设三个串和原串的最大距离为dp[0..2]。
从小到大枚举当前位每一个可行字符，判断方法如下：
设
r[0]=dp[0]-tp[3]
r[1]=dp[1]-tp[2]
r[2]=dp[2]-tp[1]
得到r[0..2]即为第i个串经过这次决策后的最小值
显然每个值需要>=0。
然而由于三者互相约束，我们至多可以出现一个负数，这样是可以这个负数的影响消除的
1. 如果出现两个以上的负数，判断不合法
2. 由于存在tp[0]的情况，每次修改对三个串对原串的海明距离至少+2
显然需要成立：r[0]+r[1]+r[2]>=2*tp[0]
3. 每个修改至少对原串的海明距离+1
需要成立：r[0]+r[1]+r[2]-max(r) >= tp[0]
正确性显然。
综上，算法复杂度O(4*N)
#include <bits/stdc++.h>
using namespace std;
const int MAXN=100005;
char A[3][MAXN], ans[MAXN];
char v[MAXN][4];
int tp[5], dp[4], num[MAXN];
int n, d;
bool check(){for(int i=0; i<3; i++){if(dp[i]<0) return false;}int r[3]={dp[0]-tp[3],dp[1]-tp[2],dp[2]-tp[1]};int cnt=0;for(int i=0; i<3; i++) if(r[i]<0) cnt++;if(cnt>=2) return false;for(int i=0; i<3; i++) if(r[i]<0){for(int j=0; j<3; j++) if(i!=j){r[j]+=r[i];}r[i]=0;}cnt=0;for(int i=0; i<3; i++) if(r[i]<0) cnt++;if(cnt) return false;sort(r,r+3);return min((r[0]+r[1]+r[2])/2,r[0]+r[1])>=tp[0];
}
int main(){while(cin>>n>>d&&n){for(int i=0; i<3; i++){scanf("%s",A[i]);dp[i]=d;}memset(tp,0,sizeof tp);for(int i=0; i<n; i++){int s=0;for(int j=0; j<3; j++){for(int k=j+1; k<3; k++){if(A[j][i]==A[k][i]){s+=j+k;}}}s=min(s,4);num[i]=s; tp[s]++;v[i][0]='A';for(int j=0; j<3; j++){v[i][j+1]=A[j][i];}sort(v[i],v[i]+4);}for(int i=0; i<n; i++){tp[num[i]]--;for(int j=0; j<4; j++){for(int k=0; k<3; k++){if(A[k][i]!=v[i][j]){dp[k]--;}}if(check()){ans[i]=v[i][j];goto ok;}for(int k=0; k<3; k++){if(A[k][i]!=v[i][j]){dp[k]++;}}}puts("-1");goto failed;ok:;}ans[n]=0;puts(ans);failed:;}return 0;
}