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

 试题 A: 特殊日期
 试题 B: 与或异或
 试题  I: 高塔

---

把填空挂上跟大伙对对答案，然后 $\mathrm{I}$ 题出的还行就先讲讲，剩下的最近有点忙，先放放。

---

试题 A: 特殊日期

本题总分：5 分

【问题描述】

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

【答案提交】

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

---

35813063

---

朴素解法

---

  考虑到以日为单位计量，时间段的阶并不大，因此直接使用java.time.LocalDate模拟日期变化，判断然后累加，程序在笔者 $\mathrm{PC}$ 运行 $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) <= 0; i = i.plusDays(1))
            if (i.getYear() % i.getMonthValue() == 0 
                    && i.getYear() % i.getDayOfMonth() == 0) ++ans;
        System.out.println(ans);
    }
}

---

倍数法

---

  设函数 $f_y(x)=\{\begin{array}{ll}1& x|y\\ 0& \mathrm{otherwise}\end{array}$，对于正整数 $y$，记 $d_y$为${\sum }_{x=1}^{31}{f}_y(x)$，$m_y$为${\sum }_{x=1}^{12}{f}_y(x)$，则在不考虑日期是否合法的情况下，答案为 ${\sum }_{y=2000}^{2000000-1}{d}_y\cdot m_y+1$。因此我们用倍数法在线性时间复杂度意义下求出 $d$ 与 $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 <= end; ++i) ++my[i * a];
                }
        );
        d.forEach(
                a -> {
                    for (int i = 1; i * a <= end; ++i) ++dy[i * a];
                }
        );
        return IntStream.range(start, end).filter(yf).map(
                a -> my[a] * dy[a]
        ).sum();
    }
}

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

---

试题 B: 与或异或

本题总分：5 分

【问题描述】

  小蓝有一张门电路的逻辑图，如下图所示$：$

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

  现在已知输入为 $In[0]=1,In[1]=0,In[2]=1,In[3]=0,In[4]=1$，小蓝想要使得最终的输出 $Out$ 的值为 $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 <= 1) {
            if (cir[n][i] == target) ++ans;
        } else {
            if (i < n) {
                cir[n - 1][i] = cir[n][i] & cir[n][i + 1];
                dfs(i + 1, n);
                cir[n - 1][i] = cir[n][i] | cir[n][i + 1];
                dfs(i + 1, n);
                cir[n - 1][i] = cir[n][i] ^ cir[n][i + 1];
                dfs(i + 1, n);
            } else {
                dfs(1, n - 1);
            }
        }
    }
}

---

试题  I: 高塔

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

【问题描述】

  小蓝正在玩一个攀登高塔的游戏。高塔的层数是无限的，但游戏最多只有 $n$ 回合。

  小蓝一开始拥有 $m$ 点能量，在每个回合都有一个值 $A_i$ 表示小蓝的角色状态。小蓝每回合可以选择消费任意点能量 $C_i$ (最低消费 $1$ 点，没有上限)，他在这回合将最多可以向上攀爬 $A_i\cdot C_i$ 层。实际攀爬的层数取决于小蓝自己在这回合的表现，不过最差也会向上爬一层。

  当某回合小蓝的能量点数耗尽，那么在完成这个回合后，游戏结束。$n$ 回合结束后，不管能量还有没有剩余，游戏都会直接结束。

  给出小蓝每回合的 $A_i$ 和自己一开始的能量点数 $m$。小蓝想知道有多少种不同的可能出现的游玩过程。如果小蓝在两种游玩过程中的任一对应回合花费的能量点数不同或该回合结束时所处层数不同，那么这两种游玩过程就被视为不同。

【输入格式】

  输入的第一行包含两个整数 $n,m$，用一个空格分隔。

  第二行包含 $n$ 个整数 $A_i$，相邻整数之间使用一个空格分隔，表示小蓝每回合的状态值。

【输出格式】

  输出一行包含一个整数表示给定条件下不同游玩过程的数量。由于答案可能很大，你只需要输出答案对 $998244353$ 取模的结果

【样例输入】

9 15
3 2 5 7 1 4 6 8 3

【样例输出】

392149233

【评测用例规模与约定】

  对于 $40\%$ 的评测用例，$n\le 300，m\le 500$；
  对于所有评测用例，$1\le n\le 2\times 10^5，n\le m\le 10^{18}，1\le A_i\le 10^9$。

---

组合数学

---

  为了方便讨论，这里先给出一种小蓝在第 $n$ 回合结束游戏的游玩过程数量的计算方法。依题意的，第 $i$ 回合小蓝共消耗了 $C_i$，共消耗了 $n\le {\sum }_{i=1}^n{C}_i\le m$点能量，第 $i$ 回合有 $A_i\cdot C_i$ 总不同的走法，故方案数为：$$\sum _{\begin{array}{c}{c}_1,c_2,\cdots ,c_n>0\\ c_1+c_2+\cdots +c_n\le m\end{array}}\prod _{i=1}^n{A}_i{C}_i=\sum _{\begin{array}{c}{c}_1,c_2,\cdots ,c_n>0\\ c_1+c_2+\cdots +c_n\le m\end{array}}\prod _{i=1}^n{C}_i\cdot \prod _{i=1}^n{A}_i.$$  记 $p(n,m)$ 为 ${\sum }_{\begin{array}{c}{c}_1,c_2,\cdots ,c_n>0\\ c_1+c_2+\cdots +c_n\le m\end{array}}{\prod }_{i=1}^n{C}_i$。因为在小于 $n$ 的回合结束要耗尽能量，所以整理可以知最终答案为：$$p(n,m)\prod _{i=1}^n{A}_i+\sum _{j=1}^{n-1}(p(j,m)-p(j,m-1))\prod _{i=1}^j{A}_i.$$  因此该思路下，$p(n,m)$ 求解的复杂度与整体直接关联，考虑 $p$ 的边界情况，当 $n=1$ 时，$p(1,m)=1+2+\cdots +m=\frac{m(m+1)}{2}$。考虑 $n+1$ 情况，枚举 $C_{n+1}$ 可能的取值 $1,2,\cdots m-n$，则有递推式：$$p(n,m)=\{\begin{array}{ll}1+2+\cdots +m& n=1\\ {\sum }_{i=1}^{m-n+1}ip(i-1,m-i)& 1<n\le m\end{array}.$$  观察到 $p(1,m)=\frac{m(m+1)}{2}=C_{m+1}^2$，有 $$\begin{array}{rl}p(2,m)& =C_m^2+2C_{m-1}^2+\cdots +(m-1)C_2^2\\ & =(C_m^2+C_{m-1}^2+\cdots +C_2^2)+(C_{m-1}^2+C_{m-2}^2+\cdots +C_2^2)+\cdots C_2^2\\ & =C_{m+1}^3+C_m^3+\cdots +C_3^3\\ & =C_{m+2}^4\end{array}.$$  类似的，可得关系式 $p(n,m)=C_{n+m}^{2n}$，故最终答案为：$$C_{n+m}^{2n}\prod _{i=1}^n{A}_i+\sum _{j=1}^{n-1}(C_{j+m}^{2j}-C_{j+m-1}^{2j})\prod _{i=1}^j{A}_i.$$  不对 $p$ 做优化的情况下时间复杂度为 $O(n^2\log m)$，因此 $p$ 的值还需迭代计算，最终复杂度为 $O(n\log m)$。此外，在杨辉三角中我们也可以看到 $p(n,m)、p(n-1,m-1)、p(n-1,n-1)$ 恰围成一个菱形，什么数形结合。

先睡觉