01
先贴一个错误的贪心
Wrong answer on test 1
#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<cctype>
#include<cstring>
#include<cmath>
using namespace std;
#define _4v system("pause");
#define zsbd return 0;
int t, len, A_as, B_as, dif;
int last_moda, first_modc;
string str_A, str_B, str_C;
int main()
{
scanf("%d", &t);
str_C.reserve(12345678);
for (int cas = 1; cas <= t; ++cas)
{
printf("Case %d: ", cas);
cin >> str_A >> str_B;
len = str_A.length();
A_as = B_as = 0;
for (int i = 0; i < len; ++i)
{
str_C[i] = 'a';
A_as += (str_A[i] == 'a');
B_as += (str_B[i] == 'a');
}
if (A_as < B_as)
{
for (int i = 0; i < len; ++i) swap(str_A[i], str_B[i]);
swap(A_as, B_as);
}
dif = A_as - B_as;
int i = len;
last_moda = first_modc = 0;
while (dif)
{
--i;
if (str_A[i] == str_B[i] || str_B[i] == 'a') continue;
if (str_A[i] == 'a')
{
if (str_B[i] == 'b')
{
if (dif > 1)
{
str_C[i] = 'b';
dif -= 2;
if (!first_modc) first_modc = i;
continue;
}
else
{
str_C[i] = 'b';
if (first_modc)
{
if (str_B[first_modc] == 'b')
{
if (last_moda) str_C[last_moda] = 'a';
else str_C[first_modc] = 'c';
}
else
{
if (last_moda <= first_modc) str_C[last_moda] = 'a';
else str_C[first_modc] = 'b';
}
}
else
{
str_C[i] = 'c';
}
dif = 0;
}
}
else
{
if (dif > 1)
{
str_C[i] = str_B[i];
dif -= 2;
if (!first_modc) first_modc = i;
continue;
}
else
{
str_C[i] = 'b';
dif = 0;
}
}
}
else
{
str_C[i] = str_B[i];
--dif;
}
last_moda = i;
}
for (int i = 0; i < len; ++i)
{
putchar(str_C[i]);
}
putchar('
');
}
//
_4v zsbd
}
02
再给出一种错误的做法
这道题应该要做一点更加仔细的分类讨论
一开始先全部填上 a
考虑一下都有怎样的情况可以改变汉明距离差值
| A | B | |
|---|---|---|
| 1 | a | b |
| 2 | a | * |
| 3 | * | a |
| 4 | b | a |
| 5 | x | y |
(1) 变成c减一，变成b减二
(2) 变成b减一，变成*减二
(3) 变成b加一，变成*加二
(4) 变成c加一，变成b加二
(5) 变成x加一，变成y减一
那么实际上怎么做好一点呢
首先从后往前扫，尽量减二
最后一次假如刚好是减二而且差值不够用了
假如是情况2那不用多考虑直接变成减一
假如是情况1
那先变成减二，然后在这里停止，往后扫
对于第一个碰到的，属于情况 1~5 之内某一种的位置
如果把它修改后字典序将要变小的话：
1..假如第一个碰到的是之前减二过的就变成减一
2..假如是之前减一过的就变成减零
3..假如是之前没操作过的就给它加一。
（由于前面尽力减了，所以不可能说往后扫的时候加二减一加二减一。）
对于更换后会使字典序变大的操作，那就再从后往前扫一次，把最后面的那一个给换了。
如果这些情况都碰不到，那就直接把停住的那个位置从减二直接变成减一。
然而这也是错误的
我暂且把代码贴在这里，还没有对拍并且过不了
可能是我代码写错了也可能是这个办法行不通
Wrong answer on test 1
#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<cctype>
#include<cstring>
#include<cmath>
using namespace std;
int t;
string A, B, C;
int n, aA = 0, aB = 0, dif, cut = -1;
int main()
{
cin >> t;
C.resize(1919810);
for (int cas = 1; cas <= t; ++cas)
{
printf("Case %d: ", cas);
cin >> A >> B;
n = A.length();
aA = aB = 0;
cut = -1;
for (int i = 0; i < n; ++i)
{
C[i] = 'a';
aA += (A[i] == 'a');
aB += (B[i] == 'a');
}
if (aA < aB)
{
for (int i = 0; i < n; ++i) swap(A[i], B[i]);
swap(aA, aB);
}
dif = aA - aB;
for (int i = n - 1; i >= 0 && dif; --i)
{
if (A[i] == B[i] || B[i] == 'a') continue;
if (A[i] == 'a')
{
if (B[i] == 'b')
{
if (dif > 1)
{
C[i] = 'b';
dif -= 2;
}
else
{
cut = i;
C[i] = 'b';
dif = 0;
}
}
else
{
if (dif > 1)
{
C[i] = B[i];
dif -= 2;
}
else
{
C[i] = 'b';
dif = 0;
}
}
continue;
}
C[i] = B[i];
--dif;
}
if (cut >= 0)
{
bool suc = false;
for (int i = cut + 1; i < n; ++i)
{
if (A[i] == B[i]) continue;
if (A[i] == 'a')
{
// -2 to -1
if (B[i] == 'b') C[i] = 'c';
else continue;
}
else if (B[i] == 'a')
{
// 0 to +1
continue;
}
else
{
// -1 to 0
C[i] = 'a';
}
suc = true;
break;
}
if (!suc)
for (int i = n - 1; i > cut; --i)
{
if (A[i] == B[i]) continue;
if (A[i] == 'a')
{
// -2 to -1
if (B[i] == 'b') C[i] = 'c';
else continue;
}
else if (B[i] == 'a')
{
// 0 to +1
C[i] = (A[i] == 'b') ? 'c' : 'b';
}
else
{
// -1 to 0
continue;
}
suc = true;
break;
}
if (!suc)
{
C[cut] = 'c';
}
}
for (int i = 0; i < n; ++i)
{
putchar(C[i]);
}
putchar('
');
}
//
// system("pause");
return 0;
}
03
换一种思路，一开始不要先全部填 a
为啥？
假如不确定的话，新填一个数最多只会让汉明距离差值变化 ±1
先填上 a 没有任何意义还可能让这种变化变大，反正就是更麻烦了
。。。
所以，记录一下往后有多少个位置两串的字符不同
一边走一边数一数现在到两串汉明距离的差有多大了，控制一下。
如果没有问题就直接a
α:
#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<cctype>
#include<cstring>
#include<cmath>
using namespace std;
int t;
string A, B, C;
int len, cur_dif;
int sum[10010];
char ch;
char lower(const char &a, const char &b)
{
for (char t = 'a'; t <= 'z'; ++t)
{
if (t != a && t != b) return t;
}
}
int main()
{
cin >> t;
C.resize(1919810);
for (int cas = 1; cas <= t; ++cas)
{
printf("Case %d: ", cas);
cin >> A >> B;
len = A.length();
sum[len] = cur_dif = 0;
for (int i = len - 1; i >= 0; --i)
{
sum[i] = sum[i + 1] + (A[i] != B[i]);
}
for (int i = 0; i < len; ++i)
{
if (A[i] == B[i])
{
C[i] = 'a';
continue;
}
if (abs(cur_dif) < sum[i + 1])
{
C[i] = 'a';
if (A[i] == 'a') ++cur_dif;
if (B[i] == 'a') --cur_dif;
}
else
{
ch = lower(A[i], B[i]);
if (!cur_dif) C[i] = ch;
else if (cur_dif > 0)
{
if (ch < B[i] && cur_dif == sum[i + 1]) C[i] = ch;
else C[i] = B[i], --cur_dif;
}
else
{
if (ch < A[i] && cur_dif == -sum[i + 1]) C[i] = ch;
else C[i] = A[i], ++cur_dif;
}
}
}
for (int i = 0; i < len; ++i) putchar(C[i]);
putchar('
');
}
//
// system("pause");
return 0;
}