Rank 196/3562. AC 7/11.

~~这标题显然是参考了arcaea的final verdict包的剧情，对吧~~

A. 不断减损的时间

题意

给定一个数组，数值可以为负数。对于无限次的操作，你可以任选一个偶数并将其除以，输出最后总和的最大值。

思路

将所有正偶数暴力除到奇数为止，并求和即可。

时间复杂度：

对应AC代码

import java.util.*;

public class Main{

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        long ans = 0;
        for(int i=0;i<n;i++){
            int a = scanner.nextInt();
            if(a <= 0) ans += a;
            else{
                while(a % 2 == 0) a /= 2;
                ans += a;
            }
        }
        System.out.println(ans);
    }

}

快速签到

B. 勉强拼凑的记忆

题意

给定块矩形积木，积木的大小为，可在内任意选择，若能使用所有积木搭成正方形，输出最大的边长，否则输出。

思路

很难说思路，因为可以打表打出规律（（

前个根据打表得到

很容易就可以得到一个通式

至于为什么会这样，我们可以考虑以上的数，因为横放几个最长的方块，然后再竖着放一个方块，最后在最后一行填满方块，即为之间的规律，而以上，我们就可以发现最底下还可以再塞一行，然后在右边再放上一个方块依然是可行的，以此类推…

时间复杂度：

对应AC代码

import java.util.*;

public class Main{

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int t = scanner.nextInt();
        while(t -- > 0){
            long q = scanner.nextLong();
            if(q == 2) System.out.println(-1); //下面式子会算成0...
            else System.out.println((q * 2 + q % 2) / 3);
        }
    }

}

打表好累.jpg

C. 忽远忽近的距离

题意

构造一个排列，满足。

思路

打表，暴力找规律即可。

可以发现是个为一块有规律输出的，处理结尾数字即可。

时间复杂度：（确信

对应AC代码

#include <bits/stdc++.h>

using namespace std;

#define ll long long

int main() {
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    int n;
    cin >> n;
    if(n < 4) cout << -1 << '\n';
    else if(n == 4) cout << "3 4 1 2\n";
    else if(n == 5) cout << "4 5 1 2 3\n";
    else if(n == 6) cout << "4 5 6 1 2 3\n";
    else if(n == 7) cout << -1 << '\n';
    else if(n == 8) cout << "3 4 1 2 7 8 5 6\n";
    else if(n == 9) cout << "3 4 1 2 7 8 9 5 6\n"; //狠狠地打表
    else {
        int i = 0;
        if (n % 4 == 3)
            for (; i < n / 4 - 2; i++)
                cout << i * 4 + 3 << " " << i * 4 + 4 << " " << i * 4 + 1 << " " << i * 4 + 2 << " ";
        else
            for (; i < n / 4 - 1; i++)
                cout << i * 4 + 3 << " " << i * 4 + 4 << " " << i * 4 + 1 << " " << i * 4 + 2 << " ";
        if (n % 4 == 0) cout << i * 4 + 3 << " " << i * 4 + 4 << " " << i * 4 + 1 << " " <<  i * 4 + 2;
        else if (n % 4 == 1) cout << i * 4 + 4 << " " << i * 4 + 5 << " " << i * 4 + 1 << " " <<  i * 4 + 2 << " " <<  i * 4 + 3;
        else if (n % 4 == 2) cout << i * 4 + 4 << " " << i * 4 + 5 << " " << i * 4 + 6 << " " << i * 4 + 1 << " " <<  i * 4 + 2 << " " <<  i * 4 + 3;
        else cout << i * 4 + 4 << " " << i * 4 + 5 << " " << i * 4 + 1 << " " <<  i * 4 + 2 << " " << i * 4 + 3 << " " << i * 4 + 9 << " " << i * 4 + 10 << " " <<  i * 4 + 11 << " " << i * 4 + 6 << " " << i * 4 + 7 << " " <<  i * 4 + 8;
    }
}

打表好累.jpeg

D. 宿命之间的对决

题意

给定一个正整数，小红和小紫轮流取当前数的因子，使当前数减少。如果小红获胜，则输出 “”，否则输出 “”

思路

简单的博弈题。

我们先假设每个人都只拿个，那么最后一定是第一次拿的时候当前数为偶数的一方获胜。

然而，输的一方肯定想要获胜，那么他一定要拿掉偶数个才行，而无论他怎么拿，获胜方都可以只拿掉奇数来使他只能从奇数的因数中取，从而不可能取到偶数，因而必输。

所以，判奇偶即可。

时间复杂度：

对应AC代码

import java.util.*;

public class Main{

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        System.out.println(scanner.nextLong() % 2 == 1 ? "yukari" : "kou");
    }

}

次世代の宿命之红砍光光（？

E. 公平守望的灯塔

题意

给定在平面直角坐标系的整点和，输出一个整点，使得为以为斜边的等腰。

思路

“K型全等”，找出中点后用全等即可解出。

当和横坐标的差值和纵坐标的差值的奇偶性不一致时，点一定会有小数存在，因此该条件无解。

时间复杂度：

对应AC代码

import java.util.*;

public class Main{

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        long xa = scanner.nextLong(), ya = scanner.nextLong(), xb = scanner.nextLong(), yb = scanner.nextLong();
        if(Math.abs(xa - xb) % 2 == Math.abs(ya - yb) % 2){ //初中数学？
            long mid2x = xa + xb, mid2y = ya + yb;
            System.out.printf("%d %d\n", (mid2x + mid2y) / 2 - ya, (mid2y - mid2x) / 2 + xa);
        }else System.out.println("No Answer!\n");
    }

}

画个图，不就是个初中数学题嘛

F. 迎接终结的寂灭

题意

输出。

思路

输出。

时间复杂度：

对应AC代码

import java.util.*;

public class Main{

    public static void main(String[] args) {
        System.out.println(42);
    }

}

怎么会是呢

G. 严肃古板的秩序

题意

给定一个运算式，其中等式左边的符号全都被替换成，等式右边只有一个数字，符号只有三种可能：，， #，其中定义# $且$ ，三个符号的优先级相同，输出一个合法的式子，否则输出。

思路

暴力即可，其中模幂运算需要使用快速幂。

时间复杂度：

对应AC代码

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

public class Main{

    static int n;
    static long ans;
    static long[] nums;
    static char[] op;
    static boolean ok = false;

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String[] s = scanner.next().split("\\?");
        n = s.length;
        nums = new long[n];
        for(int i=0;i<n-1;i++) nums[i] = Long.parseLong(s[i]);
        nums[n - 1] = Long.parseLong(s[n - 1].split("=")[0]);
        ans = Long.parseLong(s[n - 1].split("=")[1]);
        op = new char[n - 1];
        dfs(0, nums[0]);
        if(!ok) System.out.println(-1);
    }

    private static void dfs(int index, long last){
        if(index == n - 1){
            if(last == ans) {
                ok = true;
                print();
            }
            return;
        }
        if(ok) return;
        op[index] = '+';
        dfs(index + 1, last + nums[index + 1]);
        if(ok) return;
        op[index] = '-';
        dfs(index + 1, last - nums[index + 1]);
        if(ok || last <= 0 || nums[index + 1] <= 0) return;
        op[index] = '#';
        dfs(index + 1, BigInteger.valueOf(last).modPow(BigInteger.valueOf(last), BigInteger.valueOf(nums[index + 1])).longValue());
    }

    private static void print(){
        System.out.printf("%d", nums[0]);
        for(int i=1;i<n;i++){
            System.out.printf("%c%d", op[i - 1], nums[i]);
        }
        System.out.printf("=%d\n", ans);
    }

}

很经典的回溯搜索

H. 穿越万年的轮回

待补充

I. 灵魂碎片的收集

题意

定义为的所有不包括的因数的和，给定正整数，输出满足的正整数，否则输出。

限制

对于输入的，有以下限制：

，则和之间一定有一个是质数。
，则无限制

思路

我们可以直接从限制入手：

若为偶数，且是质数，那么显然只有一种分解，那么。

若为偶数，且是质数，那么也只有一种分解，那么。

若为奇数，因为一定是其中一个因子，那么剩下的一定是偶数。因为所有偶数都可以分解为两个质数之和，那么我们可以直接暴力，枚举出一种可能即可。

当然，为了判定素数方便，我们采取用线性筛打表的方式来让查询的复杂度降到。

时间复杂度：懒得分析

对应AC代码

#include <bits/stdc++.h>

using namespace std;

const int N = 1000010;

#define ll long long

vector<int> primes;
bool vis[N + 1], isPrime[N + 1];

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

int main() {
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    init();
    int t;
    ll x;
    cin >> t;
    int ans[] = {0, -1, -1, 4, 9, -1, 25, 8};
    while (t--) {
        cin >> x;
        if(x <= 7) cout << ans[x] << '\n';
        else {
            if (x % 2 == 0) {
                if (isPrime[x - 1]) cout << (x - 1) * (x - 1) << '\n';
                else cout << 2 * (x - 3) << '\n';
            } else {
                for (int i = 2; i <= x; i++) {
                    if(isPrime[i] && isPrime[x - i - 1]) {
                        cout << (ll)i * (x - i - 1) << '\n';
                        break;
                    }
                }
            }
        }
    }
}

赛时眼瞎了没看到限制

J. 无法磨灭的悔恨

待补充

K. 永恒守候的爱恋

题意

假设为前个素数，定义为个组成的多重集合。

例如，多重集{2,2,3,3,3,7}可以表示为：

。

定义为一个数组前个元素的乘积的因子数量，给定和数组，他表示了一个大小为 $size=\sum{i=1}^{n}a_i $的多重集。用这个多重集的所有元素构造一个大小为$ size $的数组，输出$ \sum{i=1}^{size}f(i) $的最大值，对$ 10^9+7$ 取模。

思路

叠满的数学题。

我们先来考虑因子个数：根据算数基本定理，对于一个分解式，因数数量为。

那么既然我们要让这个乘积更大，我们就可以每次都不重复地将数字放上去，如。那么对于第一块，结果为、、。对于第二块，结果为、。对于第三块，结果为。

显然，上述式子是分块的等比数列求和，其中

因而，我们只需一块一块地处理即可。

当然，为了快速求出每一块的元素个数，我们只需在读入的时候使用差分的方法，具体地来说：

横向从左到右绘制一张柱状图，那么纵切面的数量即为每块的元素数量。

时间复杂度：不好评价

对应AC代码

注意，此代码不一定能运行通过，有概率会超时

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

public class Main{

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int[] t = new int[200010];
        for(int i=0;i<n;i++){
            t[scanner.nextInt() + 1] --;
            t[1] ++;
        }
        int max = 0;
        for(int i=1;i<200010;i++) {
            t[i] += t[i - 1];
            if(t[i] == 0) {
                max = i - 1;
                break;
            }
        }
        long ans = 0, a1 = 1, an;
        BigInteger res = BigInteger.ONE, ip1, mod = BigInteger.valueOf(1000000007L);
        for(int i=1;i<=max;i++){ //规避一下逆元
            int now = t[i], nxt = t[i + 1];
            ip1 = BigInteger.valueOf(i + 1);
            res = res.multiply(ip1.modPow(BigInteger.valueOf(now - nxt), mod)).mod(mod);
            a1 = (a1 * (i + 1)) % 1000000007L;
            an = res.multiply(ip1.modPow(BigInteger.valueOf(nxt), mod)).mod(mod).longValue();
            ans = (ans + (an * (i + 1)) % 1000000007L + 1000000007L - a1) % 1000000007L;
            a1 = an;
        }
        System.out.println(ans);
    }

}

不用考虑第几个质数是啥呢

本文作者 Floating Ocean
本文链接 https://floating-ocean.github.io/blog_old/posts/2583580825/
版权声明本博客所有文章除特别声明外，均采用 BY-NC-SA 许可协议。转载请注明出处！