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

马肤

温馨提示:这篇文章已超过476天没有更新,请注意相关的内容是否还可用!

摘要:第十四届蓝桥杯大赛软件赛省赛(Java 大学A组)是一场面向大学生的编程竞赛,旨在选拔和培养软件领域的优秀人才。该比赛采用Java编程语言,考察参赛者的算法设计、编程实现和问题解决能力。这场比赛为大学生提供了一个展示自己才能的舞台,同时也是提升编程技能、交流学习的好机会。

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

 试题 A: 特殊日期

 试题 B: 与或异或

 试题 C: 平均

 试题 D: 棋盘

 试题 E: 互质数的个数

 试题 F: 阶乘的和

 试题 G: 小蓝的旅行计划

 试题 H: 太阳

 试题  I: 高塔

 试题 J: 反异或 01 串


第十四届蓝桥杯大赛软件赛省赛(Java 大学A组),第十四届蓝桥杯大赛软件赛省赛Java大学A组竞赛开启 第1张

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



试题 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) 10​x∣yotherwise​,对于正整数  
     
      
       
       
         y 
        
       
      
        y 
       
      
    y,记  
     
      
       
        
        
          d 
         
        
          y 
         
        
       
      
        d_y 
       
      
    dy​为 
     
      
       
        
        
          ∑ 
         
         
         
           x 
          
         
           = 
          
         
           1 
          
         
        
          31 
         
        
        
        
          f 
         
        
          y 
         
        
       
         ( 
        
       
         x 
        
       
         ) 
        
       
      
        \sum_{x=1}^{31}f_y(x) 
       
      
    ∑x=131​fy​(x), 
     
      
       
        
        
          m 
         
        
          y 
         
        
       
      
        m_y 
       
      
    my​为 
     
      
       
        
        
          ∑ 
         
         
         
           x 
          
         
           = 
          
         
           1 
          
         
        
          12 
         
        
        
        
          f 
         
        
          y 
         
        
       
         ( 
        
       
         x 
        
       
         ) 
        
       
      
        \sum_{x=1}^{12} f_y(x) 
       
      
    ∑x=112​fy​(x),则在不考虑日期是否合法的情况下,答案为  
     
      
       
        
        
          ∑ 
         
         
         
           y 
          
         
           = 
          
         
           2000 
          
         
         
         
           2000000 
          
         
           − 
          
         
           1 
          
         
        
        
         
         
           d 
          
         
           ⁡ 
          
         
        
          y 
         
        
        
         
         
           m 
          
         
           ⁡ 
          
         
        
          y 
         
        
       
         + 
        
       
         1 
        
       
      
        \sum_{y=2000}^{2000000 - 1} \operatorname{d}_y\operatorname{m}_y+1 
       
      
    ∑y=20002000000−1​dy​my​+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 分

【问题描述】

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

第十四届蓝桥杯大赛软件赛省赛(Java 大学A组),第十四届蓝桥杯大赛软件赛省赛Java大学A组竞赛开启 第2张

  图中每个三角形代表着一种门电路,可能是与门、或门、异或门中的任何一种,它接受上一层中的两个圆形中的数据作为输入,产生一个输出值输出到下一级(如图中箭头所示)。图中圆形表示的是暂存的输出结果,取值只可能是 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∏n​Ai​Ci​=c1​,c2​,⋯,cn​>0c1​+c2​+⋯+cn​≤m​∑​i=1∏n​Ci​⋅i=1∏n​Ai​.  记 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=1n​Ci​。因为在小于 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∏n​Ai​+j=1∑n−1​(p(j,m)−p(j,m−1))i=1∏j​Ai​.  因此该思路下, 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()); } }


0
收藏0
文章版权声明:除非注明,否则均为VPS857原创文章,转载或复制请以超链接形式并注明出处。

相关阅读

  • 【研发日记】Matlab/Simulink自动生成代码(二)——五种选择结构实现方法,Matlab/Simulink自动生成代码的五种选择结构实现方法(二),Matlab/Simulink自动生成代码的五种选择结构实现方法详解(二)
  • 超级好用的C++实用库之跨平台实用方法,跨平台实用方法的C++实用库超好用指南,C++跨平台实用库使用指南,超好用实用方法集合,C++跨平台实用库超好用指南,方法与技巧集合
  • 【动态规划】斐波那契数列模型(C++),斐波那契数列模型(C++实现与动态规划解析),斐波那契数列模型解析与C++实现(动态规划)
  • 【C++】,string类底层的模拟实现,C++中string类的模拟底层实现探究
  • uniapp 小程序实现微信授权登录(前端和后端),Uniapp小程序实现微信授权登录全流程(前端后端全攻略),Uniapp小程序微信授权登录全流程攻略,前端后端全指南
  • Vue脚手架的安装(保姆级教程),Vue脚手架保姆级安装教程,Vue脚手架保姆级安装指南,Vue脚手架保姆级安装指南,从零开始教你如何安装Vue脚手架
  • 如何在树莓派 Raspberry Pi中本地部署一个web站点并实现无公网IP远程访问,树莓派上本地部署Web站点及无公网IP远程访问指南,树莓派部署Web站点及无公网IP远程访问指南,本地部署与远程访问实践,树莓派部署Web站点及无公网IP远程访问实践指南,树莓派部署Web站点及无公网IP远程访问实践指南,本地部署与远程访问详解,树莓派部署Web站点及无公网IP远程访问实践详解,本地部署与远程访问指南,树莓派部署Web站点及无公网IP远程访问实践详解,本地部署与远程访问指南。
  • vue2技术栈实现AI问答机器人功能(流式与非流式两种接口方法),Vue2技术栈实现AI问答机器人功能,流式与非流式接口方法探究,Vue2技术栈实现AI问答机器人功能,流式与非流式接口方法详解
  • 发表评论

    快捷回复:表情:
    评论列表 (暂无评论,0人围观)

    还没有评论,来说两句吧...

    目录[+]

    取消
    微信二维码
    微信二维码
    支付宝二维码