蓝桥杯算法赛第 6 场小白入门赛解题报告 | 珂学家

前言

在这里插入图片描述

整体评价

因为适逢元宵节，所以这场以娱乐为主。

A. 元宵节快乐

题型: 签到

节日快乐，出题人也说出来自己的心愿, 祝大家AK快乐!

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        System.out.println("Today AK!");
    }
}

B. 猜灯谜

思路: 模拟

按题意模拟即可，环状结构

import java.io.BufferedInputStream;
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
import java.util.stream.Collectors;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(new BufferedInputStream(System.in));
        int n = sc.nextInt();
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = sc.nextInt();
        }
        List<Integer> res = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            res.add(arr[(i - 1 + n) % n] + arr[(i + 1) % n]);
        }
        System.out.println(res.stream().map(String::valueOf).collect(Collectors.joining(" ")));
    }
    
}

C. 数学奇才

思路: 思维题

可以贪心逆序从右到左翻转，每次翻转保证最右的非负数多一项，题意保证最多有n次。

所以，必然存在操作序列，使得数组元素全变非负形态。

$\sum_{i=0}^{i=n-1} abs(a_i)$

import java.io.BufferedInputStream;
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(new BufferedInputStream(System.in));
        int n = sc.nextInt();
        long[] arr = new long[n];

        long sum = 0;
        for (int i = 0; i < n; i++) {
            arr[i] = sc.nextLong();
            sum += Math.abs(arr[i]);
        }
        System.out.println(sum);
    }

}

D. 你不干？有的是帕鲁干

思路: 解方程

假设第一个元素为y, 那么

$y + 2) ^ 2 - y ^ 2 = 4(y + 1) = x$

那么该y为

$y = x /4 - 1$

这边需要保证x是4的倍数，同时y必须为>=1的奇数

import java.io.BufferedInputStream;
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(new BufferedInputStream(System.in));

        int t = sc.nextInt();
        while (t-- > 0) {
            long x = sc.nextLong();
            if (x % 4 != 0) {
                System.out.println("No");
            } else {
                long y = x / 4 - 1;
                if (y <= 0 || y % 2 == 0) {
                    System.out.println("No");
                } else {
                    System.out.println("Yes");
                    System.out.println((y) + " " + (y + 2));
                }
            }
        }
    }

}

E. 等腰三角形

思路: 贪心+双指针

感觉这题是这场周赛最难的，但是和历史比，算中等偏下的题

因为三角形中，边的关系需要满足,

$任意两边之和必须大于第三边$

这题也是最大二分匹配模型

不过这题有个取巧的地方，就是

从底边出发

如果 $b_i < b_j$ , 则选用 $b_i$ 比 $b_j$ 的结果不会变差

因此可以对腰边和底边进行排序

然后使用双指针，进行贪心配对

import java.io.BufferedInputStream;
import java.util.Arrays;
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(new BufferedInputStream(System.in));
        int n = sc.nextInt();
        int[] arr = new int[n];
        int[] brr = new int[n];

        for (int i = 0; i < n; i++) {
            arr[i] = sc.nextInt();
        }
        for (int i = 0; i < n; i++) {
            brr[i] = sc.nextInt();
        }
        Arrays.sort(arr);
        Arrays.sort(brr);
        // 双指针
        int res = 0;
        int j = 0;
        for (int i = 0; i < n; i++) {
            while (j < n && arr[j] * 2 <= brr[i]) {
                j++;
            }
            if (j < n) {
                j++;
                res++;
            }
        }
        System.out.println(res);
    }

}

F. 计算方程

思路: 二分

因为其函数是单调的，呈现单调性

因此用二分是最优解

import java.io.BufferedInputStream;
import java.util.Scanner;

public class Main {

    static boolean check(int x, int k, int m) {
        double r1 = Math.sqrt(1.0 * x);
        double r2 = (int)(Math.log(x) / Math.log(k));
        return r1 + r2 > m;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(new BufferedInputStream(System.in));
        int t = sc.nextInt();
        while (t-- > 0) {
            int k = sc.nextInt(), m = sc.nextInt();
            int l = 1, r = m * m;
            while (l <= r) {
                int mid = l + (r - l) / 2;
                if (check(mid, k, m)) {
                    r = mid - 1;
                } else {
                    l = mid + 1;
                }
            }
            System.out.println(l);
        }
    }

}