第十三届蓝桥杯国赛Java大学A组题解

A.火柴数字

题目:

小蓝最近迷上了用火柴棒拼数字字符, 方法如下图所示:

他只能拼 0 至 9 这十种数字字符, 其中每个数字字符需要的火柴棒的数目 依次是: 6,2,5,5,4,5,6,3,7,6。

他不喜欢重复拼同一个数字字符, 所以对于每个 数字字符他最多拼十个。

小蓝会把拼出来的数字字符组合在一起形成一个整数, 例如对于整数 345 , 需要的火柴棒的数目为5+4+5=14根。

小蓝有 300 根 火柴棒, 他想知道自己能拼出的最大整数是多少? 可以不使用完这 300 根火柴 棒, 可以有多余的火柴棒剩下。

题解:

 对于拼出来的数字要最大, 那么首先就要使数字尽可能地长, 就比如数字1只需要2根火柴棒,而数字0却需要6根, 足足能拼出3个数字1, 显然拼需要火柴棒少的数字优先, 如果消耗相同,那么数字大的优先, 按照这个方式对这10个数字进行优先级排序就是:

2*10+3*10+4*10+5*10+5*10+5*10+6*10=300

所以可以拼出数字1、7、4、5、3、2、9恰好各10个, 最大数字就将他们从大到小排列即可

所以最终答案为:

B.小蓝与钥匙

题目:

小蓝是幼儿园的老师, 他的班上有 28 个孩子, 今天他和孩子们一起进行了 一个游戏。

小蓝所在的学校是寄宿制学校, 28 个孩子分别有一个自己的房间, 每个房 间对应一把钥匙, 每把钥匙只能打开自己的门。

现在小蓝让这 28 个孩子分别将 自己宿舍的钥匙上交, 再把这 28 把钥匙随机打乱分给每个孩子一把钥匙, 有 28!=28*27*...*1 种分配方案。

小蓝想知道这些方案中, 有多少种方案恰有 一半的孩子被分到自己房间的钥匙 (即有 14 个孩子分到的是自己房间的钥匙, 有 14 个孩子分到的不是自己房间的钥匙)。 

题解:

 这是一个 组合数 与 错排数 的问题

28个孩子中有14个孩子得到自己的钥匙共有C(28,14)种方案, 14个孩子得到的钥匙都不是自己的钥匙有D(14)种方案, 那么最终答案就是C(28,14)*D(14), 其中C为组合数,D为错排数

part1-组合数计算:

组合数公式: 

组合数的计算公式是

递推公式含义: 左式表示从n个元素中选取m个元素;  右式则是另一种实现方式: 假设n里的某个元素是特殊元素, 那么从n个元素中选取m个元素可以分为两类情况, ①选择的m个元素中不包含特殊元素, 那么就是从n-1个元素中选择m个元素

代码表示:

long C(int n, int m) {//直接使用函数递归
     if (m > n || n < 0) return 0;
     if (n == m) return 1;
     return C(n - 1, m) + C(n - 1, m - 1);
}

long C(int n, int m) {//使用二维数组递推
    int[][] c = new int[n + 1][m + 1];
    for (int i = 1; i <= n; i++) {//C_{n}^{1}=n
        c[i][1] = i;
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 2; j <= m; j++) {
            c[i][j] = c[i - 1][j] + c[i - 1][j - 1];//递推
        }
    }
    return c[n][m];
}

 long C(int n, int m) {//降维,滚动数组
    int[] curr = new int[m + 1];
    curr[0] = 1;
    for (int i = 0; i <= n; i++) {
        for (int j = Math.min(i, m); j > 0; j--) {//j倒序遍历,因为curr[j]需要使用curr[j-1]
            curr[j] = curr[j] + curr[j - 1];
        }
    }
    return curr[m];
}

part2-错排数计算: 

错排数公式:

令n个数的错排数为D(n) 

对于数字a, 假设它去了b的位置, 接下来考虑数字b

所以a去b的位置后, 剩余的位置会有D(n-2)+D(n-1)种方案

而a去b的位置这里的b有n-1个选择, 所以D(n)=(n-1)*(D(n-2)+D(n-1))

代码表示:

long D(int n) {
    long[] d = new long[n + 1];
    d[2] = 1;
    for (int i = 3; i <= n; i++) {
        d[i] = (i - 1) * (d[i - 1] + d[i - 2]);
    }
    return d[n];
}

 最后计算C(28,14)*D(14)得:

1286583532342313400

C.内存空间

题目:

小蓝最近总喜欢计算自己的代码中定义的变量占用了多少内存空间。

为了简化问题, 变量的类型只有以下三种:

1. int: 整型变量, 一个 int 型变量占用 4 Byte 的内存空间。
2. long: 长整型变量, 一个 long 型变量占用 8 Byte 的内存空间。
3. String: 字符串变量, 占用空间和字符串长度有关, 设字符串长度为L, 则字符串占用L Byte 的内存空间, 如果字符串长度为 0 则占用 0 Byte 的内存 空间。

定义变量的语句只有两种形式:

        1. type varl=value 1 , var2=value....；

        定义了若干个 type 类型变量 var1、var2、..., 并且用 value1、value2...初始化, 多个变量之间用'， 分隔, 语句以';' 结尾, type 可能是 int、long 或 String。

        例如 int a=1,b=5,c=6；占用空间为 12 Byte; long  a=1,b=5； 占用空间为 16 Byte; String s1="", s2="hello",s3="world"；占用空 间为 10 Byte。

        2. type[] arr1=new type[size1], arr2=new type[size2]...；

        定义了若干 type 类型的一维数组变量 , 且数组的大小为 size1、size2..., 多个变量之间用'，'进行分隔, 语句以';' 结尾, type 只可 能是 int 或 long。

        例如 int[] a1=new int[10]；占用的内存空间为 40。Byte; long [] a1=new long [10]， a2=new long [10]；占用的内存空间为 160 Byte。

已知小蓝有T条定义变量的语句, 请你帮他统计下一共占用了多少内存空间。

结果的表示方式为:aGBbMBcKBdB, 其中a,b,c,d为统计结果, GB,MB,KB,B为单位。优先用大的单位表示, 1GB=1024MB, 1MB=1024KB, 1KB=1024B, 其中B表示Byte。如果a,b,c,d 中的某几个 数字为 0 , 那么不必输出这几个数字及其单位。

题目保证一行中只有一句定义变量的语句, 且每条语句都满足题干中描述的定义格式, 所有的变量名都是合 法的且均不重复。

题目中的数据很规整, 和上述给出的例子类似, 除了类型后面有一个空格, 以及定义数组时 new 后面的一个空格之外, 不会出现多余的空格。

题解:

 题目分为两部分, ①接收定义变量语句,统计byte数 ②将统计的byte数进行1024进制转换

part1-统计byte数: 

首先要判断数据类型: 对于一行语句 String statement, 可以调用startsWith来判断数据类型, 并做好类型标识,比如用1表示int[], 2表示long[]...

private static int getType(String statement) {
    if (statement.startsWith("int[]")) return 1;
    if (statement.startsWith("long[]")) return 2;
    if (statement.startsWith("int")) return 3;//注意需要先处理数组
    if (statement.startsWith("long")) return 4;
    return 5;//String
}

如果是int 或者 long 型,我们需要统计变量个数,变量个数等于语句中"="的个数

如果是String型,需要统计字符常量长度之和, 可以按照双引号进行分隔,这样分隔出的奇数项就是字符常量,统计奇数项长度即可,例如: String s1="hello",s2="world"; 分隔后为 {"String s1=", "hello", ",s2=", "world",";"}

 如果是int[] 或者 long[]型,需要统计数组长度之和, 可以按照"="和","分隔, 这样奇数项就是new type[len]的形式,再通过"["和"]"的位置将len取出并统计

private static long handle(String statement) {
    if (statement.isEmpty()) return 0;
    int type = getType(statement);//方便判断类型
    if (type == 1 || type == 2) {//数组
        int cnt = 0;//数组长度之和
        String[] res = statement.split("[=,]");//按照"="和","切割,这样奇数项就是"new type[len]"的形式
       for (int j = 1; j < res.length; j += 2) {
            //截取每个数组长度c
            int idx1 = res[j].lastIndexOf("["), idx2 = res[j].lastIndexOf("]");
            int c = Integer.parseInt(res[j].substring(idx1 + 1, idx2));
            cnt += c;
        }
        return type == 1 ? cnt * 4L : cnt * 8L;
    }
    if (type == 5) {
        String[] res = statement.split("\"");
        long len = 0;//统计长度
        for (int j = 1; j < res.length; j += 2) {
            len += res[j].length();
        }
        return len;
    }
    int count = 0;//赋值语句个数
    for (char ch : statement.toCharArray()) {
        if (ch == '=') count++;
    }
    return type == 3 ? count * 4L : count * 8L;
}

part2-byte转换: 

 对num循环除以k取余,再将num赋值为商,这个过程产出的余数序列就是num的k进制, 所以循环余1024即可

/**
 将字节转换为aGBbMBcKBd形式的字符串
 */
private static String change(long totalByte) {
    StringBuilder res = new StringBuilder(); 
    String[] units = new String[]{"B", "KB", "MB", "GB"};
    //1024进制
    for (int i = 0; i < 4 && totalByte > 0; i++) {//单位只有4个,循环4次
        int t = (int) (totalByte % 1024);
        if (t != 0) res.insert(0, t + units[i]);//如果该位为0则不输出数字和单位
        totalByte /= 1024;
    }
    return res.toString();
}

总体代码:

public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int T = sc.nextInt();
    sc.nextLine();
    long totalByte = 0;
    for (int i = 0; i < T; i++) {//处理T条赋值语句,求总byte数
        totalByte += handle(sc.nextLine());
    }
    System.out.println(change(totalByte));
}

private static long handle(String statement) {
    if (statement.isEmpty()) return 0;
    int type = getType(statement);//方便判断类型
    if (type == 1 || type == 2) {//数组
        int cnt = 0;//数组长度之和
        String[] res = statement.split("[=,]");//按照"="和","切割,这样奇数项就是"new type[len]"的形式
        for (int j = 1; j < res.length; j += 2) {
            //截取每个数组长度c
            int idx1 = res[j].lastIndexOf("["), idx2 = res[j].lastIndexOf("]");
            int c = Integer.parseInt(res[j].substring(idx1 + 1, idx2));
            cnt += c;
        }
        return type == 1 ? cnt * 4L : cnt * 8L;
    }
    if (type == 5) {
        String[] res = statement.split("\"");
        long len = 0;//统计长度
        for (int j = 1; j < res.length; j += 2) {
            len += res[j].length();
        }
        return len;
    }
    int count = 0;//赋值语句个数
    for (char ch : statement.toCharArray()) {
        if (ch == '=') count++;
    }
    return type == 3 ? count * 4L : count * 8L;
}

private static int getType(String statement) {
    if (statement.startsWith("int[]")) return 1;
    if (statement.startsWith("long[]")) return 2;
    if (statement.startsWith("int")) return 3;//注意需要先处理数组
    if (statement.startsWith("long")) return 4;
    return 5;//String
}

/**
 将字节转换为aGBbMBcKBd形式的字符串
 */
private static String change(long totalByte) {
    StringBuilder res = new StringBuilder(); 
    String[] units = new String[]{"B", "KB", "MB", "GB"};
    //1024进制
    for (int i = 0; i < 4 && totalByte > 0; i++) {//单位只有4个,循环4次
        int t = (int) (totalByte % 1024);
        if (t != 0) res.insert(0, t + units[i]);//如果该位为0则不输出数字和单位
        totalByte /= 1024;
    }
    return res.toString();
}

D.斐波那契数组

题目: 

如果数组

1. n>=2
3. 对于所有的i(i>=2), 都满足

现在, 给出一个数组 A, 你可以执行任意次修改, 每次修改将数组中的某个位置的元素修改为一个大于 0 的整数。请问最少修改几个元素之后, 数组A会变成一个斐波那契数组。 

题解: 

如果是斐波那契数组,那么A=(a,a,2a,3a,5a,8a....)

所以暴力枚举起始项值为a(0<a<=10^6), 求前两项为a的情况下,后面项需要修改几次才能使A成为斐波那契数组, 取最小值即可

public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    sc.nextLine();
    String[] split = sc.nextLine().split(" ");
    int[] arr = new int[n];
    for (int i = 0; i < n; i++) {
        arr[i] = Integer.parseInt(split[i]);
    }
    System.out.println(minChange(arr));
}

private static int minChange(int[] arr) {
    int ans = arr.length; 
    for (int a = 0; a <= 1000000; a++) { //a0->a  a1->a
        ans = Math.min(ans, check(arr, a));
    }
    return ans;
}

/**
 在前两项为first的情况下要修改多少次后面的数
 */
private static int check(int[] arr, int first) {
    int success = 0;//匹配成功的数
    if (arr[0] == first) success++;//查看前两项是否匹配
    if (arr[1] == first) success++;
    int currVal;//当前项
    int p1 = first, p2 = first;//当前值的前两项
    for (int i = 2; i < arr.length; i++) {
        currVal = p1 + p2;
        if (currVal > 1000000) break;
        if (arr[i] == currVal) success++;//成功匹配
        p1 = p2;
        p2 = currVal;
    }
    return arr.length - success;
}

E.交通信号(8AC 2TL)

题目: 

LQ市的交通系统可以看成由n个结点和 m条有向边组成的有向图。

在每条边上有一个信号灯, 会不断按绿黄红黄绿黄红黄... 的顺序循环 (初始时刚好 变到绿灯)。

当信号灯为绿灯时允许正向通行, 红灯时允许反向通行, 黄灯时不允许通行。每条边上的信号灯的三种颜色的持续时长都互相, 其中黄灯的持续时长等同于走完路径的耗时。

当走到一条边上时, 需要观察边上的信号灯, 如果允许通行则可以通过此边, 在通行过程中不再受信号灯的影响; 否则需要等待, 直到允许通行。 

请问从结点 s 到结点 t 所需的最短时间是多少, 如果 s 无法到达 t 则输出 -1 。

题解: 

使用dijkstra算法求s到t的单源最短路径,dijkstra算法的操作模版:

1. 建图
2. 设置距离表distance和节点访问表isVisited
3. 将初始点距离设为0,其余点设为无穷大,所有点都设为未访问
4. 每次在未访问节点中取最近距离的未访问节点,并用其更新它的邻居节点距离
5. 节点访问后将其设为已访问

因为绿灯正向通行,红灯反向通行,所以在建图时需要记录正反向通行标识flag.

在更新邻居节点距离时, 需要计算等待时间. 时间即距离, 当前时间可以直接在distance中根据节点来拿到, 假设为time, 每个路口绿黄红黄一个循环, 所以 tt=time%(g+r+2d) 为当前循环的所在时间

1.  tt < g 则当前路口为绿灯
2.  g < tt < g + d 则当前路口为黄灯且下一个灯为红灯
3.  g + d < tt < g + d + r 则当前路口为红灯
4.  g + d + r < tt < g + 2d + r 则当前路口为黄灯且下一个灯为绿灯 

根据当前灯的情况和flag, 计算通行到下一个节点的时间newDist, 在下一个节点原时间和新时间中取较短时间进行更新.

/**
 测试通过:8/10  2个超时
 */
public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt(), m = sc.nextInt(), s = sc.nextInt(), t = sc.nextInt();
    //建图
    List<Vertex> graph = new ArrayList<>();//这里使用了自定义的点和边结构进行建表
    for (int i = 0; i <= n; i++) {
        graph.add(new Vertex(i));
    }
    for (int i = 0; i < m; i++) {//m条边
        int u = sc.nextInt(), v = sc.nextInt(),
                g = sc.nextInt(), r = sc.nextInt(), d = sc.nextInt();
        graph.get(u).edgeList.add(new Edge(v, g, r, d, true));
        graph.get(v).edgeList.add(new Edge(u, g, r, d, false));
    }
    //初始化
    Vertex sVertex = graph.get(s), tVertex = graph.get(t);
    sVertex.dist = 0;//起点距离
    //dijkstra
    PriorityQueue<Vertex> q = new PriorityQueue<>(Comparator.comparingLong(o -> o.dist));//存储[节点,时间]
    for (Vertex vertex : graph) q.offer(vertex);
    while (!q.isEmpty()) {//队列不为空
        Vertex now = q.poll();//取最近距离的未访问节点
        if (now == tVertex) break;
        now.isVisit = true;//设为已访问
        update(now, graph, q);//更新邻居距离
    }
    System.out.println(tVertex.dist);
}

private static void update(Vertex now, List<Vertex> graph, PriorityQueue<Vertex> q) {
    long time = now.dist;//当前时间
    for (Edge edge : now.edgeList) {//更新邻居距离
        Vertex to = graph.get(edge.to);
        if (to.isVisit) continue;//已访问跳过
        long tt = time % (edge.g + edge.r + edge.d * 2L);
        long waitCurrLED;
        long newDist = time + edge.d;
        if (tt < edge.g) {//绿灯
            waitCurrLED = edge.g - tt;
            if (!edge.flag) {//等红灯
                newDist += waitCurrLED;
            }
        } else if (tt < edge.g + edge.d) {//黄
            waitCurrLED = edge.g + edge.d - tt;
            if (edge.flag) {//等绿灯
                newDist += waitCurrLED + edge.r + edge.d;
            } else {//等红灯
                newDist += waitCurrLED;
            }
        } else if (tt < edge.g + edge.d + edge.r) {//红
            waitCurrLED = edge.g + edge.d + edge.r - tt;
            if (edge.flag) {//等绿灯
                newDist += waitCurrLED + edge.d;
            }
        } else {//黄
            waitCurrLED = edge.g + 2L * edge.d + edge.r - tt;
            if (edge.flag) {//等绿灯
                newDist += waitCurrLED;
            } else {//等红灯
                newDist += waitCurrLED + edge.g + edge.d;
            }
        }
        to.dist = Math.min(to.dist, newDist);
        q.remove(to);
        q.offer(to);
    }
}

static class Edge {
    int to, g, r, d;
    boolean flag;

    public Edge(int to, int g, int r, int d, boolean flag) {
        this.to = to;
        this.g = g;
        this.r = r;
        this.d = d;
        this.flag = flag;
    }
}

static class Vertex {
    int id;
    boolean isVisit = false;
    long dist = Long.MAX_VALUE;
    List<Edge> edgeList = new ArrayList<>();

    public Vertex(int id) {
        this.id = id;
    }

}

F.数组个数(TODO)

public static void main(String[] args) { 
    //接收数据
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    sc.nextLine();
    int[] B = new int[2 * n];
    String[] arr = sc.nextLine().split(" ");
    for (int i = 0; i < n; i++) {
        B[i] = B[i + n] = Integer.parseInt(arr[i]);
    }
    //找最大值索引
    int maxIdx = 0;
    for (int i = 0; i < n; i++) {
        B[i] = B[i + n] = Integer.parseInt(arr[i]);
        if (B[i] > B[maxIdx]) maxIdx = i;
    }
    if (maxIdx == 0 && B[n - 1] == B[0]) {
        for (int i = n - 2; i >= 0; --i) {
            if (B[i] != B[maxIdx]) {
                maxIdx = i + 1;
                break;
            }
        }
    }
    if (maxIdx == n - 1) {
        maxIdx = 0;
    } else {
        n += ++maxIdx;
    }
    //[maxIdx,maxIdx+n)为一个循环数组B,其中B[maxIdx+n-1]为最大值
    //如果B有多个最大值,则其余最大值均分布在B[maxIdx+k],0<=k<最大值个数
    System.out.println("maxIdx:" + maxIdx + ", n:" + n);
    //动态规划
    int[][] dp = new int[2 * n][3];
    dp[maxIdx][2] = 1;
    for (int i = maxIdx + 1; i < n; ++i) {
        int up = min(B[i - 1], B[i], B[i + 1]);
        for (int k = 0; k <= up; ++k) {
            if (k < B[i - 1] && k < B[i] && k < B[i + 1]) {//k比三项都小
                dp[i][0] = (dp[i][0] + dp[i - 1][1]) % MOD;
                dp[i][1] = (dp[i][1] + dp[i - 1][2]) % MOD;
            } else if (k == B[i + 1]) {
                dp[i][2] = (dp[i][2] + dp[i - 1][2]) % MOD;
                if (k == B[i]) dp[i][2] = (dp[i][2] + dp[i - 1][1]) % MOD;
                if (k == B[i - 1]) dp[i][2] = (dp[i][2] + dp[i - 1][0]) % MOD;
            } else if (k == B[i]) {
                dp[i][1] = ((dp[i][1] + dp[i - 1][1]) % MOD + dp[i - 1][2]) % MOD;
                if (k == B[i - 1]) dp[i][1] = (dp[i][1] + dp[i - 1][0]) % MOD;
            } else if (k == B[i - 1]) {
                dp[i][0] = ((dp[i][0] + dp[i - 1][0]) % MOD + (dp[i - 1][1] + dp[i - 1][2]) % MOD) % MOD;
            }
        }
    } 
    System.out.println(dp[n - 1][0]);
}

private static final int MOD = 1000000007;

G.六六大顺 

题目:

 六六大顺, 本指农历六月初六。多用于祝福中年人士家庭幸福, 工作顺利, 事业有成, 身体健康。源自《左传》“君义, 臣行, 父慈, 子孝, 兄爱, 弟敬, 此数者累谓六顺也。”

6 在我国自古以来是一个吉祥的数字, 定义数列A=(a1,a2,...ai...), 其中a1=6,a2=66,ai=10*ai-1 + 6。

定义一个数列 B=(b1,b2,...bi...), 其中b1=6*6,b2=66*66,bi=ai*ai

现在小蓝想知道数列B的前n项的和是多少, 你能帮帮小蓝吗?

题解: 

解法1(通项公式法 6AC 4TL): 

根据a的递推式可以求出a的通项,进而得到b的通项,分组求和得到Sn公式 

//测试通过:6/10 4个超时
private static BigInteger Sum(int n) {
    BigInteger first = BigInteger.valueOf(400).multiply(BigInteger.TEN.pow(2 * n).subtract(BigInteger.ONE));
    BigInteger second = BigInteger.valueOf(880).multiply(BigInteger.TEN.pow(n).subtract(BigInteger.ONE));
    BigInteger third = BigInteger.valueOf(396).multiply(BigInteger.valueOf(n));
    return first.subtract(second).add(third)
            .divide(BigInteger.valueOf(1));
}

解法2(按位分析 10AC):

 列出bn的前面几项进行分析:

k  2n-1 ... 6 5 4 3 2 1 0    
b1=                   3 6   
b2=               4 3 5 6   
b3=           4 4 3 5 5 6   
b4=       4 4 4 3 5 5 5 6  
...   ... . . . . . . . . 
bn= 4 ... 4 3 5 . . . 5 6   

可发现 bi 为 i-1个4 + 一个3 + i-1个5 + 一个6

对于Sn=b1+b2+...+bn.

考虑Sn的个位: 将b1~bn个位相加 t0=6n , 那么Sn个位为t0%10,因为前面的位不会影响到个位

再考虑Sn的百位: 将b1~bn百位相加 t1=3+5(n-1) , 那么Sn的百位为(remainder+t1)%10,其中remainder=t0/10

再考虑Sn的千位:将b1~bn千位相加 t2=3+5(n-2) , 那么Sn的千位为(remainder+t2)%10,其中remainder = t0/100 + t1/10 = (t0/10 + t1)/10 = (remainder + t1)/10

所以Sn从低到高数的第k位 (k从0开始) 为,其中remainder含有递推关系

对于tk, 在k=0时, bi都为6.  在k>=1时, tk=3*num3 + 4*num4 + 5*num5:

• 3的个数: k<=n时有一个3, k>n时没有3,即 
• 4的个数: 4的出现次数规律是0,0,1,1,2,2,3,3,4,4....,等于(k-1)/2, 并且不超过all(all表示总共有数字的位置数),所以是 
• 5的个数: all减去3的个数和4的个数, 即

private static String Sum(int n) {
    StringBuilder ans = new StringBuilder();
    int num3, num4, num5;
    int current = 6 * n;//当前位和,初始为个位之和n个6
    ans.append(current % 10);
    int remainder = current / 10;
    for (int k = 1; k < 2 * n; k++) {//从低位第二位开始计算该位和
        int all = n - k / 2;//总共有数字的位置
        num3 = k <= n ? 1 : 0;
        num4 = Math.min((k - 1) / 2, all);
        num5 = all - num3 - num4;
        current = 3 * num3 + 4 * num4 + 5 * num5 + remainder;
        answer.append(current % 10);
        remainder = current / 10;
    }
    while (remainder > 0) {
        ans.append(remainder % 10);
        remainder /= 10;
    }
    return ans.reverse().toString();
}

H.选素数

题目:

小蓝有一个数x, 每次操作小蓝会选择一个小于x的素数p, 然后在x成 为p的倍数前不断将x加 1 , (如果x一开始就是p的倍数则x不变)。

小乔看到了小蓝进行了 2 次上述操作后得到的结果n, 他想知道x在一开 始是多少。如果有多种可能, 他想知道x一开始最小可以是多少, 而如果不存在任何解, 说明小乔看错了, 此时请输出-1。

题解:

素数筛:

每次都需要选择素数进行操作,所以需要提前制取素数表减少计算量(这个筛法我会写但原理并不是很懂,不会的可以自己去找素数筛原理讲解)

static int N = 1000000;
static boolean[] isComposite = new boolean[N + 1];//合数
static int[] prime = new int[N + 1];//存储素数
static int pNum = 0;//素数个数

static {
    //欧拉筛法筛素数
    isComposite[0] = isComposite[1] = true;
    for (int i = 2; i <= N; i++) {
        if (!isComposite[i]) {
            prime[pNum++] = i;//i为质数
        }
        //把后面的合数筛掉
        for (int j = 0; prime[j] * i <= N && j <= pNum; j++) {
            isComposite[prime[j] * i] = true;
            if (i % prime[j] == 0) break;//防止重复筛
        }
    }
}

2次操作:

一个数x, 每次操作会选择一个小于x的素数p, 然后在x成为p的倍数前不断将x加 1 , (如果x一开始就是p的倍数则x不变)。 

假设操作x,选择了素数p,最终的数字是n, 那么需要满足 p < x && n%p==0, 如果n=kp, 那么x的取值范围为( (k-1)p, p]

那么可以枚举在第二次操作中选择的素数p1=prime[i], 满足条件n%p==0, 枚举第二次操作前的数x1, 其中 (n/p1-1)p1<x1<=p1且p1<x1, 而x1又是作为第一次操作的最终数, 假设初始值为x0, 选择素数p0=prime[j],最终数字是x1, 其中x1%p0, 那么x0的最小值为(p0/x1 - 1)p0+1, 需要满足p0<x0

/**
 寻找最小的x,其中x可以通过两次操作得到n
 @param n 初始x经过两次操作后的值
 @return 初始值x的最小值, 如果不存在, 则输出-1
 */
private static int MinX(int n) {
    int ans = Integer.MAX_VALUE;
    //第二次操作,x1,选择prime[i],加到n,其中n需要是prime[i]的倍数
    for (int i = 0; i < pNum && prime[i] <= n; i++) {
        if (n % prime[i] != 0) continue;
        int k = n / prime[i];//(k-1倍,k倍]范围内的x1,可以加到n
        for (int x1 = (k - 1) * prime[i] + 1; x1 <= n; x1++) {
            if (x1 <= prime[i]) continue;//选择的素数需要小于操作数
            if (!isComposite[x1]) {
                //如果x1是质数,由于x0通过prime[j]加到x1,x1需要是prime[j],那么x0只能选择prime[j]==x1
                ans = Math.min(ans, x1);
                continue;
            }
            //第一次操作,x0,选择prime[j],加到x1,x1是prime[j]的倍数
            for (int j = 0; j < pNum && prime[j] <= x1; j++) {
                if (x1 % prime[j] != 0) continue;
                int k2 = x1 / prime[j];//(k-1倍,k倍]范围内的x0,可以加到x1
                int x0 = (k2 - 1) * prime[j] + 1;
                if (x0 > prime[j]) ans = Math.min(ans, x0);//选择的素数需要小于操作数
            }
        }
    }
    return ans == Integer.MAX_VALUE ? -1 : ans;
}

最终代码:

static int N = 1000000;
static boolean[] isComposite = new boolean[N + 1];//合数
static int[] prime = new int[N + 1];//存储素数
static int pNum = 0;//素数个数

static {
    //欧拉筛法筛素数
    isComposite[0] = isComposite[1] = true;
    for (int i = 2; i <= N; i++) {
        if (!isComposite[i]) {
            prime[pNum++] = i;//i为质数
        }
        //把后面的合数筛掉
        for (int j = 0; prime[j] * i <= N && j <= pNum; j++) {
            isComposite[prime[j] * i] = true;
            if (i % prime[j] == 0) break;//防止重复筛
        }
    }
}

public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    System.out.println(MinX(n));
}


/**
 寻找最小的x,其中x可以通过两次操作得到n

 @param n 初始x经过两次操作后的值
 @return 初始值x的最小值, 如果不存在, 则输出-1
 */
private static int MinX(int n) {
    int ans = Integer.MAX_VALUE;
    //第二次操作,x1,选择prime[i],加到n,其中n需要是prime[i]的倍数
    for (int i = 0; i < pNum && prime[i] <= n; i++) {
        if (n % prime[i] != 0) continue;
        int k = n / prime[i];//(k-1倍,k倍]范围内的x1,可以加到n
        for (int x1 = (k - 1) * prime[i] + 1; x1 <= n; x1++) {
            if (x1 <= prime[i]) continue;//选择的素数需要小于操作数
            if (!isComposite[x1]) {
                //如果x1是质数,由于x0通过prime[j]加到x1,x1需要是prime[j],那么x0只能选择prime[j]==x1
                ans = Math.min(ans, x1);
                continue;
            }
            //第一次操作,x0,选择prime[j],加到x1,x1是prime[j]的倍数
            for (int j = 0; j < pNum && prime[j] <= x1; j++) {
                if (x1 % prime[j] != 0) continue;
                int k2 = x1 / prime[j];//(k-1倍,k倍]范围内的x0,可以加到x1
                int x0 = (k2 - 1) * prime[j] + 1;
                if (x0 > prime[j]) ans = Math.min(ans, x0);//选择的素数需要小于操作数
            }
        }
    }
    return ans == Integer.MAX_VALUE ? -1 : ans;
}

I.图书借阅(TODO)

资本家:

• 资金回笼: 谁先还书就先借给谁
• 生意长久: 添加借的多且时间线分布最广的书

J.括号序列树(11AC 9TL)

题目:

有一棵二叉树，根结点上有一个空字符串，每个点的左儿子上的字符串为其父亲结点的字符串尾部额外加一个左括号，右儿子则是在尾部加一个右括号。树中的每个叶子结点上的字符串都分别和每个由 n 对括号组成的合法括号序列一一对应。

给定 n，求此时这棵树的最大匹配所含的边数。答案对998244353取余

题解:

最大匹配:

对于一个无向图G,它的最大匹配是边集的一个子集, 这个子集需要满足: 对于G中每一个点来说, 都只有最多一条与之相连的边在这个子集中. 最大匹配就是这个子集大小可以到达的最大值. 

简单来说就是:尽可能选择多的边, 并且在选择这些边后构成的图中, 节点成对相连, 不存在3个及以上节点相连通的情况

 例1:

该图的最大匹配方案有3种: { (1,4),(2,3) } 、 { (1,2),(4,5) } 、{ (2,3),(4,5) } , 其中(u,v)表示选择u-v边

最大匹配的所含边数为2

例2:

这是n=2时的括号序列树, 它的最大匹配所含边数为3, 图中标红的三条边是最大匹配的一种选择方案. 

度为1的节点:

假设有一个度为1的节点u, 与它相连的节点为v, v的邻居有{a1,a2,...}, 考虑v是否在最大匹配中

• v不在最大匹配中, 那么v没有与之相连的节点, u也没有与之相连的节点, 那么边(u,v)还是能够加入匹配
• v在最大匹配中, 有两种情况:
  • case1:v与u匹配
  • case2:v不与u匹配,假设v与a1匹配

        那么对比这两种情况, 它们已匹配边数均为1, 而待匹配节点, case1中v的邻居都可以参与匹配, case2中a1无法再参与匹配, u也无法参与匹配, 待匹配节点case2少于case1, 显然case1更优

所以得出结论: 度为1的节点需要尽可能参与匹配

解法1-差分(11AC 9TL):

令count[i][j]表示向左走i步,向右走j步的节点

 将其改为节点个数

count[i][j]中的节点,可能与count[i-1][j]相连,也可能与count[i][j-1]相连

然后开始匹配, 根节点度为1, 从根节点开始, 优先向左(向下)匹配, 每次匹配后将节点删去

构成的匹配如上图所示, 红字为产出边数, 将他们相加就是答案

上图的匹配过程可以使用差分来表示,用count[i]减去count[i-1]可得:

最后一行也进行差分count[n][j]-count[n][j-1]

现在对count数组求和(除去最后一行最后一列,因为它们是未匹配节点)就是答案

private static final int MOD = 998244353;

/**
 11AC 9TL
 */
 public static void main(String[] args) {
     int n = new Scanner(System.in).nextInt();
    // 构建杨辉三角数组
    long[][] arr = new long[n + 1][n + 1];
    for (int i = 0; i <= n; i++) {
        arr[i][0] = 1;
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= i; j++) {
            arr[i][j] = (arr[i][j - 1] + arr[i - 1][j]) % MOD;
        }
    }
    //对杨辉三角数组进行差分求和
    long sum = 1;
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j <= i; j++) {
            arr[i][j] = (arr[i][j] - arr[i - 1][j] + MOD) % MOD;
            if (i != n) sum = (sum + arr[i][j]) % MOD;
        }
    }
    for (int j = 1; j <= n; j++) {//最后一行单独差分
        sum = (sum + arr[n][j - 1]) % MOD;
        arr[n][j] = (arr[n][j] - arr[n][j - 1] + MOD) % MOD;
    }
    System.out.println(sum);
}

解法2-杨辉三角: 

父节点层的节点数一定小于等于子节点层的节点数, 那么从根节点开始匹配的话, 第2i-1层与第2i层匹配(i>0)的边数就等于第2i-1层节点数.

设第i层的剩余未匹配节点数为remainder[i], 对于第2i层的剩余节点:

它们可以与第2i+1层进行匹配, 如果这样做了, 那么 remainder[2i]将变为0, remainder[2i+2] 将变为 remainder[2i+2] - remainder[2i], 可以发现剩余总量没有改变, 所以第2i层的剩余节点对结果没有影响.

那么答案就是第2i-1层节点数之和, 如果令根节点为第1层, 那么就是这棵树的奇数层节点数之和

杨辉三角:

将解法1提到的count数组写回为树形结构

          1
         /
        1
       / \
      1   1
     / \ /
    1   2
   / \ / \
  1   3   2
 / \ / \ /
1   4   5
....

假设这个结构序列第i行第j列为T[i][j] , 观察发现它可以由两个杨辉三角错位相减得到(如下图)

        1                  0   1                   1  -1
       / \                / \ / \                 / \ / \
      1   1              0   1   1               1   0  -1
     / \ / \      -     / \ / \ / \     =       / \ / \ / \
    1   2   1          0   1   2   1           1   1  -1  -1 
   / \ / \ / \        / \ / \ / \ / \         / \ / \ / \ / \
  1   3   3   1      0   1   3   3   1       1   2   0  -2  -1
 / \ / \ / \ / \    / \ / \ / \ / \ / \     / \ / \ / \ / \ / \
1   4   6   4   1  0   1   4   6   4   1   1   3   2  -2  -3  -1

即T[i][j]=C(i,j)-C(i,j-1) ,其中C(i,j)为杨辉三角的第i行第j列

组合数:

C(i,j)既是杨辉三角函数,也是组合数

• 时间上: 因为肯定需要频繁地求C(i,j), 如果每次都递推求一遍非常耗时, 所以需要进行预处理, 然后O(1)地获取某一项
• 空间上: 考虑到n的范围有10^6, 直接二维数组存储内存太大, 所以只能使用一维数组间接存储.

组合数公式为 , 那么只需要预处理出阶乘数组就可以O(1)地算出C(n,m)

但是, 数字很大需要对998244353取模, 而模性质对除法不适用, 所以需要使用乘法逆元, 用乘法代替除法才能进行模运算.

所以, 总共需要两个数组, factorial[i]为i的阶乘, inverse[i]为i的阶乘在模MOD下的乘法逆元, 可得C(n,m) = factorial[n] * inverse[m] * inverse[n - m], 然后在适当位置取模即可 (运算时需要转为long型防溢出)

/**
 <h1>模组合数</h1>
 C(n,m)%MOD
 组合数C(n,m) = n! / ((n-m)! m!)
 */
private static int C(int n, int m) {
    return (int) ((long) factorial[n] * inverse[m] % MOD * inverse[n - m] % MOD);
}

乘法逆元: 

乘法逆元的情况下乘法与除法逆转, 因为 i-1的阶乘的乘法逆元 需要从 i的阶乘的乘法逆元 里刨去i, 所以inverse[i-1] = inverse[i] * i

由费马小定理可知:a在模MOD下的乘法逆元等于a^(MOD-2), 所以在计算完阶乘后, 取阶乘最后一项计算MOD-2次方(可使用快速幂算法), 然后倒序递推inverse

private static final int N = 2000001; // 2*n <= 2*10^6
private static final int MOD = 998244353;
private static final int[] factorial = new int[N]; // factorial[i]=i!
private static final int[] inverse = new int[N]; // inverse[i]=inv(i!)

/**
 取模性质对除法不适用,所以需要逆元,用乘法代替除法
 预处理出阶乘数组和乘法逆元数组
 */
private static void init(int n) {
    factorial[0] = 1;
    for (int i = 1; i <= 2 * n; i++) {//求阶乘
        factorial[i] = (int) ((long) factorial[i - 1] * i % MOD);
    }
    inverse[2 * n] = fastPow(factorial[2 * n]);
    for (int i = 2 * n; i > 0; i--) {//倒序递推求逆元
        inverse[i - 1] = (int) ((long) inverse[i] * i % MOD);
    }
}

/**
 快速幂,base^(MOD-2)
 */
private static int fastPow(int base) {
    int ans = 1;
    int p = MOD - 2;
    while (p > 0) {
        if ((p & 1) == 1) ans = (int) ((long) ans * base % MOD);
        base = (int) ((long) base * base % MOD);
        p >>= 1;
    }
    return ans;
}

奇数层节点数之和:

现在序列生成问题已经解决, 只需要求出奇数层节点数之和即可

          1
         /
        1
       / \
      1   1
     / \ /
    1   2
   / \ / \
  1   3   2
 / \ / \ /
1   4   5
....

对于这个序列,它的高度为2n+1, 对于第k行:

• k<=n时都是满的, 直接等于序列值的, 可以直接对奇数层求和
• 在k>n时, 因为n+1、n+2...的括号序列不在树上, 所以会少一些分支, 不能直接对奇数层求和, 需要在序列值的基础上减去对应缺少的分支数

对全部奇数层求和:

  // T[i][j]=C(i,j)-C(i,j-1)代入

// 拆项

 // 相消

 所以序列的全部奇数层之和为

缺失的分支数(TODO):

题解我看不懂了,你们自己看吧

如果能提供更优的算法, 欢迎评论或私信