题目思路

简单构造题。

1.考虑放连续的一段相同字母，回文子串个数是$C(n+1,2)$ 。

2.我们只需要按照r,d,e,r,d,e,...这样的顺序来放置连续的段，那么每个段之间就是独立的，即不会产生跨段的回文子串.

3.由于字符串长度有限制，$x$ 又比较大，所以我们可以采取贪心的策略，每次放尽量长的相同段(这个过程可以二分),使得最终构造出来的段尽量小。

例如:14

那么第一个段就放:rrrr

第二段放:ee

第三段放:d

最终:rrrreed

例如:15

那么第一个段就放:rrrrr 结束

代码

C++代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll getMinNum(ll tar){//通过二分找到最大的小于n的x*x+x
	ll L = 1, R = (ll)1e5, ans = -1;
	while(L <= R){
		ll mid = (L + R) / 2;
		if (mid * mid + mid <= tar){
            ans = mid;
            L = mid + 1;
        }else{
            R = mid - 1;
        }
	}
	return ans;
}
int main(){
	ll n;
	cin >> n;
	n = n * 2L;//放大两倍，好比较
	char ch[3] = {'r', 'e', 'd'};//思路就是三个轮流选
	string str = "";
	int now = 0;
	while(n > 0){
		ll val = getMinNum(n);//找到最大的那个数
		n -= val * val + val;//n减去这个值，因为x个相同字符拼起来，包含回文字串为x(x + 1)/2个，我们的n已经放大两倍，所以字串数量也放大两倍，所以就不用除2了
        for(int j = 0; j < val; j++){
            str += ch[now];//将val个字符加入答案
        }
        now = (now + 1) % 3;//轮流选
	}
	cout << str << endl;
}

Java代码

import java.util.Scanner;

public class redConstructor {
    public static long getMinNum(long tar){//通过二分找到最大的小于n的x*x+x
        long L = 1;
        long R = (long)1e5;
        long ans = -1;
        while(L <= R){
            long mid = (L + R) / 2;
            if (mid * mid + mid <= tar){
                ans = mid;
                L = mid + 1;
            }else{
                R = mid - 1;
            }
        }
        return ans;
    }
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        long n = in.nextLong();
        n = n * 2L;//放大两倍，好比较
        StringBuilder sb = new StringBuilder();
        char[] ch = new char[]{'r','e','d'};//思路就是三个轮流选
        int now = 0;
        while(n > 0){
            long val = getMinNum(n);//找到最大的那个数
            n -= val * val + val;//n减去这个值，因为x个相同字符拼起来，包含回文字串为x(x + 1)/2个，我们的n已经放大两倍，所以字串数量也放大两倍，所以就不用除2了
            for(int j = 0; j < val; j++){
                sb.append(ch[now]);//将val个字符加入答案
            }
            now = (now + 1) % 3;//轮流选
        }
        System.out.println(sb.toString());
    }
}

题目内容

有一个神话传说，说在很久以前，红色的守护者曾经来到人间，为了保护人们免受邪恶的侵害，他留下了一个强大的魔法。这个魔法被传说中的红宝石所承载，只有能够创造出特定数量回文子串的字符串才能够揭示出它的秘密。

为了获得这个神秘的魔法，有一个名叫小红的人在神秘的传说中展开了他的冒险。他在一本古老的书籍中找到了一篇有关于这个魔法的描述：

在所有由‘r’,‘e’和‘d’这三种字符构成的字符串中，只有当回文子串的数量为特定数量时，才能揭示红宝石的魔法。这个特定数量由一个神秘的整数 $x$ 所定义。

为了获得这个强大的魔法，小红开始思考如何创造出刚好有 $x$ 个回文子串的字符串。他发现，如果想要获得这个魔法，就必须要先找到这个特定的字符串，因此他开始了漫长的冒险之旅。

字符串的长度不得超过$10^5$

输入描述

一个正整数$x$.

$1 \leq x \leq 10^9$

样例

输入

4

输出

rre