生活随笔
收集整理的這篇文章主要介紹了
hdu 5903 Square Distance
小編覺得挺不錯(cuò)的,現(xiàn)在分享給大家,幫大家做個(gè)參考.
這題題解dp不懂 因?yàn)椴恢浪趺从涗沝p的答案的 字符串那么長
我是貪心過得,當(dāng)時(shí)還被四個(gè)人hack,都沒成功,hhhhh
大意就是優(yōu)先從頭取字典序小的字母,擔(dān)也要讓后面不管怎么取都合法
using namespace std;
const
int INF =
0x3f3f3f3f;
const
int MAXN =
1e3+
5;
int N,M;
char S[MAXN];
char ans[MAXN];
int tg[MAXN];
int ju(
int x,
int y,
int c) {
// printf(
"%d %d %d\n",
x,
y,c);
if(c <
0)
return 0;
if(
x ==
0) {
if(c
%2 || c >
y*2)
return 0;}
else if(c > (
x+
y)
*2 || c <
x)
return 0;
// printf(
"got\n");
return 1;
}
int main(){
int T; scanf(
"%d",&T);
while(T--) {scanf(
"%d %d",&N,&M);scanf(
"%s",S+
1);
int c1 =
0;
int c2 =
0;
for(
int i =
1; i <= N/
2; ++i) {
if(S[i] > S[i+N/
2]) swap(S[i], S[i+N/
2]);
if(S[i] != S[i+N/
2]) tg[i] =
1, c1 ++;
else tg[i] =
2, c2 ++;}
if(c1==
0) {
if(M
%2 || M>c2
*2) {
printf(
"Impossible\n");
continue;}}
else if(M > (c2+c1)
*2 || M < c1) {
printf(
"Impossible\n");
continue;}
for(
int i =
1; i <= N/
2; ++i) {char t1= S[i]; char t2= S[i+N/
2];
if(tg[i] ==
1) {
if(t1 ==
'a') {
if(ju(c1-
1,c2,M-
1)) ans[i] =
'a', M--;
else {
if(t2 ==
'b') ans[i] =
'c', M-=
2;
else ans[i] =
'b', M-=
2;}}
else {
if(ju(c1-
1,c2,M-
2)) ans[i] =
'a', M-=
2;
else ans[i] = min(t1,t2), M--;}c1--;}
else {
if(t1 ==
'a'){
if(ju(c1,c2-
1,M)) ans[i] =
'a';
else ans[i] =
'b', M-=
2;}
else {
if(ju(c1,c2-
1,M-
2)) ans[i] =
'a', M-=
2;
else ans[i] = t1;}c2--;} }
for(
int i =
0; i <
2; ++i)
for(
int j =
1; j <= N/
2; ++j)
printf(
"%c",ans[j]);
printf(
"\n");}
return 0;
}
轉(zhuǎn)載于:https://www.cnblogs.com/Basasuya/p/8433747.html
總結(jié)
以上是生活随笔為你收集整理的hdu 5903 Square Distance的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。
