hdoj-5903 Square Distance

原题链接

Square Distance

Time Limit: 4000/2000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 245    Accepted Submission(s): 83

Problem Description

A string is called a square string if it can be obtained by concatenating two copies of the same string. For example, "abab", "aa" are square strings, while "aaa", "abba" are not.

Hamming distance between two strings of equal length is the number of positions at which the corresponding symbols are different.

Peter has a string s=s1s2...sn of even length. He wants to find a lexicographically smallest square string t=t1t2...tn that the hamming distance between s and tis exact m. In addition, both s and t

Input

There are multiple test cases. The first line of input contains an integer T, indicating the number of test cases. For each test case:

The first contains two integers n and m (1≤n≤1000,0≤m≤n,n is even) -- the length of the string and the hamming distance. The second line contains the string s.

Output

For each test case, if there is no such square string, output "Impossible" (without the quotes). Otherwise, output the lexicographically smallest square string.

Sample Input

3 4 1 abcd 4 2 abcd 4 2 abab

Sample Output

Impossible abab aaaa

dp[i][j]表示第i个字符到n/2个字符以及i+n/2到n个字符与原字符串之间的距离是否能为j

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#define maxn 100005
using namespace std;
typedef long long ll;

char str[1005];
int dp[505][1005];
int main(){
	
	//freopen("in.txt", "r", stdin);
	int t;
	
	scanf("%d", &t);
	while(t--){
		int n, m;
		scanf("%d%d%s", &n, &m, str+1);
		memset(dp, 0, sizeof(dp));
		dp[n/2+1][0] = 1;
		for(int i = n/2; i > 0; i--){
			if(str[i] == str[i+n/2]){
				for(int j = 0; j <= m; j++)
				 dp[i][j] = dp[i+1][j];
				for(int j = 0; j <= m-2; j++){
					if(dp[i+1][j])
					 dp[i][j+2] = 1;
				}
			}
			else{
				for(int j = 0; j <= m-1; j++)
				 dp[i][j+1] = dp[i+1][j];
				for(int j = 0; j <= m-2; j++)
				 if(dp[i+1][j])
				  dp[i][j+2] = 1;
			}
		}
		if(dp[1][m] == 0)
		 puts("Impossible");
		else{
			int k = m;
			for(int i = 1; i <= n/2; i++){
				for(int j = 0; j <= 25; j++){
					int p = 0;
					if(str[i] != j + 'a')
					  p++;
					if(str[i+n/2] != j + 'a')
					 p++;
			       
					if(dp[i+1][k-p]){
						str[i] = str[i+n/2] = j + 'a';
						k -= p;
						break;
					}
				}
			}
			puts(str+1);
		}
	}
	return 0;
}