题目相关

问题描述

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 __LOCALtypedef 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;while (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];     }cout<<"\n";t--;}#ifdef __LOCAL//这部分代码不需要提交到OJ，本地调试使用system("pause");
#endifreturn 0;
}

时间复杂度

。

空间复杂度

O(1)。