# HDU 5903 Square Distance

$dp$预处理，贪心。

#pragma comment(linker, "/STACK:1024000000,1024000000")
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<vector>
#include<map>
#include<set>
#include<queue>
#include<stack>
#include<bitset>
#include<iostream>
using namespace std;
typedef long long LL;
const double pi=acos(-1.0),eps=1e-6;
void File()
{
freopen("D:\\in.txt","r",stdin);
freopen("D:\\out.txt","w",stdout);
}
template <class T>
{
char c=getchar(); x=0;
while(!isdigit(c)) c=getchar();
while(isdigit(c)) {x=x*10+c-‘0‘; c=getchar();}
}

const int maxn=1010;
char s[maxn],ans[maxn];
int T,n,m;
int a[maxn],b[maxn];
bool dp[510][maxn];

int main()
{
scanf("%d",&T);
while(T--)
{
memset(dp,0,sizeof dp);
scanf("%d%d",&n,&m);

scanf("%s",s);

for(int i=1;i<=n/2;i++) a[i]=s[i-1]-‘a‘+1;
for(int i=n/2;i<=n-1;i++) b[i-n/2+1]=s[i]-‘a‘+1;

dp[n/2+1][0]=1;
for(int i=n/2;i>=1;i--)
{
if(a[i]==b[i])
{
for(int j=0;j<=1000;j++) dp[i][j]=dp[i+1][j];
for(int j=0;j<=1000;j++) if(dp[i+1][j]==1&&j+2<=1000) dp[i][j+2]=1;
}

else
{
for(int j=0;j<=1000;j++)
{
if(dp[i+1][j]==1)
{
if(j+1<=1000) dp[i][j+1]=1;
if(j+2<=1000) dp[i][j+2]=1;
}
}
}
}

bool fail=0; int z=m;
for(int i=1;i<=n/2;i++)
{
bool xx=1;
for(int j=1;j<=26;j++)
{
int num=0;
if(a[i]!=j) num++; if(b[i]!=j) num++;

if(z-num<0) continue;
if(dp[i+1][z-num])
{
ans[i]=j;
xx=0; z=z-num; break;
}
}
if(xx==1) fail=1;
if(fail==1) break;
}

if(fail) printf("Impossible\n");
else
{
for(int i=1;i<=n/2;i++) printf("%c",ans[i]-1+‘a‘);
for(int i=1;i<=n/2;i++) printf("%c",ans[i]-1+‘a‘);
printf("\n");
}
}
return 0;
}

## hdu 5903 Square Distance(dp)

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 distanc

## hdu 1398 Square Coins（母函数|完全背包）

http://acm.hdu.edu.cn/showproblem.php?pid=1398 题意:有价值为1^2,2^2....7^2的硬币共17种,每种硬币都有无限个.问用这些硬币能够组成价值为n的钱数共有几种方案数. 母函数: #include <stdio.h> #include <iostream> #include <map> #include <set> #include <stack> #include <vector>

## hdu 1518 Square （dfs搜索可参考poj1011）

Square Time Limit: 10000/5000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 8589    Accepted Submission(s): 2784 Problem Description Given a set of sticks of various lengths, is it possible to join them end-to-end

## HDU 1398 Square Coins

http://acm.hdu.edu.cn/showproblem.php?pid=1398 大概像是01背包 #include<bits/stdc++.h> using namespace std; const int maxn = 400; int dp[maxn]; int s[maxn]; void init() { memset(dp,0,sizeof(dp)); } int main () { int n; for(int i=1;i<=17;i++) s[i] = i*i;

## HDU 4712 Hamming Distance (随机函数)

Hamming Distance Time Limit: 6000/3000 MS (Java/Others)    Memory Limit: 65535/65535 K (Java/Others)Total Submission(s): 1806    Accepted Submission(s): 714 Problem Description (From wikipedia) For binary strings a and b the Hamming distance is equal

## hdu 1518 Square

Problem Description Given a set of sticks of various lengths, is it possible to join them end-to-end to form a square? Input The first line of input contains N, the number of test cases. Each test case begins with an integer 4 <= M <= 20, the number

## hdu 1398 Square Coins（生成函数，完全背包）

pid=1398">链接:hdu 1398 题意:有17种货币,面额分别为i*i(1<=i<=17),都为无限张. 给定一个值n(n<=300),求用上述货币能使价值总和为n的方案数 分析:这题能够用母函数的思想,对300以内的值进行预处理就可以 也可用全然背包思想求300以内的方案数 母函数: #include<stdio.h> int main() { int c1[305],c2[305],i,j,k,n; for(i=0;i<=300;i++){