链接：https://ac.nowcoder.com/acm/contest/125080

A – 幂运算

算法：

    构造。

思路：

    无。

关键代码：

void miyan()
{
    int a;
    cin >> a;

    cout << a << ' ' << 1 << endl;
}

B – 琪露诺的 K 维偏序

算法：

    二分。

思路：

    无。

关键代码：

void miyan()
{
    int n, q;
    cin >> n >> q;
    vector<int> a(n);
    for (auto &x : a)
        cin >> x;

    while (q--)
    {
        int k, x;
        cin >> k >> x;

        int p = ranges::lower_bound(a, x) - a.begin();

        if (p >= k)
            cout << "Yes" << endl;
        else
            cout << "No" << endl;
    }
}

C – 合成大企鹅

算法：

    贪心，排序。

思路：

    让大的值尽量少开根，从最下的开始合并。

关键代码：

void miyan()
{
    int n;
    cin >> n;
    vector<double> a(n);
    for (auto &x : a)
        cin >> x;

    if (n == 1)
    {
        printf("%.10lf\n", a[0]);
        return;
    }

    ranges::sort(a);
    double ans = sqrtf(a[0] * a[1]);
    for (int i = 2; i < n; ++i)
        ans = sqrtf(ans * a[i]);

    printf("%.10lf\n", ans);
}

D,E – ⑨运算

算法：

    数学。

思路：

    对于每个数字 \(x\)，最后变成的好数字是 \(10 ^ {k} – 1\)，其模 \(9\) 的结果是 \(0\)。

    对于操作 \(1\)，不会改变 \(x\) 模 \(9\) 的结果，而操作 \(2\) 会改变模 \(9\) 的结果：

• 如果一个数字是 \(9\) 的倍数，可以考虑只使用操作 \(1\) 将其变为距离它最近的好数字，操作次数就为 \((10 ^ k – 1 – x) / 9\)。
• 如果一个数字是 \(111…..\)，那么只需要使用一次操作 \(2\) 即可。
• 如果一个数字不是 \(9\) 的倍数也不是 \(111…..\)，那么就先使用 \(a\) 次操作 \(1\)，然后使用一次操作 \(2\)，再使用 \(b\) 次操作 \(1\)，

    此时数字变为 \(x + 9a \Rightarrow 9x + 81a \Rightarrow 9x + 81a + 9b\)，最小化 \(a + b\) 的值即可。

    原式 \(= 9x + 81a + 9b = 10 ^ k – 1 \Rightarrow 9x + 9(9a + b) = 10 ^ k – 1 \Rightarrow 9a + b = ((10 ^ k – 1) – 9x) / 9\)

    已知 \(x\)，可以枚举 \(k\)，可得 \(val = 9a + b\)，其中 \(a = val / 9\)，\(b = val % 9\)，那么操作次数就为 \(1 + a + b\)。

    \(ans\) 对上述的每个次数取最小值即可。

关键代码：

vector<ll> p(20, 1);
void init()
{
    for (int i = 1; i <= 18; ++i)
        p[i] = p[i - 1] * 10;
}

void miyan()
{
    ll x;
    cin >> x;

    ll ans = LLONG_MAX;
    for (int i = 1; i <= 18; ++i)
    {
        ll need = p[i] - 1;

        if (need < x)
            continue;

        if (need == x)
            ans = min(ans, 0ll);

        if (need == 9 * x)
            ans = min(ans, 1ll);

        if (x % 9 == 0)
        {
            ll cnt = (need - x) / 9;
            ans = min(ans, cnt);
        }

        if (need > 9 * x && (need - 9 * x) % 9 == 0)
        {
            ll cur = (need - 9 * x) / 9;
            ll cnt = 1 + cur / 9 + cur % 9;
            ans = min(ans, cnt);
        }
    }

    cout << ans << endl;
}

F – 琪露诺的排列构造

算法：

    构造。

思路：

    \(n <= 2\) 无解。

    通过样例给出的 \(2 3 1\)，可以猜一下答案为：

• 先倒序输出偶数，再倒序输出奇数，\(4,2,3,1\) 不成立。
• 先正序输出偶数，再倒序输出奇数，\(2,4,3,1\) 不成立。
• \(2,3 … n,1\)，奇数情况符号条件。

    对于偶数情况，最后的一个 \(1\) 会与前面的数字相等，那么将 \(1\) 向前移动一位将其 \(-1\) 值刚好为偶数，不会冲突，也不能将 \(n\) 放到最后，那就将 \(n – 1\) 提到最后，即 \(2,3,4,n,1,n – 1\)。

关键代码：

void miyan()
{
    int n;
    cin >> n;

    if (n <= 2)
    {
        cout << -1 << endl;
        return;
    }

    if (n & 1)
    {
        for (int i = 2; i <= n; ++i)
            cout << i << ' ';
        cout << 1 << endl;
    }
    else
    {
        for (int i = 2; i <= n - 2; ++i)
            cout << i << ' ';
        cout << n << ' ' << 1 << ' ' << n - 1 << endl;
    }
}

G – 琪露诺的连续取模求和

算法：

    数学。

思路：

\(i \text{%} q = val ∈ [0, q – 1]\)

• 如果 \(val ∈ [p, q – 1]\)，\(val\) 最后等于 \(0\)。
• 如果 \(val ∈ [0, p – 1]\)，\(val\) 最后等于 \([0, p – 1]\)。

    可以发现存在周期，周期长度为 \(q\)。

    那么 \([l, r]\) 可分为以下三个部分：

• 周期的后缀 + \(k\) 个完整的周期 + 周期的前缀。

关键代码：

void miyan()
{
    ll l, r, p, q;
    cin >> l >> r >> p >> q;

    --l, --r;

    ll val = p * (p - 1) / 2;

    ll L = l / q, R = r / q;

    ll cnt = R - L - 1;

    ll ans = cnt * val;

    ll suf = q - l % q;
    ll pre = r % q + 1;

    if (suf > q - p + 1)
    {
        suf -= q - p + 1;

        ll start = p - 1 - suf + 1;
        ll end = p - 1;

        ll cur = (start + end) * (end - start + 1) / 2;

        ans += cur;
    }

    pre = min(pre, p - 1);

    ll start = 1;
    ll end = pre;

    ll cur = (start + end) * (end - start + 1) / 2;

    ans += cur;

    cout << ans << endl;
}