0%

牛客2023寒假集训 - 3

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. 灵魂碎片的收集

题意

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

限制

对于输入的 ,有以下限制:

  1. ,则 之间一定有一个是质数。
  2. ,则无限制

思路

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

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

为偶数,且 是质数,那么也只有一种分解 ,那么

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

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

时间复杂度:懒得分析

对应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_isize\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);
    }

}

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