链接:

题意:

Por Costel the pig, our programmer in-training, has recently returned from the Petrozaporksk training camp. There, he learned a lot of things: how to boil a cob, how to scratch his belly using his keyboard, etc... He almost remembers a programming problem too:

A semipalindrome is a word for which there exists a subword such that is a prefix of and (reverse ) is a suffix of . For example, 'ababba' is a semipalindrom because the subword 'ab' is prefix of 'ababba' and 'ba' is suffix of 'ababba'.

Let's consider only semipalindromes that contain letters 'a' and 'b'. You have to find the -th lexicographical semipalindrome of length .

Por Costel doesn't remember if the statement was exactly like this at Petrozaporksk, but he finds this problem interesting enough and needs your help to solve it.

思路:

考虑首字母等于末字母,中间按字典序处理即可,字典序处理可用二进制的思想.

aaa = 000, aab = 001, aba == 010, 就是挨个进位,注意,第k小在字典序的二进制中是k-1, 因为aaa = 000,从0开始.

代码:

#include <iostream>

#include <cstdio>

#include <cstring>

#include <vector>

//#include <memory.h>

#include <queue>

#include <set>

#include <map>

#include <algorithm>

#include <math.h>

#include <stack>

#include <string>

#include <assert.h>

#include <iomanip>

#define MINF 0x3f3f3f3f

using namespace std;

typedef long long LL;

map<string, double> Sc;

const int MAXN = 1e3+10;

char s[100];

LL n, k;

//aaaa, aaba, abaa, abba, baba,

int main()

{

    freopen("semipal.in", "r", stdin);

    freopen("semipal.out", "w", stdout);

    ios::sync_with_stdio(false);

    cin.tie(0);

    int t;

    cin >> t;

    while (t--)

    {

        cin >> n >> k;

        if (k > 1LL<<(n-2))

        {

            k -= 1LL<<(n-2);

            k--;

            s[0] = 'b';

            s[n-1] = 'b';

            for (int i = n-2;i >= 1;i--)

            {

                if (k%2 == 0)

                    s[i] = 'a';

                else

                    s[i] = 'b';

                k /= 2;

            }

        }

        else

        {

            s[0] = 'a';

            s[n-1] = 'a';

            k--;

            for (int i = n-2;i >= 1;i--)

            {

                if (k%2 == 0)

                    s[i] = 'a';

                else

                    s[i] = 'b';

                k /= 2;

            }

        }

        s[n] = 0;

        cout << s << endl;

    }

    return 0;

}

巴特西

Gym-100923L-Por Costel and the Semipalindromes(进制转换,数学)

链接:

题意:

思路:

代码:

最新文章

热门文章