Contestant. Rank 3808. Rating +17.

A. Exponential Equation

题意

给定整数 \(n\)，输出一对 \(x, y\)，满足 \(x ^ y \cdot y + y ^ x \cdot x = n\)。

思路

不妨令 \(x = 1\)，那么 \(y = n / 2\)。

显然，当 \(n\) 为奇数的时候，一定是无解的，因为 \(x ^ y \cdot y\) 和 \(y ^ x \cdot x\) 的奇偶性一定是一致的。

所以，\(n\) 为偶数的时候，输出 \(1, n / 2\)。

时间复杂度：\(O(1)\)

对应AC代码

import java.math.BigInteger;
import java.util.*;

public class Main{

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int t = scanner.nextInt();
        nxt:
        while (t-- > 0) {
            int n = scanner.nextInt();
            if(n % 2 == 1) System.out.println(-1);
            else System.out.printf("%d %d\n", 1, n / 2);
        }
    }

}

你说我怎么就这么蠢

B. Number Factorization

题意

给定一个整数 \(n\)，构建数组 \(a, p\)，使 \(n = \prod a_i^{p_i}\)。其中，\(a_i\) 必须为不相同的质数的乘积。

输出 \(\sum a_i \cdot p_i\) 的最大值。

思路

显然，\(a_i ^ {p_i} = a_i \cdot a_i \cdot \ldots\)，那么我们不妨直接拆开，令所有 \(p_i = 1\)。

那么，我们只需分解质因数，分别将出现次数 \(\geq 1\) 次、\(\geq 2\) 次 ... 的数相乘后求和即可。

时间复杂度：不会分析

对应AC代码

#include <bits/stdc++.h>

using namespace std;

const int N = 500010, inf = 0x3f3f3f3f;

#define int long long

vector<int> primes;
bool vis[N];

void init() {
    for (int i = 2; i <= N; ++i) {
        if (!vis[i]) {
            primes.emplace_back(i);
        }
        for (int j : primes) {
            if (1ll * i * j > N) break;
            vis[i * j] = true;
            if (i % j == 0) break;
        }
    }
}

vector<tuple<int, int, bool>> fact(int x) {
    vector<tuple<int, int, bool>> f;
    for (int i : primes) {
        if(i > x) break;
        if (x % i == 0) {
            int cnt = 0;
            while (x % i == 0) x /= i, cnt ++;
            if(cnt != 0) f.emplace_back(i, cnt, false);
        }
    }
    if (x != 1) {
        f.emplace_back(x, 1, false);
    }
    return f;
}

signed main() {
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    init();
    int t, n;
    cin >> t;
    while(t --) {
        cin >> n;
        vector<tuple<int, int, bool>> f = fact(n);
        int ans = 0, cnt = f.size();
        while(cnt > 0){
            int now = 1;
            for(auto &e : f){
                int x, p, ok;
                tie(x, p, ok) = e;
                if(ok) continue;
                now *= x;
                p --;
                if(p == 0) get<2>(e) = true, cnt --;
                get<1>(e) = p;
            }
            ans += now;
        }
        cout << ans << '\n';
    }
}

写得好乱

C. Remove the Bracket

题意

给定一个数组 \(a\) 以及一个整数 \(s\)，对于所有 \(i \in [2, n- 1]\)，有 \(x_i+y_i=a_i\) 且 \((x_i - s)(y_i - s) \geq 0\)。

构造 \(x_i, y_i\)，让下列式子的值最小，并输出这个值

\(F = a_1 \cdot x_2+y_2 \cdot x_3+y_3 \cdot x_4 + \ldots + y_{n - 2} \cdot x_{n-1}+y_{n-1} \cdot a_n\)

思路

我们不妨来单独考虑 \(x_i,y_i\)：

将其放入式子，我们可以得到 \(\ldots+ y_{i-1}\cdot x_i+y_i\cdot x_{i+1}+\ldots\)。在这段式子里，若 \(x_i + 1,y_i - 1\)，那么整个式子将会减少 \(x_{i + 1} - y_{i - 1}\)。

也就是说，我们希望 \(x_i\) 或 \(y_i\) 取到 \(s\)，因为只有在边界才能找到最值。

因而，我们可以用 \(dp\) 枚举所有我们希望的情况中的最小值。

时间复杂度：\(O(n)\)

对应AC代码

import java.io.*;
import java.math.*;
import java.util.*;
import java.util.concurrent.atomic.*;

public class Main{

    public static void main(String[] args) throws Exception{
        Console console = new Console();
        int t = console.nextInt();
        nxt:
        while(t -- > 0){
            int n = console.nextInt(), s = console.nextInt();
            long[] min = new long[n + 1], max = new long[n + 1];
            for(int i=1;i<=n;i++){
                int cur = console.nextInt();
                if(i == 1 || i == n){
                    min[i] = max[i] = cur;
                }else if(cur <= s){
                    min[i] = 0;
                    max[i] = cur;
                }else{
                    min[i] = Math.min(s, cur - s);
                    max[i] = Math.max(s, cur - s);
                }
            }
            long[][] dp = new long[n + 1][2];
            for(int i=2;i<=n;i++){
                dp[i][0] = Math.min(dp[i - 1][0] + max[i - 1] * min[i], dp[i - 1][1] + min[i - 1] * min[i]);
                dp[i][1] = Math.min(dp[i - 1][0] + max[i - 1] * max[i], dp[i - 1][1] + min[i - 1] * max[i]);
            }
            console.println(dp[n][0]);
        }
        console.close();
    }

    //快读模板 此处略去
    //public static class Console implements Closeable {}

}

论想不到dp于是乱找规律这件事