Square Distance
Accepts: 73
Submissions: 598
Time Limit: 4000/2000 MS (Java/Others)
Memory Limit: 65536/65536 K (Java/Others)
问题描述
一个字符串被称为square当且仅当它可以由两个相同的串连接而成. 例如, "abab", "aa"是square, 而"aaa", "abba"不是. 两个长度相同字符串之间的hamming distance是对应位置上字符不同的位数. Alex有个偶数长度的字符串ss1s2...sns=s1s2...sn. 他想要找到一个字典序最小的square tt1t2...tnt=t1t2...tn 使得ss和tt之间的hamming distance恰好是mm. 另外, ss和tt仅包含小写英文字母.
输入描述
输入包含多组数据, 第一行包含一个整数TT 1T500(1≤T≤500)表示测试数据组数. 对于每组数据: 第一行包含两个整数nn和mm 1n10000mnn(1≤n≤1000,0≤m≤n,n is even)表示字符串的长度和hamming distance. 第二行包含一个字符串ss.
输出描述
对于每组数据, 如果不存在这样的一个square, 输出"Impossible" (不包含引号). 否则, 输出字典序最小的square.
输入样例
3
4 1
abcd
4 2
abcd
4 2
abab
输出样例
Impossible
abab
aaaa
因为要字典序最小打印，所以倒着保存状态
f[i][j]表示i到n/2且hamming distance为j是否可行
DP一遍之后贪心从头开始选择就行了
//
// main.cpp
// bc87-1002
//
// Created by Candy on 10/1/16.
// Copyright © 2016 Candy. All rights reserved.
// #include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
#include <string>
using namespace std;
const int N=,V=1e6+;
inline int read(){
char c=getchar();int x=,f=;
while(c<''||c>''){if(c=='-')f=-;c=getchar();}
while(c>=''&&c<=''){x=x*+c-'';c=getchar();}
return x;
}
int T,n,m,l,d[N][N];//dao xu
char s[N],t[N];
void dp(){
memset(d,,sizeof(d));
d[l+][]=;
for(int i=l;i>=;i--)
for(int j=;j<=m;j++){
if(s[i]==s[i+l]) {
d[i][j]|=d[i+][j];
if(j>=) d[i][j]|=d[i+][j-];
}else{
if(j>=) d[i][j]|=d[i+][j-];
if(j>=) d[i][j]|=d[i+][j-];
}
//printf("d %d %d %d\n",i,j,d[i][j]);
}
if(!d[][m]){printf("Impossible\n");return;}
int res=m;
for(int i=;i<=l;i++)
for(int k=;k<;k++){
int tmp=(s[i]-'a'!=k)+(s[i+l]-'a'!=k);
if(d[i+][res-tmp]){
t[i]=t[i+l]=k+'a';
res-=tmp;
break;
}
}
for(int i=;i<=n;i++) putchar(t[i]);
putchar('\n');
}
int main(int argc, const char * argv[]) {
T=read();
while(T--){
n=read();m=read(); l=n/;
scanf("%s",s+);
dp();
}
return ;
}