温馨提示:这篇文章已超过476天没有更新,请注意相关的内容是否还可用!
摘要:第十四届蓝桥杯大赛软件赛省赛(Java 大学A组)是一场面向大学生的编程竞赛,旨在选拔和培养软件领域的优秀人才。该比赛采用Java编程语言,考察参赛者的算法设计、编程实现和问题解决能力。这场比赛为大学生提供了一个展示自己才能的舞台,同时也是提升编程技能、交流学习的好机会。
蓝桥杯 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) 10x∣yotherwise,对于正整数 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=20002000000−1dymy+1。因此我们用倍数法在线性时间复杂度意义下求出 d d d 与 m m m,将答案拆分成若干合法部分累加,最后得到正确答案。 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(0≤i≤4) 行第 j ( 0 ≤ j ≤ i ) \small j(0 ≤ j ≤ i) j(0≤j≤i) 个圆形的值。其中 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](i≤0),计算方式为 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[i−1][j] op arr[i−1][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[i−1][j]、arr[i−1][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 if (cir[n][i] == target) ++ans; } else { if (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 m≤500;
对于所有评测用例, 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 1≤n,m≤2000,1≤x1≤x2≤n,1≤y1≤y2≤m。
二维差分
如果我们用数字的奇偶性来表示黑白棋,用 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
试题 F: 阶乘的和
时间限制:3.0s 内存限制:512.0MB 本题总分:15 分
【问题描述】
给定 n \small n n 个数 A i \small A_i Ai,问能满足 m ! \small m! m! 为 ∑ i = 1 n ( A i ! ) \small \sum_{i=1}^n(A_i!) ∑i=1n(Ai!) 的因数的最大的 m \small m m 是多少。其中 m ! \small m! m! 表示 m \small m m 的阶乘,即 1 × 2 × 3 × ⋅ ⋅ ⋅ × m \small 1 × 2 × 3 × · · · × m 1×2×3×⋅⋅⋅×m。
【输入格式】
输入的第一行包含一个整数 n \small n n。
第二行包含 n \small n n 个整数,分别表示 A i \small A_i Ai,相邻整数之间使用一个空格分隔。
【输出格式】
输出一行包含一个整数表示答案。
【样例输入】
3 2 2 2【样例输出】
3【评测用例规模与约定】
对于 40 % \small 40\% 40% 的评测用例, n ≤ 5000 \small n ≤ 5000 n≤5000;
对于所有评测用例, 1 ≤ n ≤ 1 0 5 1 ≤ A i ≤ 1 0 9 \small 1 ≤ n ≤ 10^5\ 1 ≤ A_i ≤ 10^9 1≤n≤105 1≤Ai≤109。
贪心
如果我们尽可能的合并较小的阶乘,直至无法合并,如 2 ! + 2 ! + 2 ! = 3 × 2 ! = 3 ! 2!+2!+2!=3\times2!=3! 2!+2!+2!=3×2!=3!,我们取 3 3 3 作 m m m 一定最优,那么这种策略在任何情况都能受用吗?
首先我们将 A 1 , A 2 , ⋯ , A n A_1, A_2,\cdots,A_n A1,A2,⋯,An 按升序重排,即我们可以一般性假设 i >= 1, r >>= 1) { maxL += mark[l]; maxR += mark[r]; } return Math.max(maxL, maxR); } StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in))); int nextInt() { try { in.nextToken(); } catch (IOException e) { e.printStackTrace(); } return (int) in.nval; } }
试题 H: 太阳
时间限制:3.0s 内存限制:512.0MB 本题总分:20 分
【问题描述】
这天,小蓝在二维坐标系的点 ( X , Y ) \small (X, Y) (X,Y) 上放了一个太阳,看做点光源。
他拿来了 n \small n n 条线段,将它们平行于 x \small x x 轴放置在了坐标系中,第 i \small i i 条线段的左端点在 x i , y i \small x_i, y_i xi,yi,长度为 l i \small l_i li。线段之间不会有重合或部分重合的情况(但可能出现端点相交)。小蓝想知道有多少条线段能被太阳照亮(一条线段有长度大于 0 \small 0 0 的部分被照亮就算)。
【输入格式】
输入的第一行包含三个正整数 n , X , Y \small n, X, Y n,X,Y,相邻整数之间使用一个空格分隔。
接下来 n \small n n 行,第 i \small i i 行包含三个整数 x i , y i , l i \small x_i, y_i, l_i xi,yi,li,相邻整数之间使用一个空格分隔。
【输出格式】
输出一行包含一个正整数表示答案。
【样例输入】
3 10 2000000 5 3 5 6 2 4 0 1 10
【样例输出】
2
【评测用例规模与约定】
对于 30 % \small 30\% 30% 的评测用例, n ≤ 1000 \small n ≤ 1000 n≤1000;
对于所有评测用例, 1 ≤ n ≤ 100000 \small 1 ≤ n ≤ 100000 1≤n≤100000, 0 ≤ x i , X ≤ 1 0 7 \small 0 ≤ x_i, X ≤ 10^7 0≤xi,X≤107, 0 0\\c_1+c_2+\cdots+c_n\leq m}}\prod_{i=1}^nC_i\cdot\prod_{i=1}^nA_i. c1,c2,⋯,cn>0c1+c2+⋯+cn≤m∑i=1∏nAiCi=c1,c2,⋯,cn>0c1+c2+⋯+cn≤m∑i=1∏nCi⋅i=1∏nAi. 记 p ( n , m ) p(n,m) p(n,m) 为 ∑ c 1 , c 2 , ⋯ , c n > 0 c 1 + c 2 + ⋯ + c n ≤ m ∏ i = 1 n C i \sum_{\substack{c_1,c_2,\cdots,c_n > 0\\c_1+c_2+\cdots+c_n\leq m}}\prod_{i=1}^nC_i ∑c1,c2,⋯,cn>0c1+c2+⋯+cn≤m∏i=1nCi。因为在小于 n n n 的回合结束要耗尽能量,所以整理可以知最终答案为: p ( n , m ) ∏ i = 1 n A i + ∑ j = 1 n − 1 ( p ( j , m ) − p ( j , m − 1 ) ) ∏ i = 1 j A i . p(n,m)\prod_{i=1}^nA_i+\sum_{j=1}^{n-1}(p(j,m) -p(j,m-1))\prod_{i=1}^jA_i. p(n,m)i=1∏nAi+j=1∑n−1(p(j,m)−p(j,m−1))i=1∏jAi. 因此该思路下, p ( n , m ) p(n,m) p(n,m) 求解的复杂度与整体直接关联,考虑 p p p 的边界情况,当 n = 1 n=1 n=1 时, p ( 1 , m ) = 1 + 2 + ⋯ + m = m ( m + 1 ) 2 p(1,m) = 1+2+\cdots+m=\cfrac {m(m+1)}2 p(1,m)=1+2+⋯+m=2m(m+1)。考虑 n + 1 n+1 n+1 情况,枚举 C n + 1 C_{n+1} Cn+1 可能的取值 1 , 2 , ⋯ m − n 1,2,\cdots m-n 1,2,⋯m−n,则有递推式: p ( n , m ) = { 1 + 2 + ⋯ + m n = 1 ∑ i = 1 m − n + 1 i p ( i − 1 , m − i ) 1 = 1) { if (b % 2 == 1) res = res * a % mod; a = a * a % mod; } return res; } void run() { int n = nextInt(); long m = nextLong() % mod; long A = 1, p1 = 1, p2 = 1, ans = 0; for (int i = 1; i A = A * nextInt() % mod; p1 = p1 * (m + i) % mod * (m - i + 1) % mod * qpow(2 * i, mod - 2) % mod * qpow(2 * i - 1, mod - 2) % mod; p2 = p2 * (m - 1 + i) % mod * (m - i) % mod * qpow(2 * i, mod - 2) % mod * qpow(2 * i - 1, mod - 2) % mod; if (i == n) p2 = 0; ans = (ans + (p1 - p2) * A) % mod; } System.out.print((ans + mod) % mod); } BufferedReader in = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer token; String next() { while (token == null || !token.hasMoreTokens()) { try { token = new StringTokenizer(in.readLine()); } catch (IOException e) { e.printStackTrace(); } } return token.nextToken(); } int nextInt() { return Integer.parseInt(next()); } long nextLong() { return Long.parseLong(next()); } }
还没有评论,来说两句吧...