有一个神话传说,说在很久以前,红色的守护者曾经来到人间,为了保护人们免受邪恶的侵害,他留下了一个强大的魔法。这个魔法被传说中的红宝石所承载,只有能够创造出特定数量回文子串的字符串才能够揭示出它的秘密。
简单构造题。
1.考虑放连续的一段相同字母,回文子串个数是C(n+1,2) 。
2.我们只需要按照r,d,e,r,d,e,...这样的顺序来放置连续的段,那么每个段之间就是独立的,即不会产生跨段的回文子串.
3.由于字符串长度有限制,x 又比较大,所以我们可以采取贪心的策略,每次放尽量长的相同段(这个过程可以二分),使得最终构造出来的段尽量小。
扫码备注加群即可,期待您的到来~