题意：
给一个字符串t ，求与这个序列刚好有m个位置字符不同的由两个相同的串拼接起来的字符串 s，
要求字典序最小的答案
分析：
把字符串折半，分成0 - n/2-1 和 n/2 - n-1
dp[i][j] 表示 第i位及之后的总代价为j可不可行
从第 n/2-1 位推回第 0 位， 若dp[0][m] = 1，则存在
然后贪心对每一位从'a'试到'z'，选取接下来存在解的字符
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <cstring>
using namespace std;
const int MAXN = ;
bool dp[MAXN][MAXN];//dp[i][j] ：第i位及之后的总代价为j可不可行
int t, n, m;
char s[MAXN];
int main()
{
scanf("%d", &t);
while (t--)
{
scanf("%d%d", &n, &m);
scanf("%s", s);
memset(dp, , sizeof(dp));
dp[n/][] = ;
for (int i = n/-; i >= ; i--)
{
if (s[i] == s[i+n/])
{
for (int j = ; j <= m; j++) dp[i][j] = dp[i+][j];//不改
for (int j = ; j <= m-; j++) if (dp[i+][j]) dp[i][j+] = ;//改两个
}
else
{
for (int j = ; j <= m-; j++) if (dp[i+][j]) dp[i][j+] = ;//改一个
for (int j = ; j <= m-; j++) if (dp[i+][j]) dp[i][j+] = ;//改两个
}
}
if (!dp[][m])
{
puts("Impossible"); continue;
}
int k = m;
for (int i = ; i < n/; i++)
{
for (int j = ; j < ; j++)
{
int p = ;
if (s[i] != j+'a') p++;
if (s[i+n/] != j+'a') p++;
if (dp[i+][k-p])
{
s[i] = j + 'a';
s[i+n/] = j + 'a';
k -= p;
break;
}
}
}
puts(s);
}
}