题目 Codeforces Subsequences
题目链接 :Codeforces Subsequences
题目大意：
构造一个字符串，至少包含k个
codeforces子序列，并且字符串最短。
思路：构造
假设我们要找的不是codeforces的子序列，而是abcde。如果一个字符串中a字母不在最前面，那么把它移到最前面其他不变的话，就多了一个abcde序列。所以为了让序列更多，那么只需要将所有的a都移动到最前面即可。b跟着a的后面，c跟着b的后面，其他也如此。每个字母的排序问题已经解决了，那么现在就是每个字母有多少个的问题了。答案是我们应该让每个字母的数量尽可能接近。
证明：子序列的数量就等于
SumA * SumB * SumC * SumD * SumE，SumA表示a的数量，如果SumA - SumB > 1的话，那么(SumA - 1) * (SumB + 1) > SumA * SumB,所以为了让字符串更短，所以让每个字母的数量尽可能接近。现在我们就可以通过循环增加每个字符的数量，一旦乘积至少为k，那么就退出循环，最后打印每个字母的数量即可。
代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e6 + 10, inf = 0x3f3f3f3f, mod = 998244353;
int n, k;
ll a[N], c[N];
signed main()
{
#ifdef Xin
freopen("in.in", "r", stdin);
freopen("out.out", "w", stdout);
#endif
ll k;
cin >> k;
string s = "codeforces";
int n = s.size();
vector<int> a(n, 1);
ll sum = 1;
for (int i = 0; sum < k; i = (i + 1) % n)
{
sum = sum / a[i] * (a[i] + 1);
a[i]++;
}
for (int i = 0; i < n; i++)
{
for (int j = 0; j < a[i]; j++)
cout << s[i];
}
return 0;
}小红的构造题
题目链接 :小红的构造题
题目大意：
构造一个字符串，至少包含k个
red子序列，并且字符串长度不超过200000
思路：构造
这道题就不能用上道题的方法了，为什么？假设
k == 1e14，那么为了让字符串最短，那么每个字目的长度为1e5，那么三个字母的长度就为3e5超过范围。为什么上道题可以那样写，因为codeforces有10个字母，每个字母长度假设有100，那么最多只需要1000个字符就能解决问题。那这道题这么解决：
我们可以先构造这样一个字符串
rererererere....，在第一个re后面加x个d，那序列个数就加了x个，如果在第二个re后面加了x个d，那么就增加了3*x子序列，依次类推，在第k个re后面加x个d，那就增加k*(k+1)*x/2个子序列。所以为了让字符串长度越小，所以需要从后往前枚举，每次填入x个字符串即可。
代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e6 + 10, inf = 0x3f3f3f3f, mod = 998244353;
ll k;
ll a[N], c[N];
signed main()
{
#ifdef Xin
freopen("in.in", "r", stdin);
freopen("out.out", "w", stdout);
#endif
cin >> k;
if (k == 0)
{
cout << "a";
return 0;
}
int M = 80000;
for (int i = 1; i <= M; i++)
{
a[i] = (ll)i * (i + 1) / 2;
}
int id = 0;
for (int i = M; i >= 1; i--)
{
if (k >= a[i])
{
c[i] = k / a[i];
k %= a[i];
}
}
for (int i = 1; i <= M; i++)
{
cout << "re";
while (c[i]--)
cout << 'd';
}
return 0;
}