第十四届蓝桥杯大赛软件赛省赛(Java 大学A组) 第十四届蓝桥杯大赛软件赛省赛 Java 大学 A 组

蓝桥杯 2023年省赛真题
Java 大学A组

试题 A: 特殊日期
试题 B: 与或异或
试题 C: 平均
试题 D: 棋盘
试题 E: 互质数的个数
试题 F: 阶乘的和
试题 G: 小蓝的旅行计划
试题 H: 太阳
试题  I: 高塔
试题 J: 反异或 01 串



那么根据这个夹逼定理我们容易得出湖北经济学院趋近于武大华科。



试题 A: 特殊日期

本题总分5


【问题描述】

  记一个日期为 y y \small yy yy m m \small mm mm d d \small dd dd 日,统计从 2000 \small 2000 2000 1 \small 1 1 1 \small 1 1 日到 2000000 \small 2000000 2000000 1 \small 1 1 1 \small 1 1 日,有多少个日期满足年份 y y \small yy yy 是月份 m m \small mm mm 的倍数,同时也是 d d \small dd dd 的倍数。

【答案提交】

  这是一道结果填空的题,你只需要算出结果后提交即可。本题的结果为一个整数,在提交答案时只填写这个整数,填写多余的内容将无法得分。


35813063


朴素解法


  考虑到以日为单位计量,时间段的阶并不大,因此直接使用java.time.LocalDate模拟日期变化,判断然后累加,程序在笔者 P C \rm PC PC 运行 15 15 15 秒后得到了答案。

import java.time.LocalDate;
public class Main {
 public static void main(String ...args) { new Main().run(); }
 LocalDate start = LocalDate.of(2000, 1, 1);
 LocalDate end = LocalDate.of(2000000, 1, 1);
 void run() {
 long ans = 0;
 for (LocalDate i = start; i.compareTo(end) 

倍数法


  设函数 f y ( x ) = { 1 x   ∣   y 0 o t h e r w i s e f_y(x) = \begin{cases} 1 & x\,|\,y\\ 0 & \rm otherwise \end{cases} fy(x)={10xyotherwise,对于正整数 y y y,记 d y d_y dy ∑ x = 1 31 f y ( x ) \sum_{x=1}^{31}f_y(x) x=131fy(x) m y m_y my ∑ x = 1 12 f y ( x ) \sum_{x=1}^{12} f_y(x) x=112fy(x),则在不考虑日期是否合法的情况下,答案为 ∑ y = 2000 2000000 − 1 d ⁡ y m ⁡ y + 1 \sum_{y=2000}^{2000000 - 1} \operatorname{d}_y\operatorname{m}_y+1 y=200020000001dymy+1。因此我们用倍数法在线性时间复杂度意义下求出 d d d m m m,将答案拆分成若干合法部分累加,最后得到正确答案。

import java.util.function.IntPredicate;
import java.util.stream.IntStream;
public class Main {
 public static void main(String ...args) { new Main().run(); }
 void run() {
 System.out.println(
 calc(IntStream.rangeClosed(1, 12), IntStream.range(1, 29), y -> true)
 + calc(IntStream.of(2), IntStream.of(29), y -> y % 100 == 0 ? (y % 400 == 0) : (y % 4 == 0))
 + calc(IntStream.iterate(1, m -> m == 1 ? 3 : m + 1).limit(11), IntStream.rangeClosed(29, 30), y -> true)
 + calc(IntStream.of(1, 3, 5, 7, 8, 10, 12), IntStream.of(31), y -> true)
 + 1
 );
 }
 final int start = 2000, end = 2000000;
 int calc(IntStream m, IntStream d, IntPredicate yf) {
 int[] my = new int[end + 1];
 int[] dy = new int[end + 1];
 m.forEach(
 a -> {
 for (int i = 1; i * a {
 for (int i = 1; i * a my[a] * dy[a]
 ).sum();
 }
}

  帅是帅,但放在竞赛中性价比极低,编程多耗费时间都够你针对朴素解法的程序给出好几个测试用例了。



试题 B: 与或异或

本题总分5


【问题描述】

  小蓝有一张门电路的逻辑图,如下图所示 : :

  图中每个三角形代表着一种门电路,可能是与门、或门、异或门中的任何一种,它接受上一层中的两个圆形中的数据作为输入,产生一个输出值输出到下一级(如图中箭头所示)。图中圆形表示的是暂存的输出结果,取值只可能是 0 \small 0 0 1 \small 1 1,为了便于表示我们用 a r r [ i ] [ j ] \small arr[i][ j] arr[i][j] 表示第 i ( 0 ≤ i ≤ 4 ) \small i(0 ≤ i ≤ 4) i(0i4) 行第 j ( 0 ≤ j ≤ i ) \small j(0 ≤ j ≤ i) j(0ji) 个圆形的值。其中 a r r [ 0 ] = ( I n [ 0 ] , I n [ 1 ] , I n [ 2 ] , I n [ 3 ] , I n [ 4 ] ) \small arr[0] = (In[0], In[1], In[2], In[3], In[4]) arr[0]=(In[0],In[1],In[2],In[3],In[4]) 表示的是输入数据,对于某个 a r r [ i ] [ j ] ( i ≤ 0 ) \small arr[i][ j](i ≤ 0) arr[i][j](i0),计算方式为 a r r [ i ] [ j ] = a r r [ i − 1 ] [ j ]   o p   a r r [ i − 1 ] [ j + 1 ] \small arr[i][ j] = arr[i − 1][ j]\ op\ arr[i − 1][ j + 1] arr[i][j]=arr[i1][j] op arr[i1][j+1],其中 o p \small op op 表示的是将 a r r [ i − 1 ] [ j ] 、 a r r [ i − 1 ] [ j + 1 ] \small arr[i − 1][ j]、arr[i − 1][ j + 1] arr[i1][j]arr[i1][j+1] 作为输入,将 a r r [ i ] [ j ] \small arr[i][ j] arr[i][j] 作为输出的那个门电路,与门、或门、异或门分别对应于按位与 ( & ) \small (\&) (&)、按位或 (   ∣   ) \small (\:|\:) ()、按位异或 (   \small (\, (^   ) \small \,) ) 运算符。

  现在已知输入为 I n [ 0 ] = 1 , I n [ 1 ] = 0 , I n [ 2 ] = 1 , I n [ 3 ] = 0 , I n [ 4 ] = 1 \small In[0] = 1, In[1] = 0, In[2] = 1, In[3] = 0, In[4] = 1 In[0]=1,In[1]=0,In[2]=1,In[3]=0,In[4]=1,小蓝想要使得最终的输出 O u t \small Out Out 的值为 1 \small 1 1,请问一共有多少种不同的门电路组合方式?其中上图中显示的就是一种合法的方式。

【答案提交】

  这是一道结果填空的题,你只需要算出结果后提交即可。本题的结果为一个整数,在提交答案时只填写这个整数,填写多余的内容将无法得分。


30528


深度优先搜索


  暴搜杯!我的青春回来了,开搜!

public class Main {
 public static void main(String ...args) { new Main().run(); }
 int[][] cir = new int[6][6];
 int ans = 0, target = 1;
 void run() {
 cir[5] = new int[]{ 0, 1, 0, 1, 0, 1 };
 dfs(1, 5);
 System.out.println(ans);
 }
 void dfs(int i, int n) {
 if (n 


试题 C: 平均

时间限制3.0s 内存限制512.0MB 本题总分10


【问题描述】

  有一个长度为 n \small n n 的数组( n \small n n 10 \small 10 10 的倍数),每个数 a i \small a_i ai 都是区间 [ 0 , 9 ] \small [0, 9] [0,9] 中的整数。小明发现数组里每种数出现的次数不太平均,而更改第 i \small i i 个数的代价为 b i \small b_i bi,他想更改若干个数的值使得这 10 \small 10 10 种数出现的次数相等(都等于 n 10 \small \frac n{10} 10n ),请问代价和最少为多少。

【输入格式】

  输入的第一行包含一个正整数 n \small n n

  接下来 n \small n n 行,第 i \small i i 行包含两个整数 a i , b i \small a_i, b_i ai,bi,用一个空格分隔。

【输出格式】

  输出一行包含一个正整数表示答案。

【样例输入】

10
1 1
1 2
1 3
2 4
2 5
2 6
3 7
3 8
3 9
4 10

【样例输出】

27

【样例说明】

  只更改第 1 , 2 , 4 , 5 , 7 , 8 \small 1, 2, 4, 5, 7, 8 1,2,4,5,7,8 个数,需要花费代价 1 + 2 + 4 + 5 + 7 + 8 = 27 \small 1 + 2 + 4 + 5 + 7 + 8 = 27 1+2+4+5+7+8=27

【评测用例规模与约定】

  对于 20 % \small 20\% 20% 的评测用例, n ≤ 1000 \small n ≤ 1000 n1000
  对于所有评测用例, n ≤ 100000 , 0 < b i ≤ 2 × 1 0 5 \small n ≤ 100000, 0 < bi ≤ 2 × 10^5 n100000,0<bi2×105


贪心


  记 [ 0 , 9 ] [0, 9] [0,9] 中的整数 x x x 修改为整数 y y y 的操作为 x ↦ c y x\xmapsto{c}y xcy,即花费代价 c c c x x x 修改为 y y y,如果一个方案中同时出现 x ↦ c 1 y 、 y ↦ c 2 z x\xmapsto{c_1}y、y\xmapsto{c_2}z xc1yyc2z,那么使用 x ↦ c 1 z x\xmapsto{c_1}z xc1z 替换掉这两个操作就能使总代价减小 c 2 c_2 c2,即原方案一定非最优。容易归纳出最优方案中一定不存在长度大于 1 1 1 的路径(将 x ↦ y 、 y ↦ z x\xmapsto{}y、y\xmapsto{}z xyyz 看作长度为 2 2 2 的路径),那么方案要满足题意只能取每个整数超出目标出现次数 n 10 \frac n{10} 10n 的部分,在这个基础上最小代价和就是每个整数取超出部分个最小代价之和。

import java.io.StreamTokenizer;
import java.io.InputStreamReader;
import java.io.BufferedReader;
import java.io.IOException;
import java.util.Arrays;
public class Main {
 public static void main(String ...args) { new Main().run(); }
 int[] buffer = new int[200000], cnt = new int[10];
 void run() {
 int n = nextInt(), m = n / 10;
 long ans = 0;
 for (int i = 0; i < n; ++i) {
 buffer[i] = nextInt();
 buffer[i] |= nextInt() = 0; --i)
 if (++cnt[buffer[i] & 0xf] > m)
 ans += buffer[i] >> 4;
 System.out.println(ans);
 }
 StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
 int nextInt() {
 try {
 in.nextToken();
 } catch (IOException e) {
 e.printStackTrace();
 }
 return (int) in.nval;
 }
}

  实现上可以将 a i , b i a_i, b_i ai,bi 用一个整形表示,以减少排序的开销,也可以按 a i a_i ai b i b_i bi 分类再依次排序。



试题 D: 棋盘

时间限制3.0s 内存限制512.0MB 本题总分10


【问题描述】

  小蓝拥有 n × n \small n × n n×n 大小的棋盘,一开始棋盘上全都是白子。小蓝进行了 m \small m m 次操作,每次操作会将棋盘上某个范围内的所有棋子的颜色取反 (也就是白色棋子变为黑色,黑色棋子变为白色)。请输出所有操作做完后棋盘上每个棋子的颜色。

【输入格式】

  输入的第一行包含两个整数 n , m \small n, m n,m,用一个空格分隔,表示棋盘大小与操作数。

  接下来 m m m 行每行包含四个整数 x 1 , y 1 , x 2 , y 2 \small x_1, y_1, x_2, y_2 x1,y1,x2,y2,相邻整数之间使用一个空格分隔,表示将在 x 1 \small x_1 x1 x 2 \small x_2 x2 行和 y 1 \small y_1 y1 y 2 \small y_2 y2 列中的棋子颜色取反。

【输出格式】

  输出 n \small n n 行,每行 n \small n n 0 \small 0 0 1 \small 1 1 表示该位置棋子的颜色。如果是白色则输出 0 \small 0 0,否则输出 1 \small 1 1

【样例输入】

3 3
1 1 2 2
2 2 3 3
1 1 3 3

【样例输出】

001
010
100

【评测用例规模与约定】

  对于 30 % \small 30\% 30% 的评测用例, n   m ≤ 500 \small n\ m ≤ 500 n m500
  对于所有评测用例, 1 ≤ n , m ≤ 2000 , 1 ≤ x 1 ≤ x 2 ≤ n , 1 ≤ y 1 ≤ y 2 ≤ m \small 1 ≤ n, m ≤ 2000,1 ≤ x_1 ≤ x_2 ≤ n,1 ≤ y_1 ≤ y_2 ≤ m 1n,m20001x1x2n1y1y2m


二维差分


  如果我们用数字的奇偶性来表示黑白棋,用 n × n n\times n n×n 大小且元素全为 0 0 0 的矩阵来表示初始棋盘,容易发现对棋盘 x 1 \small x_1 x1 x 2 \small x_2 x2 行和 y 1 \small y_1 y1 y 2 \small y_2 y2 列中的棋子颜色取反的操作与对矩阵 x 1 \small x_1 x1 x 2 \small x_2 x2 行和 y 1 \small y_1 y1 y 2 \small y_2 y2 列中的元素加 1 1 1 的操作等价,我们只需要所有操作结束后的棋盘状态,很典型的二维差分问题。
  实现上用到了异或运算在相加上不进位与 0 0 0 1 1 1 A S C I I \rm ASCII ASCII 相邻的特性。

import java.io.PrintWriter;
import java.io.StreamTokenizer;
import java.io.InputStreamReader;
import java.io.BufferedReader;
import java.io.IOException;
public class Main {
 public static void main(String ...args) { new Main().run(); }
 byte[][] low = new byte[2002][2002];
 void run() {
 PrintWriter out = new PrintWriter(System.out);
 int n = nextInt(), m = nextInt();
 for (int i = 0; i < m; ++i) {
 int x = nextInt(), y = nextInt();
 int k = nextInt(), g = nextInt();
 low[x][y] ^= 1;
 low[x][g + 1] ^= 1;
 low[k + 1][y] ^= 1;
 low[k + 1][g + 1] ^= 1;
 }
 for (int i = 1; i 


试题 E: 互质数的个数

时间限制3.0s 内存限制512.0MB 本题总分15


【问题描述】

  给定 a , b \small a, b a,b,求 1 ≤ x < a b \small 1 ≤ x < a^b 1x<ab 中有多少个 x \small x x a b \small a^b ab 互质。由于答案可能很大,你只需要输出答案对 998244353 \small 998244353 998244353 取模的结果。

【输入格式】

  输入一行包含两个整数分别表示 a , b \small a, b a,b,用一个空格分隔。

【输出格式】

  输出一行包含一个整数表示答案。

【样例输入 1】

2 5

【样例输出 1】

16

【样例输入 2】

12 7

【样例输出 2】

11943936

【评测用例规模与约定】

  对于 30 % \small 30\% 30% 的评测用例, a b ≤ 1 0 6 \small a^b ≤ 10^6 ab106
  对于 70 % \small 70\% 70% 的评测用例, a ≤ 1 0 6 , b ≤ 1 0 9 \small a ≤ 10^6,b ≤ 10^9 a106b109
  对于所有评测用例, 1 ≤ a ≤ 1 0 9 , 1 ≤ b ≤ 1 0 18 \small 1 ≤ a ≤ 10^9,1 ≤ b ≤ 10^{18} 1a1091b1018


欧拉函数


  欧拉函数是积性函数,其形式为 φ ( n ) \varphi(n) φ(n),表示小于等于 n n n 且与 n n n 互质的正整数的个数,因此当 a b = 1 a^b =1 ab=1 时答案为 0 0 0 φ ( 1 ) = 1 \varphi(1)=1 φ(1)=1