2018 北京区域赛 I - Palindromes （找规律）

题目

HihoCoder - 1878

题目大意

给出k，让求出第k个回文数（k的“长度”不超过1e5）

题解

之前做过类似的题，是统计各阶段的数找到第K个回文数，但这里K太大，需要寻找新的方法。

打表找规律：

只有一位数：减一输出

否则：

若第0位为2~9 ：首位减一，0~len-2反转贴后面

若第0位为1：若第1位为1~9：丢掉首位，剩下的反转贴后面

若第1位为0：丢掉首位，第1位改成9，2~len-2反转贴后面.

AC代码

#include<cstdio>

#include<iostream>

#include<string>

#include<sstream>

using namespace std;

void solve(string str)

{

    int len = str.length();

    if (len == )

    {

        printf("%c\n", str[] - );

        return;

    }

    if (str[] == '')

    {

        if (str[] == '')

        {

            str[] = '';

            for (int i = ; i < len; i++)  printf("%c", str[i]);

            for (int i = len - ; i >= ; i--)  printf("%c", str[i]);

            printf("\n");

        }

        else

        {

            for (int i = ; i < len; i++)  printf("%c", str[i]);

            for (int i = len - ; i >= ; i--)  printf("%c", str[i]);

            printf("\n");

        }

    }

    else

    {

        str[] = str[] - ;

        for (int i = ; i < len; i++)  printf("%c", str[i]);

        for (int i = len - ; i >= ; i--)  printf("%c", str[i]);

        printf("\n");

    }

}

int main()

{

    int T;

    scanf("%d", &T);

    while (T--)

    {

        string str;

        cin >> str;

        solve(str);

    }

}

打表程序

#include<cstdio>

#include<iostream>

#include<sstream>

#include<string>

using namespace std;

typedef long long LL;

const LL maxn = 1e18;

void ToString(LL num, string& str)

{

    stringstream ss;

    ss << num;

    ss >> str;

}

bool ispd(string str)

{

    bool flag = true;

    int len = str.length();

    for (int i = ; i < len / ; i++)

        if (str[i] != str[len -  - i])  flag = false;

    return flag;

}

int main()

{

    LL cnt = ;

    for (LL i = ; i < maxn; i++)

    {

        string s;

        ToString(i, s);

        if (ispd(s))  cout << cnt++ << ' ' << i << endl;

    }

    return ;

}

参考链接：https://blog.csdn.net/hxxjxw/article/details/84205963

巴特西

2018 北京区域赛 I - Palindromes （找规律）

题目

题目大意

题解

AC代码

打表程序

最新文章

热门文章