此题不错。给你一些字字符,要求你用这些字符构成一个回文串,求字典序第k大的回文串。

首先通过给定的字符,我们可以直接判断能否构成回文串(奇数的字符不超过一种),其次可以统计每个字符在回文串的左边应该出现多少次。

然后从左到右判断每一位应该放那个字母,一边放置一遍更新即可。

我仅判断奇数次的个数为奇偶就ac了,输出的时候只输出了一个,如果有三个呢? 哈哈, 数据太水了。

召唤代码君:

#include <iostream>
#include <cstdio>
#include <cstring>
typedef long long ll;
using namespace std; int t[],c[],n,T,cas=,tot,pos;
char s[],ans[];
ll P[];
bool flag; ll count()
{
ll sum=,cur=;
for (int i=; i<; i++)
sum+=t[i],cur*=P[t[i]];
return P[sum]/cur;
} int main()
{
P[]=;
for (int i=; i<; i++) P[i]=P[i-]*i;
scanf("%d",&T);
while (T--)
{
flag=true;
scanf("%s%d",s,&n);
memset(t,,sizeof t);
pos=-;
tot=;
for (int i=; s[i]; i++) t[s[i]-'a']++;
for (int i=; i<; t[i]/=,tot+=t[i],i++)
if (t[i]&)
{
if (pos==-) pos=i;
else flag=false;
}
printf("Case %d: ",++cas);
if (!flag || count()<n)
{
puts("XXX");
continue;
}
for (int i=; i<=tot; i++)
{ for (int j=; j<; j++)
{
if (t[j]<=) continue;
t[j]--;
ll tmp=count();
if (n<=tmp)
{
c[i]=j+'a';
break;
}
t[j]++,n-=tmp;
}
}
for (int i=; i<=tot; i++) printf("%c",c[i]);
if (pos!=-) printf("%c",(char)('a'+pos));
for (int i=tot; i>=; i--) printf("%c",c[i]);
printf("\n");
}
return ;
}
05-11 11:15
查看更多