学军中学图灵杯趣味编程邀请赛题解 —— B. 回文串

题目相关

问题描述

zzq写了一个程序，可以输出一个字符串中的回文子串个数。一个串回文是指它正着读和反着读相同，一个串的子串为该串一个连续的部分，相同的回文子串在多个地方出现计算多次。
今天，他想让你给出一个长度不超过 333 的仅包含小写字母的字符串，使得程序的输出恰好为 m，即其中恰包含 m 个回文子串。
一个输入中可能包含多组数据。

输入格式

第一行一个正整数 T，表示数据组数。
接下来 T 行每行一个正整数 m。

输出格式

对于每组数据输出一行，一个满足题意的字符串。

样例输入

2
3
17

样例输出

aa
qaqqwqqaq

正确的输出可能不唯一。

数据范围

对于所有数据， 。
Subtask 1（50pts）：存在正整数 k 使得 m=k*(k-1)/2。
Subtask 2（10pts）：。
Subtask 3（20pts）：。
Subtask 4（20pts）：。

题解报告

本次图灵杯举行于

题目分析

首先，看一下回文子串。样例数据 aa 的回文子串有几个，我们可以写出：a(第一个字母), a(第二个字母), aa，这样构成了 3 个回文子串，也就是 个，其中 n 为字符串的长度。

其次，根据题目，我们知道最大的字符串长度为 333，根据上面的推论，假设这 333 个字符串都是由字母 a 构成，这样可以得到最多的回文子串。这个最大值为 ，也就是说大于题目的 m 的最大值 23333。

我们可以使用 26 个小写英文字母 a ~ z 来构成字符串，因此我们可以使用贪心的思路来完成。也就是先用当个 a 构成最大的组，后面不够的使用单个字符来补充。

下面我们将问题转换为如何确定用自己字母 a 构成拥有最多回文子串的字符串，这个也简单，我们可以通过打表法，也就是说，先写出长度由 0 ~ 333 个单字母 a 构成的字符串能组成的回文子串的数目。这样问题就变成一个查表问题，为了提供查表速度，我们可以使用二分查找下界即可。

这样本题通过 打表 + 二分 + 贪心 来解决。下面我们使用样例数据来验证一下思路是否可行。

样例数据

样例数据 1

m=3。我们给出部分打表的值，v[0]=0，v[1]=1，v[2]=3，v[3]=6。这样我们通过查表找到了 v[2]=3 这里，意思是使用 2 个相同字符可以获得 3 个回文子串。因此我们只需要构造 aa 即可。符合答案。

样例数据 2

m=17，我们给出部分打表的值，v[0]=0，v[1]=1，v[2]=3，v[3]=6，v[4]=10，v[5]=15，v[6]=21。这样我们通过查表找到了 v[6]=21 这里，使用的 STL lower_bounder() 函数。将这个位置减一才是答案 v[5]=15，意思就是使用 5 个相同字符可以获得 15 个回文子串。还有 17-15=2 个回文子串需要构造。因此我们选择下一个字符 b 来构造一个回文子串，再选择下一个字符 c 来构造一个回文子串。最终构造的字符串为 aaaaabc。下面我们来验证一下是否是 17 个。

长度为 1 的回文子串有：a, a, a, a, a, b, c。这里有 7 个。

长度为 2 的回文子串有：aa, aa, aa, aa。这里有 4 个。

长度为 3 的回文子串有：aaa, aaa, aaa。这里有 3 个。

长度为 4 的回文子串有：aaaa, aaaa。这里有 2个。

长度为 5 的回文子串有：aaaaa。这里有 1 个。

一共有 7+4+3+2+1=17 个。符合题目要求。

AC 参考代码

//学军中学图灵杯 B 题
#include <bits/stdc++.h>

using namespace std;

//如果提交到OJ，不要定义 __LOCAL
#define __LOCAL

typedef long long LL;

int main() {
#ifndef __LOCAL
    //这部分代码需要提交到OJ，本地调试不使用
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
#endif
    //打表
    vector<int> v;
    v.push_back(0);
    for (int i=1; i<=333; i++) {
        v.push_back(v[i-1]+i);
    }

    int t;
    cin>>t;

    while (t) {
        char ch='a';//构造的字符
        int m;
        cin>>m;

        //二分查找
        int pos=lower_bound(v.begin(), v.end(), m)-v.begin();
        if (v[pos]!=m) {
            pos--;
        }

        //构造字符串
        string ans(pos, ch);
        ch++;
        cout<<ans;

        m -= v[pos];
        //后面的字符串都用单字符构成
        for (int i=0; i<m; i++) {
            cout<<ch;
            ch++;
        }
        cout<<"\n";

        t--;
    }

#ifdef __LOCAL
    //这部分代码不需要提交到OJ，本地调试使用
    system("pause");
#endif
    return 0;
}

时间复杂度

。

空间复杂度

O(1)。