UVA11027_Palindromic Permutation

此题不错。给你一些字字符，要求你用这些字符构成一个回文串，求字典序第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 ;

}

巴特西

UVA11027_Palindromic Permutation

最新文章

热门文章