每日省赛真题解析·第三天
每日省赛真题解析·第三天

每日省赛真题解析·第三天

目录

  • 2021省赛试题H
  • 2021省赛试题I
  • 2021省赛试题J

2021省赛试题H

题目链接:杨辉三角形 – 蓝桥云课 (lanqiao.cn)

题目要求:

下面的图形是著名的杨辉三角形。如果我们按从上到下、从左到右的顺序把所有数排成一列,可以得到如下数列: 1, 1, 1, 1, 2, 1, 1, 3, 3, 1, 1, 4, 6, 4, 1……给定一个正整数 NN,请你输出数列中第一次出现 NN 是在第几个数?

解题思路:

·20分(暴力枚举):

由于 n 很小,我们可以按从上到下、从左到右的顺序不断枚举,直到 n 第一次出现后停止枚举并输出枚举的次数即可。

·100分(二分法):

代码:

import java.util.*;

public class Main {
    private static int n;

    private static long C(long a, long b) {
        long res = 1;
        for (long i = a, j = 1; j <= b; i--, j++) {
            res = res * i / j;
            if (res > n) {
                return res;
            }
        }
        return res;
    }

    public static void main(String[] args) {
        Scanner cin = new Scanner(System.in);
        n = cin.nextInt();
        for (int k = 16; k >= 0; k--) {
            int l = 2 * k, r = Math.max(n, l), res = -1;
            while (l <= r) {
                int mid = l + r >> 1;
                if (C(mid, k) >= n) {
                    res = mid;
                    r = mid - 1;
                } else {
                    l = mid + 1;
                }
            }
            if (C(res, k) == n) {
                System.out.println((long) (res + 1) * res / 2 + k + 1);
                break;
            }
        }
        cin.close();
    }
}

二.2021省赛试题I

题目链接:双向排序 – 蓝桥云课 (lanqiao.cn)

题目要求:

给定序列 (a1​,a2​,⋅⋅⋅,an​)=(1,2,⋅⋅⋅,n),即 ai​=i。小蓝将对这个序列进行 m 次操作,每次可能是将a1​,a2​,⋯,aqi​​ 降序排列,或者将aqi​​,aqi+1​​,⋯,an​ 升序排列。请求出操作完成后的序列。

解题思路:

·30分:

调用 sort() 函数。对于每个操作,直接对相应区间使用 sort() 函数即可。时间复杂度 O(nmlog)。

·50分:使用权值数组的做法。

举个例子:

  • 对于 降序排列 操作,设它需要排序的区间为 [1,pos]。那么我们可以先将 [1,pos]​ 内的每个数字打上标记,然后从n∼1​ 开始遍历每个数字。如果 i 数字是第 1​ 个被打上标记的数字,那么我们就令它插入到第一个位置(即 a[1]=i),如果是第 2​ 个被打上标记的数字,我们就让它插入到第二个位置(即 a[2]=i​)……依次插入每个数,直到插完 [1,pos] 的所有位置。
  • 对于 升序操作 操作同理。

时间复杂度 O(nm)。

·100分:

50%得分代码:

import java.util.Scanner;

//该方法能通过60%的测试数据
public class Main {
	public static int N = 100010;
	public static int n, m, op, pos;
	public static int[] flag = new int[N];
	public static int[] A = new int[N];

	public static void main(String[] args) {
		for (int i = 0; i < N; i++)
			flag[i] = 1;
		for (int i = 0; i < N; i++)
			A[i] = i;
		Scanner scanner = new Scanner(System.in);
		n = scanner.nextInt();
		m = scanner.nextInt();
		while ((m--) != 0) {
			op = scanner.nextInt();
			pos = scanner.nextInt();
			if (op == 0) {
				for (int i = 1; i <= n; i++)
					flag[i] = 1; // 重置标记
				for (int i = 1; i <= pos; i++)
					flag[A[i]] = 0;
				int k = 1;
				for (int i = n; i >= 1; i--) {
					if (flag[i] == 0)
						A[k++] = i;
				}
			}
			if (op == 1) {
				for (int i = 1; i <= n; i++)
					flag[i] = 0; // 重置标记
				for (int i = pos; i <= n; i++)
					flag[A[i]] = 1;
				int k = pos;
				for (int i = 1; i <= n; i++) {
					if (flag[i] == 1)
						A[k++] = i;
				}
			}
		}
		for (int i = 1; i <= n; i++)
			System.err.print(A[i] + " ");
		System.out.println();
	}
}

AC代码:

import java.io.IOException;
import java.util.*;
import java.io.*;

class InputReader {
    private final static int BUF_SZ = 65536;
    BufferedReader in;
    StringTokenizer tokenizer;

    public InputReader(InputStream in) {
        super();
        this.in = new BufferedReader(new InputStreamReader(in), BUF_SZ);
        tokenizer = new StringTokenizer("");
    }

    private String next() {
        while (!tokenizer.hasMoreTokens()) {
            try {
                tokenizer = new StringTokenizer(in.readLine());
            } catch (IOException e) {
                throw new RuntimeException(e);
            }
        }
        return tokenizer.nextToken();
    }

    public int nextInt() {
        return Integer.parseInt(next());
    }
}

class Tree {
    public int l = 0;
    public int r = 0;
    public int sum = 0;
    public int lazy = -1;
}

public class Main {
    public static final int N = 100010;
    public static int n;
    public static int m;
    public static int op;
    public static int pos;
    public static Tree[] tree = new Tree[N << 2];

    public static void push_up(int rt) {
        tree[rt].sum = tree[rt << 1].sum + tree[rt << 1 | 1].sum;
    }

    public static void push_down(int rt) {
        int x = tree[rt].lazy;
        if (x != -1) {
            int len1 = tree[rt << 1].r - tree[rt << 1].l + 1;
            int len2 = tree[rt << 1 | 1].r - tree[rt << 1 | 1].l + 1;
            tree[rt << 1].sum = len1 * x;
            tree[rt << 1 | 1].sum = len2 * x;
            tree[rt << 1].lazy = tree[rt << 1 | 1].lazy = x;
            tree[rt].lazy = -1;
        }
    }

    public static void build(int l, int r, int rt) {
        tree[rt].l = l;
        tree[rt].r = r;
        tree[rt].lazy = -1;
        if (l == r) {
            tree[rt].sum = 1;
            return;
        }
        int mid = l + r >> 1;
        build(l, mid, rt << 1);
        build(mid + 1, r, rt << 1 | 1);
        push_up(rt);
    }

    public static void update1(int L, int R, int rt, int cnt) {
        if (cnt == 0) {
            return;
        }
        if (tree[rt].sum == cnt) {
            tree[rt].sum = tree[rt].lazy = 0;
            return;
        }
        push_down(rt);
        if (cnt < tree[rt << 1].sum) {
            update1(L, R, rt << 1, cnt);
        } else {
            update1(L, R, rt << 1 | 1, cnt - tree[rt << 1].sum);
            tree[rt << 1].sum = 0;
            tree[rt << 1].lazy = 0;
        }
        push_up(rt);
    }

    public static void update2(int L, int R, int rt, int cnt) {
        if (cnt == 0) {
            return;
        }
        int l = tree[rt].l;
        int r = tree[rt].r;
        int len = r - l + 1;
        if (len - tree[rt].sum == cnt) {
            tree[rt].sum = len;
            tree[rt].lazy = 1;
            return;
        }
        push_down(rt);
        int cnt1 = tree[rt << 1].r - tree[rt << 1].l + 1 - tree[rt << 1].sum;
        if (cnt < cnt1) {
            update2(L, R, rt << 1, cnt);
        } else {
            update2(L, R, rt << 1 | 1, cnt - cnt1);
            tree[rt << 1].sum = tree[rt << 1].r - tree[rt << 1].l + 1;
            tree[rt << 1].lazy = 1;
        }
        push_up(rt);
    }

    public static int query(int L, int R, int rt) {
        int l = tree[rt].l;
        int r = tree[rt].r;
        if (L <= l && r <= R) {
            return tree[rt].sum;
        }
        push_down(rt);

        int mid = l + r >> 1;
        int res = 0;
        if (L <= mid) {
            res += query(L, R, rt << 1);
        }
        if (R > mid) {
            res += query(L, R, rt << 1 | 1);
        }
        return res;
    }

    public static void main(String[] args) {
        for (int i = 0; i < (N << 2); i++) tree[i] = new Tree();
        InputReader cin = new InputReader(System.in);
        n = cin.nextInt();
        m = cin.nextInt();
        build(1, n, 1);
        while ((m--) != 0) {
            op = cin.nextInt();
            pos = cin.nextInt();
            if (op == 0) {
                int cnt0 = n - tree[1].sum;
                int cnt = Math.max(0, pos - cnt0);
                update1(1, n, 1, cnt);
            } else {
                int cnt1 = tree[1].sum;
                int cnt = Math.max(0, n - pos + 1 - cnt1);
                update2(1, n, 1, cnt);
            }
        }
        int vv1 = 0;
        int vv2 = 0;
        for (int i = n; i >= 1; i--) {
            if (query(i, i, 1) == 0) {
                System.out.print(i + " ");
            }
        }
        for (int i = 1; i <= n; i++) {
            if (query(i, i, 1) == 1) {
                System.out.print(i + " ");
            }
        }
        System.out.println();
    }
}

三.2021省赛试题J

题目链接:括号序列 – 蓝桥云课 (lanqiao.cn)

题目要求:

给定一个括号序列,要求尽可能少地添加若干括号使得括号序列变得合法,当添加完成后,会产生不同的添加结果,请问有多少种本质不同的添加结果。两个结果是本质不同的是指存在某个位置一个结果是左括号,而另一个是右括号。

例如,对于括号序列 ( ( ( ),只需要添加两个括号就能让其合法,有以下几种不同的添加结果:( )( )( )、( )( ( ) )、( ( ) )( )、( ( )( ) )和 ( ( ( ) ) )​。

解题思路:

for(int i = 1 ; i <= cnt ; i ++) dp[1][i] = 1;
    if(sum[1] > 0) dp[1][0] = 1;
    for(int i = 2 ; i <= n ; i ++){
        for(int j = i - sum[i] ; j <= cnt ; j ++){
            for(int k = 0 ; k <= j ; k ++){
                dp[i][j] += dp[i - 1][k];
                dp[i][j] %= mod;
            }
        }
    }

代码:

import java.util.*;

public class Main {
    private static final int N = 5010;
    private static final long mod = 1000000000 + 7;
    private static char[] s;
    private static final long[][] dp = new long[N][N];
    private static final int[] sum = new int[N];
    private static final long[] nex = new long[N];
    private static final long[] pre = new long[N];

    private static long calc(int cnt, boolean flag) {
        if (cnt == 0) {
            return 1;
        }
        for (long[] longs : dp) Arrays.fill(longs, 0);
        Arrays.fill(sum, 0);
        Arrays.fill(pre, 0);
        if (!flag) {
            for (int i = 0; i < s.length / 2; i++) {
                char x = s[i];
                s[i] = s[s.length - i - 1];
                s[s.length - i - 1] = x;
            }
            for (int i = 0; i < s.length; i++) {
                if (s[i] == ')') {
                    s[i] = '(';
                } else {
                    s[i] = ')';
                }
            }
        }

        int n = 0, now = 0;
        for (char c : s) {
            if (c == ')') sum[++n] = now;
            if (c == '(') now++;
        }
        if (sum[1] > 0) {
            dp[1][0] = 1;
            pre[0] = 1;
        }
        for (int i = 1; i <= cnt; i++) {
            dp[1][i] = 1;
            pre[i] = pre[i - 1] + 1;
        }
        for (int i = 2; i <= n; i++) {
            for (int j = 0; j <= cnt; j++) nex[j] = 0;
            for (int j = Math.max(0 , i - sum[i]); j <= cnt; j++) {
                dp[i][j] = pre[j];
                if(j - 1 < 0) nex[j] = dp[i][j];
                else nex[j] = (nex[j - 1] + dp[i][j]) % mod;
            }
            if (cnt + 1 >= 0) System.arraycopy(nex, 0, pre, 0, cnt + 1);
        }
        return dp[n][cnt];
    }

    public static void main(String[] args) {
        String S;
        Scanner cin = new Scanner(System.in);
        S = cin.next();
        s = S.toCharArray();
        int tot = 0, cnt1 = 0, cnt2 = 0;
        for (var i : s) {
            if (i == '(') {
                tot++;
            } else {
                tot--;
            }
            if (tot < 0) {
                cnt1++;
                tot = 0;
            }
        }
        cnt2 = tot;
        System.out.println(calc(cnt1, true) * calc(cnt2, false) % mod);
        cin.close();
    }
}