2021年第三届计算机能力挑战赛决赛java编程题第一套试卷

2021年第三届全国高校计算机能力挑战赛决赛（java）个人解答源码及思路（第一套试卷）1. 临近年末，A公司准备给公司员工分法奖品，每名员工都可以提出自己期望的奖品。为了安排采购，公司统计了各种奖品的价格以及选择此奖品的人数。假如你是采购人员，需要申请财务报销。请你计算出这批奖品的总体价格标准差。公式中数值X1，X2，X3，.XN（皆为实数），其平均值（算术平均值）为，标准差为。输入格式：第一行，输入一个数字n(n1000），表示奖品的种类。之后共n行，每行输入一个正整数x和一个浮点数y，分别表示选择某种奖品的人数和此奖品的价格。(0<x1000,0<y1000)输出格式：输出此奖品的总体价格标准差（四舍五入保留2位有效数字）。输入样例：420 50.0022 65.5018 80.0025 45.00输出样例：13.45参考源码：1. import java.text.DecimalFormat;2. import java.util.Scanner;3. public class FirstProblemFinal 4.     public static void main(String args) 5.         Scanner scan = new Scanner(System.in);6.         int n = scan.nextInt();7.         int number = new intn;8.         double price = new doublen;9.         double averagePrice = 0;10.         double totalPrice = 0;11.         /总样本数12.         int totalNumber = 0;13.         for (int i = 0; i < n; i+) 14.             int x = scan.nextInt();15.             double y = scan.nextDouble();16.             numberi = x;17.             pricei = y;18.             totalPrice += x * y;19.             totalNumber += x;20.         21.         averagePrice = totalPrice / totalNumber;22.         double squreValue = 0;23.         for (int i = 0; i < n; i+) 24.             squreValue += numberi * (pricei - averagePrice) * (pricei - averagePrice);25.26.         27.         squreValue = squreValue / totalNumber;28.         DecimalFormat df = new DecimalFormat("0.00");29.         System.out.println(df.format(Math.sqrt(squreValue);30.     31.32. 算法思路： 模拟算法，注意公式中的N是总样本数。运行截图：2.假如你可以对数字进行如下两种操作：操作一：将当前数×2。操作二：将当前数-1。现在给出两个数n，m（0<n,m1000），请问你最少需要多少次操作才能将n变成m？输入格式：共一行，两个数字n，m。输出格式：输出最少的操作次数。输入样例：2 17输出样例：8参考源码：1. import java.util.Scanner;2. public class SecondProblemFinal 3.     public static void main(String args) 4.         Scanner sc = new Scanner(System.in);5.         int n = sc.nextInt();6.         int m = sc.nextInt();7.         if (n = m) 8.             System.out.println(0);9.             return;10.         11.         if (n > m) 12.             System.out.println(n - m);13.             return;14.         15.         int count = 0;16.         while (n < m) 17.             if (m % 2 = 0) 18.                 m /= 2;19.                 count+;20.              else 21.                 m += 1;22.                 m /= 2;23.                 count += 2;24.             25.         26.         count+=n-m;27.         System.out.println(count);28.     29. 算法思路：转换后的等式有下面3种形式：表达式（含n）*2=m；表达式(含n)*2-1=m; 表达式(含n)-1=m。然后逆推，由m来求n。这道题如果调整为将计算表达式输出，例如：(2*2-1)*2-1)*2-1)*2-1=17，将增加一定的难度，需要用到栈（括号匹配问题）数据结构。运行截图：测试用例1(2*2-1)*2-1)*2-1)*2-1=17测试用例2(6-1)*2=10(3-1)*2*2=83.假如有一个3*3*3的立方体，它有六个面，每个面共有九个小正方形。每小正方形按如下规则染色：角上的方格为red，中心的方格为green，其他的方格为blue。初始有一个机器人站在立方体顶面的中心，面朝一个blue方格。它将接受到n条如下指令：'L'：为左转90度，'R'为：右转90度，'W'：为向前走一格。机器人可以穿过立方体的棱到达另一个面。给出指令，求出机器人最后所在格子的颜色。输入格式：第一行共一个数字n（0<n106），表示指令的条数。接下来共n行，每行一个大写字母'L'或'R'或'W'。输出格式：输出一行小写字母，表示机器人最后所在格子的颜色(red,green,blue)输入样例：7WWLWWRW输出样例：blue参考源码：1. import java.util.Scanner;2. public class ThirdProblemFinal 3.     public static void main(String args) 4.         /3*3的颜色二维数组(坐标）5.         /*6.          * red   blue   red7.          * blue  green  blue8.          * red   blue   red9.          */10.         String positions = new String33;11.         positions00 = "red"12.         positions01 = "blue"13.         positions02 = "red"14.         positions10 = "blue"15.         positions11 = "green"16.         positions12 = "blue"17.         positions20 = "red"18.         positions21 = "blue"19.         positions22 = "red"20.         /四个方向（上，右，下，左）前进一步，先后位置（X和Y)之间的差值21.         int dx = -1, 0, 1, 0;22.         int dy = 0, 1, 0, -1;23.         Scanner scan = new Scanner(System.in);24.         int n = scan.nextInt();25.         /W R D L 上右下左26.         /0 1 2 327.         int directions = 0;28.         int x = 1, y = 1;29.         for (int i = 0; i < n; i+) 30.             String command = scan.next();31.             if ("L".equals(command) 32.                 directions = (directions + 3) % 4;33.              else if ("R".equals(command) 34.                 directions = (directions + 1) % 4;35.              else 36.                 x += dxdirections;37.                 y += dydirections;38.                 x = (x + 3) % 3;39.                 y = (y + 3) % 3;40.             41.         42.43.         System.out.println(positionsxy);44.     45.46. 算法思路： 设置一个3*3的二维数组作为一面，其余面的下标（坐标）对3取余；四个方向的转动(通过L或者R)对4去余。运行截图：测试用例1测试用例2（连续旋转）测试用例3（连续旋转）测试用例44.输入一个正整数n，之后输入n个十六进制正整数，输出这n个数中正序对的个数。正序对：设 A为一个有n个数