A. 幂运算

构造 $a = x, b = 1$ 那么 $a^b = x$ 满足题意。

void solve(){
    int x;cin >> x;
    cout << x << " " << 1 << "\n";
}

B. 琪露诺的 K 维偏序

给出的数组已经是有序的了，贪心第 $k_i$ 小的数，只需要判断 $a_{k_i} < x_i$ 即可。

当然，这题也可以使用二分查找小于 $x_i$ 的数量，然后对比数量。

void solve() {
    int n, q;
    cin >> n >> q;
    vector<int> a(n+9);
    for (int i = 1; i <= n; i++) cin >> a[i];
    sort(a.begin()+1,a.begin()+n+1);
    while (q--) {
        int k,x;
        cin >> k >> x;
        cout << (a[k] < x ? "Yes\n" : "No\n");
    }
}

C. 合成大企鹅

结论：每次贪心取最小的两个数合成。

这里给出两种证明办法：（证明方式不唯一）

证明1：取对数考虑，每次操作相当于删了两个数，添加它们的平均数，那么很显然先删的数被平均过最多次，权值是最小的。

证明2：我们倾定两个数 $a\le b$ ，那么假设我们对这两个数进行一次合成，那么新得出的数字一定满足 $a\le \sqrt{ab}\le b$ ，即每次会对于相较于较大的数来说，结果变小。此时如果操作的 $a,b$ 是所有数中最小的两个数，那么产生的数一定是最小的数。所以我们为了保留值尽可能大，就要从最小的数进行操作。

时间复杂度： $O(n)$ 到 $O(n\log n)$ ，瓶颈在排序。

void solve(){
    int n;cin >> n;
    double ans = 1;
    vector<int> a(n+1);
    for (int i = 1;i <= n;i ++) cin >> a[i];
    sort(a.begin()+1,a.end());
    for (int i = 1;i <= n;i ++){
        if (i == 1){
            ans = a[i];
        } else {
            ans *= a[i];
            ans = sqrt(ans);
        }
    };
    cout << fixed << setprecision(12) << ans << "\n";
}

D/E. ⑨运算

D 题数据范围很小，可以直接跑一次暴力预处理，然后多查。E 题怎么做呢？

首先，考虑不使用操作 2，判断操作 1 是否可以变成全为 9 的数。变的那个数一定是大于等于 $x$ 的最小的全为 9 的数记为 $f(x)$ ，如果可以变成的话当且仅当 $9\ |\ f(x)-x$ ，答案就为 $\frac{f(x)-x}{9}$ 。

考虑做一次操作 2，我们考虑在操作 2 操作之后等价于原来的操作前的 $+1$ ，于是我们要操作 2 前尽可能少的步数到达 $111\cdots 11$ ，然后用一次操作 2。

最后两者答案取最小。

单组测试时间复杂度 $O(\lg(x))$ 。

using i64 = long long;
void solve(){
    i64 x;
    cin >> x;
    i64 y = 9,z;
    while(y < x) y = y * 10 + 9;
    z = x <= y/9 ? y/9 : y/9*10+1;
    i64 ans = 2e18;
    if (x%9==0) ans = min(ans,(y-x)/9);
    ans = min(ans,(z-x)/9+(z-x)%9+1);
    cout << ans << "\n";
}

F. 琪露诺的排列构造

只有 $n \le 2$ 时是无解的。

对于 $n$ 是奇数，可以构造 $[2,3,\cdots,n,1]$ ，前 $n-1$ 项互不相等且为奇数，第 $n$ 项为偶数不与前面相等。

对于 $n$ 是偶数，可以构造 $[2,3,\cdots,n-2,n,1,n-1]$ 。前 $n-3$ 项互不相等且是小于 $2n-4$ 的奇数。而第 $n-2$ 和 $n$ 项大于 $2n-4$ ，第 $n-1$ 项是偶数，所以满足题意。

构造方案不唯一，例如可以特判 $n=4$ 后把偶数拆成两个奇数相加（ $(3)+(n-3)$ ），独立构造（下方代码）。

单组测试时间复杂度 $O(n)$ 。

void solve() {
    int n;
    cin >> n;
    if (n <= 2) {
        cout << -1 << endl;
    }else if (n%2) {
        for (int i = 2; i <= n; i++) cout << i << " ";
        cout << 1 << endl;
    }else if (n == 4) {
        cout << "2 4 1 3" << endl;
    }else {
        cout << "2 3 1 ";
        for (int i = 5; i <= n; i++) cout << i << " ";
        cout << 4 << endl;
    }
}

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

记 $f(l,r) = \sum_{i=l}^r i \bmod (q) \bmod (q-1) \bmod (q-2) \cdots \bmod (p)$ ，显然有 $f(l,r) = f(1,r)-f(1,l-1)$ 。

考虑如何计算 $f(1,n)$ ：

可以证明： $i \bmod (q) \bmod (q-1) \bmod (q-2) \cdots \bmod (p) =$ - $i \bmod q \quad \mathrm{if}\ (i \bmod q) < p$ - $0 \quad \mathrm{otherwise}$
$i$ 从 $1$ 到 $n$ ，有完整的 $\left \lfloor \frac{n}{q} \right \rfloor$ 段 $\sum_{j=0}^{p-1}j$ 和剩下的一段 $\sum_{j=0}^{\min(i \bmod q,p-1)} j$ 。

单组测试时间复杂度 $O(1)$ 。