16582.十二生肖【算法赛】

蓝桥杯题库 题目链接。

常识，打卡题

生肖排名：鼠、牛、虎、兔、龙、蛇、马、羊、猴、鸡、狗、猪

龙排第 5 直接输出即可

Python3代码

print(5)

16577.欢迎参加福建省大学生程序设计竞赛【算法赛】

蓝桥杯题库 题目链接。

模拟

题意：相同题数、相同罚时的队伍归为一类，最终共有多少类队伍？

思路：

创建一个二维数组counts，两个维度分别表示 题数 和 罚时 。

例如：

• counts[2][960] = 1 表示有队伍做了2题同时罚时为960。
• counts[3][700] = 0 表示没有任何一支队伍做了3题同时罚时为700。

注：counts[a][b]的值只有 0 和 1 两种值分别表示有没有队伍做了a题同时罚时为b。如果有两只队伍的题数和罚时相等，counts的值也为 1 因为他们是一类队伍只需要统计一次即可。

最后遍历数组 counts 累加其中的 1 即可。

Java代码

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        int[][] counts = new int[14][3000];
        int ans = 0;
        for (int i = 0; i < n; i++) {
            int a = scan.nextInt();
            int b = scan.nextInt();
            counts[a][b] = 1;
        }
        for (int i = 0; i < 14; i++) {
            for (int j = 0; j < 3000; j++) {
                if (counts[i][j] == 1) {
                    ans++;
                }
            }
        }
        System.out.println(ans);
        scan.close();
    }
}

16583.匹配二元组的数量【算法赛】

蓝桥杯题库 题目链接。

数学，枚举

思路：

公式 Ai / j = Aj / i可以转换为 Ai * i = Aj * j

我们将数组nums根据这个公式进行处理，使nums[i] = nums[i] * i。问题就转换为了寻找处理后的数组nums中有多少对相等元素。

(需要注意的是：为了满足条件，nums数组下标要从 1 开始，因为分母不能等于 0 ，并且1 ≤ i < j)

步骤：

1. 转换数组，使nums[i] = nums[i] * i
2. 对数组 nums 进行排序
3. 排序之后，值相等的元素就会相邻在一起。
4. 假如遇到nums = 1, 2, 3, 3, 3, 3。对其中有count (4)个3，就能组成count * (count - 1) / 2种成对的组合
5. 累加count * (count - 1) / 2

Java代码

import java.util.Scanner;
import java.util.Arrays;
// 计算ai / j == aj / i等价于计算ai * i == aj * j
// 即计算下标和元素值相乘的结果是否相等
public class Main {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        long[] nums = new long[n + 1];
        long ans = 0;
        // 因为分母不能为0，所以下标要从1开始。
        // 这里初始化为-1的目的是为了后面排序在第一位
        nums[0] = -1; 
        for (int i = 1; i <= n; i++) {
            long tmp = scan.nextLong();
            // 数组直接初始化为 Ai * i 的形式
            nums[i] = tmp * i;
        }
        Arrays.sort(nums);
        // count 用于统计当前元素周围有几个相等的元素
        int count = 1;
        for (int i = 2; i <= n; i++) {
            if (nums[i] == nums[i - 1]) {
                count++;
            } else {
                ans += count * (count - 1) / 2;
                count = 1;
            }
        }
        // 防止数组结尾的相邻相同元素未统计到
        ans += count * (count - 1) / 2;
        System.out.println(ans);
        scan.close();
    }
}

16822.元素交换【算法赛】

蓝桥杯题库 题目链接。

思维

思路：

本题可以交换任意两个元素的位置。我们只需要比较 初始状态 和 最终状态 的区别。

最终状态只有两种情况:

• 状态一：10101010...
• 状态二：01010101...

假如初始状态为 11000110 ，最终状态为状态一 10101010 因为可以交换任意两个元素的位置，我们只需要从第一位开始向后比较是否和最终状态相同。

假设我们看 1 这个元素的位置，我们发现状态一的 1 都在奇数位置。我们只需要遍历初始状态，判断奇数位置是否为 1 。如果不为 1 说明我们需要从别的某个位置交换过来一个 1 。这个时候累加结果 ans 即可。

注意：因为最终状态有两种，所以开始要定义两个ans，最后输出小的那一个。

具体代码如下：

Java代码

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        int ans1 = 0, ans2 = 0;
        for (int i = 1; i <= 2 * n; i++) {
            int b = scan.nextInt();
            if (i % 2 == 1 && b == 1) {
                ans1++;
            } else if (i % 2 == 1 && b == 0) {
                ans2++;
            }
        }
        System.out.println(Math.min(ans1, ans2));
        scan.close();
    }
}

16578.下棋的贝贝【算法赛】

蓝桥杯题库 题目链接。

思维

题意：

每个棋子在坐标中会给上下左右四个位置的棋子增加一层buff，求 n 个棋子怎么放置buff总数最多为多少？

思路：

显而易见当棋子组成一个大正方形时buff最多。我们可以计算 n 个棋子能组成的最大正方形，再将剩余的棋子围到正方形的某一条边即可。

剩余的棋子不会超过两倍边长，因为超过两倍边长的话就围成了一个更大的正方形，和上一步冲突

步骤：

1. 使用sqrt函数求大正方形边长，例如(int) sqrt(11) = 3表示11个棋子能围成的最大正方形边长为3
2. 计算大正方形的总buff。
3. 计算剩余棋子能够提供的buff。

C++代码

#include<bits/stdc++.h>
using namespace std;

int main(){
    long long n, side, remain, ans = 0;
    cin >> n;
    side = sqrt(n);
    // 计算大正方形的贡献 4角 + 4条边 + 内部
    ans += (4 * 2) + ((side - 2) * 4 * 3) + ((side - 2) * (side - 2) * 4);
    remain = n - side * side;

    if (remain > 0 && remain <= side) {
        // 剩余棋子小于等于一条边
        ans += 4 * remain - 2;
    }
    else if (remain > side) {
        ans += 4 * remain - 4;
    }
    cout << ans << endl;
    return 0;
}

Java代码

import java.util.Scanner;  
  
public class Main {  
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        long n = scan.nextLong();
        long side = (long) Math.sqrt(n);
        long ans = 0;

        // 计算正方形的邻居数量总合
        ans += 4 * 2;
        ans += (side - 2) * 4 * 3;
        ans += (side - 2) * (side - 2) * 4;
        
        // 剩余棋子
        long remain = n - side * side;
        if (remain > 0 && remain <= side) {
            // 剩余棋子小于等于一条边
            ans += 4 * remain - 2;
        }
        else if (remain > side) {
            ans += 4 * remain - 4;
        }
        System.out.println(ans);
        scan.close();
    }   
}

更多题解访问: githubgitee