Contestant. Rank 3808. Rating +17.

A. Exponential Equation

题意

给定整数 ，输出一对 ，满足 。

思路

不妨令 ，那么 。

显然，当 为奇数的时候，一定是无解的，因为 和 的奇偶性一定是一致的。

所以， 为偶数的时候，输出 。

时间复杂度：

对应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

题意

给定一个整数 ，构建数组 ，使 。其中， 必须为不相同的质数的乘积。

输出 的最大值。

思路

显然，，那么我们不妨直接拆开，令所有 。

那么，我们只需分解质因数，分别将出现次数 次、 次 … 的数相乘后求和即可。

时间复杂度：不会分析

对应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

题意

给定一个数组 以及一个整数 ，对于所有 ，有 且 。

构造 ，让下列式子的值最小，并输出这个值

$F = a1 \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$

思路

我们不妨来单独考虑 ：

将其放入式子，我们可以得到 $\ldots+ y{i-1}\cdot x_i+y_i\cdot x{i+1}+\ldotsxi + 1,y_i - 1x{i + 1} - y_{i - 1}$。

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

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

时间复杂度：

对应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于是乱找规律这件事