第十三届蓝桥杯大赛软件赛省赛第二场（Java 大学A组）

蓝桥杯 2022年省赛真题
^{Java 大学A组第二场}

试题 A: 练习
试题 B: 超级质数
试题 C: 考勤刷卡
试题 D: 最大和
试题 E: 染色时间
试题 F: k 倍区间
试题 G: 选素数
试题 H: 五子棋
试题 I: 第几小
试题 J: 单峰序列

太久没写题了，调下状态。

试题 A: 练习

本题总分： 5 5 5 分

【问题描述】

小蓝在蓝桥杯练习系统上做题。做到一道题，他编写好程序，在自己的电脑上尝试了题目中提供的几个样例，全部得到了正确的结果，可是当他将自己的程序提交到练习系统上时，却得了 0 0 0 分，这种情况可能的原因是什么？请在以下选项中选择所有可能导致这种情况的原因。

A . mathrm A. A. 题目中的样例一般比较小，在评测的时候可能使用的评测用例比较大，小蓝的程序虽然在小样例能得到解，对于大一些的评测用例可能速度太慢，超过了题目要求的时间限制。

B . mathrm B. B. 小蓝的内存使用过多，虽然在自己的电脑上运行正确，可是在评测的内存限制下无法运行。

C . mathrm C. C. 小蓝的程序有考虑不足之处，题目中的样例比较小，小蓝的程序恰好能得到对应的结果，可是当评测用例比较复杂时，小蓝的程序无法得到正确的结果。

【答案提交】

这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个由大写字母组成的字符串，按字母顺序给出所选择的选项，在提交答案时只填写这个字符串，填写多余的内容将无法得分。例如，如果选项全部正确，请填写答案 A B C mathrm{ABC} ABC。

ABC

试题 B: 超级质数

本题总分： 5 5 5 分

【问题描述】

如果一个质数 P P P 的每位数字都是质数，而且每两个相邻的数字组成的两位数是质数，而且每三位相邻的数字组成的三位数是质数，依次类推，如果每相邻的 k k k 位数字组成的 k k k 位数都是质数，则 P P P 称为超级质数。

如果把超级质数 P P P 看成一个字符串，则这个超级质数的每个子串都是质数。

例如， 53 53 53 是一个超级质数。

请问，最大的超级质数是多少？

【答案提交】

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

373

递推

若 n n n 是质数，而 ⌊ n 10 ⌋ 、 n − 1 0 ⌊ log ⁡ 10 n ⌋ ⌊ n 1 0 ⌊ log ⁡ 10 n ⌋ ⌋ lfloorfrac n{10}rfloor、n - 10^{lfloorlog_{10}nrfloor}lfloorfrac n{10^{lfloorlog_{10}nrfloor}}rfloor ⌊10n⌋、n−10⌊log10n⌋⌊10⌊log10n⌋n⌋ 同为超级质数，则 n n n 同为超级质数。

递推就完事了。

import java.util.*;

public class Test {

    public static void main(String[] args) { new Test().run(); }

    int[] P = { 2, 3, 5, 7 };

    long ans = 0;

    void run() {
        Queue queue = new ArrayDeque();
        HashMap map = new HashMap();
        for (long p : P) {
            queue.offer(p);
            map.put(p, p);
        }
        while (!queue.isEmpty()) {
            long now = queue.poll();
            long head = map.get(now);
            long buff = (now - head) * 10;
            ans = Math.max(ans, now);
            for (long p : P) {
                long temp = now * 10 + p;
                if (millerRabin(temp) &&
                    map.containsKey(buff + p)) {
                    map.put(temp, head * 10);
                    queue.offer(temp);
                }
            }
        }
        System.out.println(ans);
    }

    int time = 50;
    
    boolean millerRabin(long n) {
        if (n % 2 == 0) return n == 2;
        long b = n - 1;
        int k = 0;
        for (; b % 2 == 0; ++k, b /= 2);
        for (int i = 0, j; i < time; ++i) {
            long a = (int)(Math.random() * (n - 1) + 1);
            long v = qpow(a, b, n);
            if (v == 1) continue;
            for (j = 0; j < k; ++j) {
                if (v == n - 1) break;
                v = multi(v, v, n);
            }
            if (j == k) return false;
        }
        return true;
    }

    long multi(long a, long b, long p) {
        long prod = 0;
        while (b > 0) {
            if (b % 2 == 1) prod = (prod + a) % p;
            a = (a + a) % p;
            b >>= 1;
        }
        return prod;
    }

    long qpow(long a, long b, long p) {
        long pow = 1;
        while (b > 0) {
            if (b % 2 == 1) pow = multi(pow, a, p);
            a = multi(a, a, p);
            b >>= 1;
        }
        return pow;
    }
}

试题 C: 考勤刷卡

时间限制: 3.0 s 3.0mathrm s 3.0s 内存限制: 512.0 M B 512.0mathrm{MB} 512.0MB 本题总分： 10 10 10 分

【问题描述】

小蓝负责一个公司的考勤系统，他每天都需要根据员工刷卡的情况来确定每个员工是否到岗。

当员工刷卡时，会在后台留下一条记录，包括刷卡的时间和员工编号，只要在一天中员工刷过一次卡，就认为他到岗了。

现在小蓝导出了一天中所有员工的刷卡记录，请将所有到岗员工的员工编号列出。

【输入格式】

输入的第一行包含一个正整数 n n n，表示一天中所有员工的刷卡记录的条数。

接下来 n n n 行，每行包含一条刷卡记录，每条刷卡记录的格式为：

H H : M M : S S I D mathrm{HH:MM:SS ID} HH:MM:SS ID

其中 H H : M M : S S mathrm{HH:MM:SS} HH:MM:SS 表示刷卡时间， H H mathrm{HH} HH 为一个 0 0 0 到 23 23 23 之间的两位十进制整数（可能含前导 0 0 0）表示时， M M mathrm{MM} MM 为一个 0 0 0 到 59 59 59 之间的两位十进制整数（可能含前导 0 0 0）表示分， S S mathrm{SS} SS 为一个 0 0 0 到 59 59 59 之间的两位十进制整数（可能含前导 0 0 0）表示秒， I D mathrm{ID} ID 为一个不含前导 0 0 0 的整数表示员工的编号。

所有记录按照刷卡时间升序排列，可能同一时刻有多人刷卡。

【输出格式】

输出若干行，每行包含一个整数，按照从小到大的顺序输出，表示到岗员工的编号。

【样例输入】

4
13:05:42 103
14:07:12 4567
15:03:00 103
17:00:21 1

【样例输出】

1
103
4567

【评测用例规模与约定】

对于 50 % 50% 50% 的评测用例， 1 ≤ n ≤ 100 1 ≤ n ≤ 100 1≤n≤100。
对于所有评测用例， 1 ≤ n ≤ 10000 1 ≤ n ≤ 10000 1≤n≤10000，员工编号为不超过 1 0 9 10^9 109 的正整数。

感觉有诈，但读了几遍也没瞅着陷阱，

鉴定为纯纯的签到。

import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.TreeSet;
import java.util.Set;

public class Main {

    public static void main(String[] args) { new Main().run(); }

    void run() {
        try (BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
             PrintWriter out = new PrintWriter(System.out)) {
            int n = Integer.parseInt(in.readLine());
            Set set = new TreeSet();
            while (n-- > 0) {
                String line = in.readLine();
                set.add(Integer.parseInt(
                    line.substring(line.indexOf(0x20) + 1)
                ));
            }
            for (Integer id : set) out.println(id);
        } catch (IOException e) {
            e.printStackTrace();
        }
    }
}

试题 D: 最大和

时间限制: 3.0 s 3.0mathrm s 3.0s 内存限制: 512.0 M B 512.0mathrm{MB} 512.0MB 本题总分： 10 10 10 分

【问题描述】

小蓝在玩一个寻宝游戏，游戏在一条笔直的道路上进行，道路被分成了 n n n 个方格，依次编号 1 1 1 至 n n n，每个方格上都有一个宝物，宝物的分值是一个整数（包括正数、负数和零），当进入一个方格时即获得方格中宝物的分值。小蓝可以获得的总分值是他从方格中获得的分值之和。

小蓝开始时站在方格 1 1 1 上并获得了方格 1 1 1 上宝物的分值，他要经过若干步到达方格 n。

当小蓝站在方格 p p p 上时，他可以选择跳到 p + 1 p + 1 p+1 到 p + D ( n − p ) p + D(n − p) p+D(n−p) 这些方格中的一个，其中 D ( 1 ) = 1 ， D ( x ) （ x > 1 ） D(1) = 1，D(x) （x > 1） D(1)=1，D(x)（x>1）定义为 x x x 的最小质因数。

给定每个方格中宝物的分值，请问小蓝能获得的最大总分值是多少。

【输入格式】

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

第二行包含 n n n 个整数，依次表示每个方格中宝物的分值。

【输出格式】

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

【样例输入】

5
1 -2 -1 3 5

【样例输出】

【样例说明】
最优的跳跃方案为：：： 1 → 3 → 4 → 5 1 → 3 → 4 → 5 1→3→4→5。

【评测用例规模与约定】

对于 40 % 40% 40% 的评测用例， 1 ≤ n ≤ 100 1 ≤ n ≤ 100 1≤n≤100。
对于 80 % 80% 80% 的评测用例， 1 ≤ n ≤ 1000 1 ≤ n ≤ 1000 1≤n≤1000。
对于所有评测用例， 1 ≤ n ≤ 10000 1 ≤ n ≤ 10000 1≤n≤10000，每个宝物的分值为绝对值不超过 1 0 5 10^5 105 的整数。

做个最简单的估计，排除掉 2 ∼ n 2 sim n 2∼n 中最小质因数为 2 2 2 即奇偶性为偶的数，给上界为 O ( n 2 ) O(n^2) O(n2) 的复杂度配上一个系数 1 4 frac 14 41 就能在 3 s 3mathrm s 3s 内通过所有用例了。

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.StreamTokenizer;
import java.io.IOException;

public class Main {

    public static void main(String[] args) { new Main().run(); }
    
    void run() {
    	int n = nextInt(), a;
    	int[] prime = new int[n + 1];
    	int[] dp = new int[n + 1];
    	for (int i = 2; i <= n; ++i)
    		if (prime[i] == 0)
    			for (int j = i; j <= n; j += i)
    				if (prime[j] == 0) prime[j] = i;
    	prime[1] = 1;
    	for (int i = 1; i <= n; ++i) {
    		a = nextInt();
    		dp[i] += a;
    		for (int j = min(i + prime[n - i], n); j > i; --j)
    			if (dp[i] > dp[j]) dp[j] = dp[i];
    	}
    	System.out.println(dp[n]);
    }
    
    int min(int arg1, int arg2) { return arg1 < arg2 ? arg1 : arg2; }
    
    StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
    
    int nextInt() {
    	try {
			in.nextToken();
		} catch (IOException e) {
			e.printStackTrace();
		}
		return (int)in.nval;
    }
}

试题 E: 染色时间

时间限制: 3.0 s 3.0mathrm s 3.0s 内存限制: 512.0 M B 512.0mathrm{MB} 512.0MB 本题总分： 15 15 15 分

【问题描述】

小蓝有一个 n n n 行 m m m 列的白色棋盘，棋盘的每一个方格都可以被染成彩色。

每个方格有一个染色时间 t i j t_{i j} tij，不同方格的染色时间可能不同。如果一个方格被触发了染色，这个方格就会在 t i j t_{i j} tij 秒之后变成彩色，然后将自己上下左右四个方向相邻的方格触发染色。每个方格只能被触发染色一次，第一次触发之后的触发为无效触发。

给定每个方格的染色时间，在时刻 0 0 0 触发第一行第一列的方格染色，请问多长时间后整个棋盘完成染色。

【输入格式】

输入的第一行包含两个整数 n , m n, m n,m，分别表示棋盘的行数和列数。

接下来 n n n 行，每行 m m m 个正整数，相邻的整数之间用一个空格分隔，表示每个方格的染色时间。该部分的第 i i i 行第 j j j 个整数表示 t i j t_{i j} tij，即第 i i i 行第 j j j 列的方格的染色时间。

【输出格式】

输出一行包含一个整数，表示整个棋盘完成染色的时间。

【样例输入】

2 3
1 2 3
4 5 6

【样例输出】

【评测用例规模与约定】

对于 30 % 30% 30% 的评测用例， 1 ≤ n , m ≤ 10 1 ≤ n, m ≤ 10 1≤n,m≤10。
对于 60 % 60% 60% 的评测用例， 1 ≤ n , m ≤ 50 1 ≤ n, m ≤ 50 1≤n,m≤50。
对于所有评测用例， 1 ≤ n , m ≤ 500 1 ≤ n, m ≤ 500 1≤n,m≤500， 1 ≤ t i j ≤ 1000 1 ≤ t_{i j} ≤ 1000 1≤tij≤1000。

大模拟。

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.StreamTokenizer;
import java.io.IOException;
import java.util.PriorityQueue;
import java.util.Queue;

public class Main {

    public static void main(String[] args) { new Main().run(); }

    int[][] offset = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};

    void run() {
        Queue queue = new PriorityQueue();
        int n = nextInt(), m = nextInt(), ans = 0;
        int[][] clock = new int[n][m];
        for (int i = 0; i < n; ++i)
            for (int j = 0; j < m; ++j)
                clock[i][j] = nextInt();
        queue.offer(new Block(clock[0][0], 0, 0));
        clock[0][0] = 0;
        while (!queue.isEmpty()) {
            Block now = queue.poll();
            if (now.time > ans) ans = now.time;
            for (int i = 0, x, y; i < 4; ++i) {
                x = now.x + offset[i][0];
                y = now.y + offset[i][1];
                if (x >= 0 && x < n && y >= 0 && y < m &&
                    clock[x][y] > 0) {
                    queue.offer(new Block(clock[x][y] + now.time, x, y));
                    clock[x][y] = 0;
                }
            }
        }
        System.out.println(ans);
    }

    class Block implements Comparable {

        int time, x, y;

        Block(int time, int x, int y) {
            this.time = time;
            this.x = x;
            this.y = y;
        }

        public int compareTo(Block b) {
            return this.time - b.time;
        }
    }

    StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));

    int nextInt() {
        try {
            in.nextToken();
        } catch (IOException e) {
            e.printStackTrace();
        }
        return (int)in.nval;
    }
}

试题 F: k 倍区间

时间限制: 3.0 s 3.0mathrm s 3.0s 内存限制: 512.0 M B 512.0mathrm{MB} 512.0MB 本题总分： 15 15 15 分

【问题描述】

一个整数序列 A = ( a 1 , a 2 , ⋯ , a n ) A = (a_1, a_2, cdots, a_n) A=(a1,a2,⋯,an) 的区间和为 S i , j = a i + a i + 1 + ⋯ + a j S_{i, j} = a_i + a_{i+1} + cdots + a_j Si,j=ai+ai+1+⋯+aj。

给定整数序列 A A A 和一个正整数 k k k，请问有多少个区间 [ i , j ] [i, j] [i,j] 满足 1 ≤ i ≤ j ≤ n 1 ≤ i ≤ j ≤ n 1≤i≤j≤n 且 S i , j S_{i, j} Si,j 是 k k k 非负整数倍。

【输入格式】

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

第二行包含 n n n 个整数 a 1 , a 2 , ⋯ , a n a_1, a_2, cdots , a_n a1,a2,⋯,an，相邻的整数之间用一个空格分隔。

【输出格式】

输出一行包含一个数表示满足条件的区间数量。

【样例输入】

7 3
1 -1 0 2 2 2 -30

【样例输出】

【样例说明】
满足条件的区间有 [ 1 , 2 ] , [ 1 , 3 ] , [ 1 , 6 ] , [ 2 , 5 ] , [ 3 , 3 ] , [ 3 , 6 ] , [ 4 , 6 ] [1, 2], [1, 3], [1, 6], [2, 5], [3, 3], [3, 6], [4, 6] [1,2],[1,3],[1,6],[2,5],[3,3],[3,6],[4,6]。

【评测用例规模与约定】

对于 40 % 40% 40% 的评测用例， 1 ≤ n ≤ 500 ， 1 ≤ k ≤ 10 1 ≤ n ≤ 500，1 ≤ k ≤ 10 1≤n≤500，1≤k≤10；
对于 60 % 60% 60% 的评测用例， 1 ≤ n ≤ 2000 1 ≤ n ≤ 2000 1≤n≤2000；
对于所有评测用例， 1 ≤ n ≤ 100000 ， 1 ≤ k ≤ 1 0 9 ， − 1 0 9 ≤ a i ≤ 1 0 9 1 ≤ n ≤ 100000，1 ≤ k ≤ 10^9，−10^9 ≤ a_i ≤ 10^9 1≤n≤100000，1≤k≤109，−109≤ai≤109。

同余类

设 S i = ∑ j = 1 i a j S_i = sum_{j=1}^i a_j Si=∑j=1iaj，若一对 i , j i,j i,j 使得 S j − S i S_j - S_i Sj−Si 非负， k ∣ ( S j − S i ) k | (S_j - S_i) k∣(Sj−Si)，则 [ i , j ] [i,j] [i,j] 是一个 k k k 倍区间，且 S i ≡ S j ( m o d k ) S_i equiv S_j pmod k Si≡Sj(modk)。

于是我们将序列 S 1 , S 2 , ⋯ , S n S_1,S_2,cdots,S_n S1,S2,⋯,Sn 抽离成若干个稳定的 k 的同余系，这样同余系内任意的两个不同元素，都能确定一个区间，其和为 k k k 的一个倍数，然后顺序遍历每个同余系，用合数的方式确定当前元素的排名计入答案就行了，此举意在使确定的区间和非负。

J a v a mathrm{Java} Java 的 T r e e S e t mathrm{TreeSet} TreeSet 没有实现 r a n k ( ) mathrm{rank()} rank() 方法，所以这里通过离散化树状数组组织出了类似的功能。

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.StreamTokenizer;
import java.io.IOException;
import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

public class Main {

    public static void main(String[] args) { new Main().run(); }

    void run() {
        int n = nextInt(), m, k = nextInt(), ans = 0;
        Map trees = new HashMap();
        Prefix[] tuple = new Prefix[n + 1];
        Prefix[] sorted = new Prefix[n + 1];
        tuple[0] = sorted[0] = new Prefix(0);
        for (int i = 1; i <= n; ++i)
            tuple[i] = sorted[i] =
                new Prefix(tuple[i - 1].sum + nextInt());
        Arrays.sort(sorted, (a, b) -> Long.compare(a.sum, b.sum));
        sorted[0].rank = 1;
        for (int i = 1; i <= n; ++i)
            if (sorted[i].sum > sorted[i - 1].sum)
                sorted[i].rank = sorted[i - 1].rank + 1;
            else sorted[i].rank = sorted[i - 1].rank;
        m = sorted[n].rank;
        for (int i = 0; i <= n; ++i) {
            int[] tree = trees.get((int)(tuple[i].sum % k));
            if (tree == null)
                trees.put((int)(tuple[i].sum % k), tree = new int[m + 1]);
            for (int j = tuple[i].rank; j > 0; j &= j - 1) ans += tree[j];
            for (int j = tuple[i].rank; j <= m; j += j & -j) ++tree[j];
        }
        System.out.println(ans);
    }

    class Prefix {

        int rank;

        long sum;

        Prefix(long sum) { this.sum = sum; }
    }

    StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));

    int nextInt() {
        try {
            in.nextToken();
        } catch (IOException e) {
            e.printStackTrace();
        }
        return (int)in.nval;
    }
}

试题 G: 选素数

时间限制: 3.0 s 3.0mathrm s 3.0s 内存限制: 512.0 M B 512.0mathrm{MB} 512.0MB 本题总分： 20 20 20 分

【问题描述】

给定两个正整数 s 、 t s、t s、t，每回合可以选择任意一个小于 s s s 的不是 s s s 的因子的素数 p p p，然后取最小的 y y y 使得 y > s y > s y>s 且 y mod ⁡ p = 0 y operatorname{mod} p = 0 ymodp=0，并将这个 y y y 赋值给 s s s。

问最多多少回合后， s ≥ t s ≥ t s≥t。

【输入格式】

输入的第一行包含一个整数 T T T 表示询问次数。

接下来 T T T 行，每行包含两个整数 s i , t i s_i, t_i si,ti，用一个空格分隔，表示一次询问。

【输出格式】

输入 T T T 行，每行包含一个整数，依次表示每次询问的答案。

【样例输入】

【样例输出】

1
1
2

【评测用例规模与约定】

对于 20 % 20% 20% 的评测用例， T = 1 , t i ≤ 1 0 4 T = 1, t_i ≤ 10^4 T=1,ti≤104；
对于 60 % 60% 60% 的评测用例， 1 ≤ T ≤ 500 , t i ≤ 500000 1 ≤ T ≤ 500, t_i ≤ 500000 1≤T≤500,ti≤500000；
对于所有评测用例， 1 ≤ T ≤ 200000 , 3 ≤ s i ≤ t i ≤ 1 0 7 1 ≤ T ≤ 200000, 3 ≤ s_i ≤ t_i ≤ 10^7 1≤T≤200000,3≤si≤ti≤107。

分类讨论

当 2 ∤ s 2 nmid s 2∤s 时，最多 t − s t - s t−s 回合后， s ≥ t s ≥ t s≥t，

不会。

试题 H: 五子棋

时间限制: 5.0 s 5.0mathrm s 5.0s 内存限制: 1.0 G B 1.0mathrm{GB} 1.0GB 本题总分： 20 20 20 分

【问题描述】

小蓝和小乔正在一张 n × n n times n n×n 的棋盘上下五子棋，小蓝持黑先落子，之后双方轮流落子，当有一方获胜时，游戏立刻终止。

现在给出棋盘的状态，问给出的状态是否合法。如果合法，找出是否有人获胜。如果有人获胜，找出输出胜负的决定手在哪里。如果有多个可能的决定手位置 ( x , y ) (x, y) (x,y)，优先输出 x x x 最小的， x x x 也相同时输出 y y y 最小的。

在本题中，只考虑最简单的规则：双方每次可以选一个未放棋子的位置放自己的棋子，当某一步落子后出现横向、或纵向、或两个 4 5 ο ⁡ 45^{operatorname{omicron}} 45ο 方向之一有 5 5 5 个或 5 5 5 个以上连续的自己的棋子时获胜。

【输入格式】

输入的第一行包含一个整数 T T T 表示数据组数。接下来依次表示每组数据。

对于第 i i i 组数据，第一行包含一个整数 n i n_i ni，表示棋盘的大小。

接下来 n i n_i ni 行每行包含一个长度为 n i n_i ni 的字符串，由 0 0 0 或 1 1 1 或 . . . 组成，不包含空格或其它字符。其中 0 0 0 （ A S C I I mathrm{ASCII} ASCII 码为 48 48 48）表示黑棋子， 1 1 1 （ A S C I I mathrm{ASCII} ASCII 码为 49 49 49）表示白棋子， . . . （ A S C I I mathrm{ASCII} ASCII 码为 46 46 46）表示空位。

【输出格式】

对于每组数据，如果给定的状态不合法，那么仅输出一行包含一个英文字符串 N O mathrm{NO} NO。

如果给定的状态合法，则输出两行，第一行包含一个英文字符串 Y E S mathrm{YES} YES。如果无人获胜，第二行包含一个英文字符串 D R A W mathrm{DRAW} DRAW；否则第二行包含两个整数 x , y x, y x,y，用一个空格分隔，表示胜负的决定手的坐标为第 x x x 行 y y y 列。

【样例输入】

3
3
...
...
...
5
00000
.....
.....
.....
11111
5
11101
...0.
...0.
...0.
...0.

【样例输出】

YES
DRAW
NO
YES
1 4

【评测用例规模与约定】

对于 25 % 25% 25% 的评测用例， Σ n i ≤ 10 Sigma n_i ≤ 10 Σni≤10；
对于 50 % 50% 50% 的评测用例， Σ n i ≤ 100 Sigma n_i ≤ 100 Σni≤100；
对于 75 % 75% 75% 的评测用例， Σ n i ≤ 500 Sigma n_i ≤ 500 Σni≤500；
对于所有评测用例， 1 ≤ n i ≤ 5000 ， Σ n i ≤ 5000 1 ≤ n_i ≤ 5000，Sigma n_i ≤ 5000 1≤ni≤5000，Σni≤5000。

鉴定为大模拟，

输入格式限制了输入的合法性，那么剩下的不合法状况只剩下双方同胜、连续同色棋子数大于五以及白落子比黑多（黑子说话）。

然后按照先 x x x 后 y y y 的升序枚举是否有以该格为起始的连续的五个同色棋子就完了。

// 歇会

试题 I: 第几小

时间限制: 5.0 s 5.0mathrm s 5.0s 内存限制: 512.0 M B 512.0mathrm{MB} 512.0MB 本题总分： 25 25 25 分

【问题描述】

给定一个数组 A = ( a 1 , a 2 , ⋯ , a n ) A = (a_1, a_2, cdots , a_n) A=(a1,a2,⋯,an)，请对该数组执行 m m m 次修改或查询操作：

若操作为 1 1 1 x x x y y y，表示将 a x a_x ax 的值修改为 y y y；

若操作为 2 2 2 l l l r r r p p p 表示求 a p a_p ap 在 a l , a l + 1 , ⋯ , a r a_l, a_{l+1}, cdots , a_r al,al+1,⋯,ar 中是第几小的（比 a p a_p ap 小的元素个数加 1 1 1）。

【输入格式】

输入的第一行包含一个整数 n n n。

第二行包含 n n n 个整数 a 1 , a 2 , ⋯ , a n a_1, a_2, cdots , a_n a1,a2,⋯,an，表示数组中每个数的初始值，相邻的整数之间用一个空格分隔。

第三行包含一个整数 m m m。

接下来 m m m 行每行包含一个操作，可能是 1 1 1 x i x_i xi y i y_i yi 或 2 2 2 l i l_i li r i r_i ri p i p_i pi，相邻的整数之间用一个空格分隔。

【输出格式】

输出一行，包含多个整数，相邻的整数之间用一个空格分隔，依次表示第二种操作的答案。

【样例输入】

【样例输出】

2 3

【评测用例规模与约定】

对于 20 % 20% 20% 的评测用例， n ≤ 500 n ≤ 500 n≤500；
对于 40 % 40% 40% 的评测用例， n ≤ 5000 n ≤ 5000 n≤5000；
对于所有评测用例， 1 ≤ n ≤ 100000 ， 1 ≤ m ≤ 2 n ， 1 ≤ a i , y i ≤ 1 0 6 ， 1 ≤ x i ≤ n ， 1 ≤ l i ≤ p i ≤ r i ≤ n 1 ≤ n ≤ 100000，1 ≤ m ≤ 2n，1 ≤ a_i, y_i ≤ 10^6，1 ≤ x_i ≤ n，1 ≤ l_i ≤ p_i ≤ r_i ≤ n 1≤n≤100000，1≤m≤2n，1≤ai,yi≤106，1≤xi≤n，1≤li≤pi≤ri≤n。

// 先挂着

试题 J: 单峰序列

时间限制: 3.0 s 3.0mathrm s 3.0s 内存限制: 512.0 M B 512.0mathrm{MB} 512.0MB 本题总分： 25 25 25 分

【问题描述】

给定 n , m n, m n,m，求有多少个不同的序列 A A A 满足如下条件 : : :

1. 1. 1. A A A 中有至少 1 1 1 个数、至多 n n n 个数，且都是互不相同的正整数；

2. 2. 2. A A A 中所有元素的和恰好为 m m m；

3. 3. 3. 存在一个下标 k k k 使得对于 1 < i ≤ k 1 < i ≤ k 1 A i A_{i−1} > A_i Ai−1>Ai。

【输入格式】

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

【输出格式】

输出一行包含一个整数表示答案，答案可能很大，请输出答案除以 1000000007 1000000007 1000000007 的余数。

【样例输入 1】

2 3

【样例输出 1】

【样例说明 1】
A A A 可能为 ( 3 ) 、 ( 1 , 2 ) (3)、(1, 2) (3)、(1,2) 或 ( 2 , 1 ) (2, 1) (2,1)。

【样例输入 2】

10001 20223

【样例输出 2】

259920306

【评测用例规模与约定】

对于 25 % 25% 25% 的评测用例， n , m ≤ 10 n, m ≤ 10 n,m≤10；
对于 50 % 50% 50% 的评测用例， n , m ≤ 300 n, m ≤ 300 n,m≤300；
对于 75 % 75% 75% 的评测用例， n , m ≤ 5000 n, m ≤ 5000 n,m≤5000；
对于所有评测用例， 1 ≤ n , m ≤ 100000 1 ≤ n, m ≤ 100000 1≤n,m≤100000。

// 先挂

第十三届蓝桥杯大赛软件赛省赛第二场（Java 大学A组）

Java相关栏目本月热门文章