2022/7/16 每日一题(构造)

小红的构造题
题意：构造出一个字符串，使得其实"red"子序列的数量满足指定k个。0≤k≤10^14
思路:刚开始想的是可以控制r、ed、d这三种方式来实现子序列数量的增加，但增加的方式看不出规律来。
1.构造rererere……类型的子序列，通过添加d的方式添加序列。
2.若在第一个re出添加x个d，则整个字符串添加x的red；若在第二个re处添加x个d，则会添加出3x个red；若在第三个re处添加x个d，则会添加出6x个red……则找出规律，若在第n个re处添加x个d，则整个字符串会添加x*(x+1)/2*x个red
3.子序列的数量以立方的速度向上增长，以此确定re的数量。

代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+6;
int a[N],n;
signed main()
{
    
    int n;cin>>n;
    if(!n)
    {
    
        cout<<"der"<<endl;return 0;
    }
    int i;
    for(i=1;i*i*i<=n;i++);
    for(int j=i;j>=1;j--)
    {
    
        a[j]+=n/(j*(j+1)/2);
        n%=j*(j+1)/2;
    }
    for(int j=1;j<=i;j++)
    {
    
        cout<<"re";
        while(a[j]--) cout<<"d";
    }
    cout<<endl;
    return 0;
}