【构造】构造一个字符串满足k个子序列问题总结

题目 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;
}