长度为 len 的相同字符连续段,其回文子串个数为 2len(len+1)(每一段连续子串都是回文)。若相邻两段使用不同字符,则不会产生跨段回文,总回文子串数等于各段贡献之和。
字符只有 r、e、d 三种,按 r,e,d,r,e,d,\ldots 轮流放置各段,即可保证相邻段字符不同。
由于 x 最大可达 109,而字符串长度不能超过 105,应尽量使用较长的段。每次贪心取最大的 len,使得 2len(len+1)≤ 剩余需求。实现上把需求乘 2,二分最大的 len 满足 len(len+1)≤ 剩余值,然后从剩余中减去该贡献,继续构造下一段。
需要构造一个仅由字符 r、e、d 组成的字符串 s,使得 s 中回文子串的个数恰好等于给定的正整数 x。
回文子串按起止位置计数:只要两个子串的左右端点不完全相同,即使内容相同也视为不同的回文子串。单字符一定是回文。
构造出的字符串长度不得超过 105。题目保证在此限制下一定存在合法构造。
约束条件:
r、e、d,长度不超过 105。
Scan the QR code below with WeChat to sign in
First-time scan will create your account automatically
请使用微信扫描下方二维码完成注册