1925(921div2)

只做了一题，仍然是个废物 $\dots$ ，经过假期的训练，我希望达到至少过 3 题的水平

A. We Got Everything Covered!

给你两个正整数 $n$ 和 $k$ 。

您的任务是找出一个字符串 $s$ ，使得所有可能的长度为 $n$ 的字符串都可以用前 $k$ 个小写英文字母作为 $s$ 的子序列出现。

如果有多个答案，则打印长度最小的答案。如果仍有多个答案，可以打印其中任意一个。

注：如果从 $b$ 中删除一些字符（可能为零）而不改变其余字符的顺序即可得到 $a$ ，则字符串 $a$ 称为另一个字符串 $b$ 的子串。

void solve()
{
    int n, k;
    cin >> n >> k; // n:子字符串长度，k:字母个数
    vector<char> a;
    for (int i = 1; i <= n; i++)
        for (int i = 1; i <= k; i++)
            a.push_back('a' + i - 1);

    for (auto x : a)
        cout << x;
    cout << '\n';
}

B. A Balanced Problemset?

将 $x$ 分解为 $n$ 个整数组成，使得这 $n$ 个数的 gcd 最大，也就是最平衡。

Solution

想了半天没想出来 $\dots$

没太搞懂 $\dots$

这段代码已经被 HACK 了，现在提交会 T
![](/img/user/ZZZ-Misc/Z-Attachment/images-old-ACM/Pasted image 20240128171314.png)

void solve()
{
    int n, x;
    cin >> x >> n;
    if (n == 1)
    {
        cout << x << '\n';
        return;
    }
    for (int i = x / n; i >= 1; i--)
    {
        if (x % i == 0 && x / i >= n)
        {
            cout << i << '\n';
            return;
        }
    }
}

有： $G C D (a_{1}, a_{2}, a_{3}, \dots, a_{n}) = G C D (a_{1}, a_{1} + a_{2}, a_{1} + a_{2} + a_{3}, \dots, a_{1} + a_{2} + a_{3} + \dots + a_{n})$ $\leftrightarrow G C D (a_{1}, a_{1} + a_{2}, a_{1} + a_{2} + a_{3}, \dots, x)$

所以答案一定是 $x$ 的一个约数。

现在，考虑 $x$ 的一个因数 $d$ ，我有两种想法
$(1)$

当 $n \times d \leq x$ ,选择为： $d, d, d, \dots, x - (n - 1) d \leftrightarrow gcd (d, 2 d, 3 d . ., x)$ 有可行答案 $d$
当 $n \leq d$ ,有可行答案 $x / / d$ （本来每一份是 $\frac{x}{n}, n$ 份，这时 $n \leq d$ ，如果分为 $d$ 份每一份就是 $\frac{x}{d}$ 可以分为更多份，每一份也更大， $\geq n$ 的部分可以直接安到任意位置，这时的 $\frac{x}{d}$ 也可以作为答案）

$(2)$

直接遍历因子 $1 - x$ (然后 $n \times d \leq x, 取 d$ )会超时
遍历因子 $1 - \sqrt{x}$ (然后 $n \times d \leq x o r n \times (\frac{x}{d}) \leq x, 取 d o r x / d$ ) 这样就可以将因子遍历完。

找到满足该条件的最大 $d$ 。这可以在 $O (\sqrt{x})$ 时间内通过简单的因数分解来实现。

![](/img/user/ZZZ-Misc/Z-Attachment/images-old-ACM/Pasted image 20240128180042.png)

void solve()
{
    int n, x;
    cin >> x >> n;
    int ans = 1;
    for (int i = 1; i * i <= x; i++)
    {
        if (x % i == 0)//如果i是x的因子
        {
            if (n <= x / i)//n*i<=x ->i i i ... x-(n-1)*i  ->i
                ans = max(ans, i);
            if (n <= i)
                ans = max(ans, x / i);
        }
    }
    cout << ans << '\n';
}

C . Did We Get Everything Covered?

给你两个整数 $n$ 和 $k$ 以及一个字符串 $s$ 。

您的任务是检查是否所有长度为 $n$ 的字符串都可以用第一个 $k$ 小写英文字母组成，并作为 $s$ 的子序列出现。

如果答案是否定的，那么您还需要打印一个长度为 $n$ 的字符串，该字符串可以用第一个 $k$ 小写英文字母组成，但不会作为 $s$ 的子序列出现。

如果有多个答案，您可以打印任意一个。

注：如果从 $b$ 中删除一些字符（可能为零）而不改变其余字符的顺序，就可以得到 $a$ ，那么字符串 $a$ 就被称为另一个字符串 $b$ 的子串。

(待更 $\dots$ )