2021年全国大学生计算机能力挑战赛（Java）决赛试题代码（外加部分试题）

一、前言

        前几天参加的比赛，今天在写题目的时候感觉和打比赛时有一题很类似，于是就凭借记忆稍微写一点东西。后面如果题目公布的话，我会补充上题目。

二、题目解答

        第一题内容记不得了，只有代码：

public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        int n = sc.nextInt();
        double avg=0;
        double sum=0;
        int sumpeople=0;
        double sumx=0;
        for(int i=0;i 
 
 
        第二题代码：
 
 
 public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        int m=sc.nextInt();
        if(n==m)
            System.out.println(0);
        else if(n>m){
            System.out.println(n-m);
        }
        else{
            int cnt=0;
            while(n 
 
 
        第三题：这题我大致记得，题目是这样描述的，有一个类似三阶魔方的正方体，有六个面，每个面九个方格。现在将每个面的中心块涂成绿色，每个面的拐角四个涂成红色，其余部分涂成蓝色。现在初始时，一个小人在任意一个面的中间，朝向任意一个方向。现在请你输入n+1行，其中第一行输入一个数n，代表n个 *** 作，接下来的n行可以输入“L”、“R”和“W”。其中L代表小人向左转但是位置不动，R代表小人向右转但是位置不动，W代表小人朝着现在的方向前进一格，小人一直在正方体面上运动。问n次 *** 作后，小人最后停留位置的颜色是什么？
 
 
        这道题，很明显需要使用矩阵进行计算，因为每个面都是一样的，所以我们只要选择一个面建立一个grid[3][3]即可。然后初始化值的时候分别对红绿蓝使用不同的数字标识，并且初始位置为（1,1）。初始方向任意，我们设为（1,0），然后我们可以定义一个方向数组，从左到右，如果是向右转，就查找当前数组的下一个数，否则就查找上一个数，注意边界判断即可。代码如下（不理解可评论区留言）：
 
public static void main(String[] args) {
        int [][]grid=new int[3][3];
        grid[1][1]=1;
        grid[0][0]=grid[2][0]=grid[2][2]=grid[0][2]=0;
        grid[1][0]=grid[0][1]=grid[2][1]=grid[1][2]=2;
        int [][]toward={{1,0},{0,-1},{-1,0},{0,1}};
        int[]first={1,0};
        int x=1,y=1;
        HashMap map=new HashMap<>();
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        sc.nextLine();
        for(int i=0;i 
 
 
第四题：这一题就是令我回忆的题目，内容大概也是第一行输入一个数n，第二行输入n个数，求这n个数的正序对数目。所谓正序对，指的就是如果两个数，前面一个比后面一个小，这两个数就构成正序对。例如：1,3,2,4的正序对有（1,3），（1,2），（1,4），（3,4），（2,4）。
 
 
        这道题目真的是，比赛前一天刚看过，归并排序的变式，只要在归并排序中加上一行记录正序对数目即可。如果暴力做的话，两个循环，是O(N^2)的复杂度，而n可以取10^5，所以肯定是会RE的，因此使用归并才是正解。代码如下：
 
 public static void main(String[] args) {
       Scanner sc=new Scanner(System.in);
       int n=sc.nextInt();
       int []arr=new int[n];
       for(int i=0;i>1);

        return process(arr,l,mid)+process(arr,mid+1,r)+merge(arr,l,mid,r);
    }
    public static int merge(int[]arr,int l,int m,int r){
        int[]help=new int[r-l+1];
        int i=0;
        int p1=l,p2=m+1;
        int res=0;
        while(p1<=m&&p2<=r){
            res+=(arr[p1]
 
 
 
 归并排序和其他经典排序精讲请看这篇博客！六大排序算法精讲
 
 
 
 
       第五题（最后一题）：具体也记不得了，反正用栈或者哈希表都挺容易的
 
 
public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        int M=sc.nextInt();
        int N=sc.nextInt();
        int cnt=0;
        Listlist=new ArrayList<>();

        for(int i=0;i 
 
三、结尾
 
        以上代码均为两小时内手敲，可能为了保证有分，并没有多么优化，如有错误，敬请斧正。
					
										


					

						
欢迎分享，转载请注明来源：内存溢出
原文地址: http://outofmemory.cn/zaji/5693391.html