跳至主要內容

「蓝桥」1014 第 1 场算法双周赛

大约 13 分钟

「蓝桥」1014 第 1 场算法双周赛

T1. 三带一【算法赛】

问题描述

小蓝和小桥玩斗地主，小蓝只剩四张牌了，他想知道是否是“三带一”牌型。

三带一
三带一

所谓“三带一”牌型，即四张手牌中，有三张牌一样，另外一张不与其他牌相同，换种说法，四张手牌经过重新排列后，可以组成 AAABAAAB 型。

输入格式

第一行输入一个整数 TT ，代表斗地主的轮数。

接下来 TT 行，每行输入一个长度为 44 的字符串，代表小蓝的手牌。

字符 { 'A','2','3','4','5','6','7','8','9','X','J','Q','K' } 对应代表牌面 { A,2,3,4,5,6,7,8,9,10,J,Q,KA, 2, 3, 4, 5, 6, 7, 8, 9,10, J, Q, K } 。

牌面中不包含大小王。

输出格式

输出 TT 行，每行一个字符串，如果当前牌是“三带一”牌型，输出 Yes ，否则输出 No 。

样例输入

5
AAAA
33X3
JQKX
6566
KKKQ

样例输出

No
Yes
No
Yes
Yes

说明

“四炸”牌型不属于“三带一”牌型。

评测数据范围

数据范围：1≤T≤501 \le T \le 50 。

字符中只包含：{ A,2,3,4,5,6,7,8,9,X,J,Q,KA, 2, 3, 4, 5, 6, 7, 8, 9, X, J, Q, K } 。

参考实现

解题思路

模拟。

这里利用排序简化代码。

参考代码

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    static char[] cs;

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int t = scanner.nextInt();
        while (t-- > 0) {
            cs = scanner.next().toCharArray();
            System.out.println(solve());
        }
    }

    private static String solve() {
        Arrays.sort(cs);
        boolean ans1 = cs[0] == cs[1] && cs[1] == cs[2] && cs[2] != cs[3];
        boolean ans2 = cs[0] != cs[1] && cs[1] == cs[2] && cs[2] == cs[3];
        return ans1 || ans2 ? "Yes" : "No";
    }
}

T2. 数树数【算法赛】

问题描述

小蓝最近学了二叉树，他想到了一个问题。

给定一个层数为 nn 的满二叉树，每个点编号规则如下：

图片描述
图片描述

具体来说，二叉树从上向下数第 pp 层，从左往右编号分别为： 1,2,3,4...2p−11,2,3,4...2^{p-1} 。

小蓝给你一条从根节点开始的路径，他想知道到达的节点编号是多少。

例如：路径是 right−leftright-left ，那么到达的节点是 1−2−31-2-3 ，最后到了三号点，如下图所示。

图片描述
图片描述

输入格式

第一行输入两个整数 n,qn,q ，nn 表示完全二叉树的层数，qq 代表询问的路径数量。

接下来 qq 行，每行一个字符串 SS ，SS 只包含字符 { 'L','R' }，'L' 代表向左，R 代表向右。

输出格式

输出 qq 行，每行输出一个整数，代表最后到达的节点编号。

样例输入

3 6
R
L
LL
LR
RL
RR

样例输出

2
1
1
2
3
4

说明

2≤n≤20,1≤q≤103,1≤∣S∣<n2 \le n \le 20, 1 \le q \le 10^3, 1 \le |S| \lt n。

完全二叉树：一个二叉树，如果每一个层的结点数都达到最大值，则这个二叉树就是满二叉树。也就是说，如果一个二叉树的层数为 KK ，且节点总数是 2k−12^k-1 ，则它就是满二叉树。

参考实现

解题思路

利用满二叉树性质。

参考代码

import java.util.Scanner;

public class Main {
    static int n;
    static char[] s;

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int q = scanner.nextInt();
        while (q-- > 0) {
            s = scanner.next().toCharArray();
            System.out.println(solve());
        }
    }

    private static String solve() {
        int id = 1;
        for (char c : s) {
            if (c == 'R') id = id * 2 + 1;
            else id *= 2;
        }
        int ans = id - (1 << s.length) + 1;
        return String.valueOf(ans);
    }
}

T3. 分组【算法赛】

问题描述

蓝桥小学要进行弹弹球游戏，二年级一班总共有 nn 个同学，要求分成 kk 个队伍，由于弹弹球游戏要求队员的身高差不能太大，小蓝是班长，他对这个事情正在发愁，他想问你，如何最小化每个组之间的身高极差。

具体的，假设分成了 kk 个组，第 ii 组最高的人身高是 HxiHx_i ，最矮的是 HniHn_i，你被要求最小化表达式： max⁡1≤i≤k(Hxi−Hni)\underset{1 \leq i \leq k}{\max} (Hx_i-Hn_i) 。直白来说，你需要将 nn 个元素分出 kk 组，使得最大的极差尽可能小。你需要输出这个最小化后的值。

输入格式

第一行输入两个整数 n,kn, k 。

第二行输入 nn 个整数：h1,h2,h3...hnh_1, h_2,h_3...h_n ，分别代表 nn 个人的身高。

输出格式

输出一个整数，代表最小值。

样例输入

5 3
8 4 3 6 9

样例输出

1

说明

样例分组情况：{ 3,43,4 } ，{ 66 } ，{ 8,98,9 } 。

评测数据规模

数据范围： 1≤k≤n≤105,1≤hi≤1091 \le k \le n \le 10^5, 1 \le h_i \le 10^9 。

参考实现

解题思路

二分答案。

参考代码

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    static int n, k;
    static int[] h;

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        n = scanner.nextInt();
        k = scanner.nextInt();
        h = new int[n];
        for (int i = 0; i < n; i++) {
            h[i] = scanner.nextInt();
        }
        System.out.println(solve());
    }

    private static String solve() {
        Arrays.sort(h);
        int l = 0, r = h[n - 1];
        while (l < r) {
            int m = l + (r - l) / 2;
            if (checkMid(m)) r = m;
            else l = m + 1;
        }
        return String.valueOf(l);
    }

    static boolean checkMid(int mid) {
        int cnt = 1;
        int pre = h[0];
        for (int i = 0; i < n; i++) {
            if (h[i] - pre > mid) {
                cnt++;
                pre = h[i];
            }
        }
        return cnt <= k;
    }
}

T4. 健身【算法赛】

问题描述

小蓝要去健身，他可以在接下来的 1∼n1 \sim n 天中选择一些日子去健身。

他有 mm 个健身计划，对于第 ii 个健身计划，需要连续的 2ki2^{k_i} 天，如果成功完成，可以获得健身增益 sis_i ，如果中断，得不到任何增益。

同一个健身计划可以多次完成，也能多次获得健身增益，但是同一天不能同时进行两个或两个以上的健身计划。

但是他的日程表中有 qq 天有其他安排，不能去健身，问如何安排健身计划，可以使得 nn 天的健身增益和最大。

输入格式

第一行输入三个整数 n,m,qn,m,q 。

第二行输入 qq 个整数，t1,t2,t3...tqt_1,t_2,t_3...t_q ，代表有其他安排的日期。

接下来 mm 行，每行输入两个整数 ki,sik_i, s_i 。代表该训练计划需要 2ki2^{k_i} 天，完成后可以获得 sis_i 的健身增益。

输出格式

一个整数，代表最大的健身增益和。

样例输入

10 3 3
1 4 9
0 3
1 7
2 20

样例输出

30

说明

在样例中 2∼32 \sim 3 天进行计划 22 ，5∼85 \sim 8 天进行计划 33 ， 10∼1010 \sim 10 天进行计划 11 。

评测数据范围

数据范围： 1≤q≤n≤2×1051 \le q \le n \le 2 \times 10 ^5 ， 1≤m≤501 \le m \le 50 ， 1≤si≤1091 \le s_i \le 10^9 ， 0≤ki≤200 \le k_i \le 20 ， 1≤t1<t2<...<tq≤n1\le t_1 \lt t_2 \lt... \lt t_q \le n 。

参考实现

解题思路

DP + 前缀和。

首先可以确定，由于对于 kk 值相同的时候，可能存在多> 个增益，所以对于每一个不同的 kk 值，只保留最大的增> 益值即可。

代码中使用 sw[k] 来表示需要锻炼 2k2^k 天的计划可> 以得到的最大增益。

使用 dp[i] 表示训练到 ii 天可以得到的最大增益> 值。

转移方程如下：

如果当前这一天不训练，或者不能训练，那么 dp[i]=>max(dp[i],dp[i−1])dp[i] = > max(dp[i], dp[i-1]) 。

然后考虑当前这一天是某个计划结束的一天，那么 dp>[i]=max(dp[i],dp[i−2k]+sw[k])dp> [i] = max(dp[i], dp[i - 2^k] + sw[k]) ，那么需> 要满足第 i−2k+1i-2^k + 1 天到第 ii 都是空闲的。

如何快速计算，在某个区间段是否空闲呢，使用前缀和算> 法，使用 sum[i]sum[i] 来表示前 ii 天有多少个不空闲的时> 间，那么我们使用 sum[r]−sum[l−1]sum[r]-sum[l-1] 是否等于 00 就> 可以判断区间是否空闲。

最后 dp[n]dp[n] 即是答案。

时间复杂度： O(n×max(ki))O(n \times max(k_i)) 。

参考代码

import java.util.Scanner;

public class Main {
    static int n, m, q;
    static int[] t;
    static int[][] ks;

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        n = scanner.nextInt();
        m = scanner.nextInt();
        q = scanner.nextInt();
        t = new int[q];
        for (int i = 0; i < q; i++) {
            t[i] = scanner.nextInt();
        }
        ks = new int[m][2];
        for (int i = 0; i < m; i++) {
            ks[i][0] = scanner.nextInt();
            ks[i][1] = scanner.nextInt();
        }
        System.out.println(solve());
    }

    private static String solve() {
        int[] a = new int[n];
        for (int i : t) {
            a[i-1]++;
        }
        int[] ps = new int[n + 1];
        for (int i = 0; i < n; i++) {
            ps[i + 1] = ps[i] + a[i];
        }

        // sw[k] 表示需要锻炼 2^k 天的计划可以得到的最大增益
        long[] sw = new long[21];
        for (int[] p : ks) {
            int k = p[0], s = p[1];
            sw[k] = Math.max(sw[k], s);
        }

        long[] f = new long[n + 1];
        for (int i = 1; i <= n; i++) {
            f[i] = f[i - 1];
            for (int k = 0; k <= 20; k++) {
                int j = i - (1 << k);
                if (j >= 0 && ps[i] - ps[j] == 0) {
                    f[i] = Math.max(f[i], f[j] + sw[k]);
                } else {
                    break;
                }
            }
        }
        return String.valueOf(f[n]);
    }
}

T5. 契合匹配【算法赛】

问题描述

小蓝有很多齿轮，每个齿轮的凸起和凹陷分别用一个字符表示，一个字符串表示一个齿轮。

图片描述
图片描述

如果两个齿轮的对应位分别是同一个字母的大小写，我们称这两个齿轮是契合的。

例如：AbCDeFgh 和 aBcdEfGH 就是契合的，但是 abc 和 aBC 不是契合的。

这天，小蓝的弟弟小桥从抽屉里拿来了两个齿轮，小蓝想知道，这俩个齿轮是不是契合的。

特别需要注意的是，齿轮是环形的，所以是可以旋转的（顺时针和逆时针均可），如果是契合的，小蓝还想让你告诉他，最少将第一个齿轮旋转多少位，两个齿轮可以完全契合在一起。

例如： AbbCd 与 BcDaB，在将第一个齿轮逆时针旋转两位后，变成 bCdAb ，两个齿轮就完全契合在一起了。

输入格式

第一行输入一个正整数 nn ，代表两个齿轮的长度。

第二行输入一个长度为 nn 的字符串 SS ，代表第一个齿轮。

第三行输入一个长度为 nn 的字符串 TT ，代表第二个齿轮。

输出格式

第一行输出一个字符串： Yes 或者 No 。代表两个齿轮是否契合。

如果可以契合，第二行输出一个整数，代表需要旋转的位数。

如果不可以契合，不用多余输出。

样例输入

5
AbbCd
BcDaB

样例输出

Yes
2

评测数据范围

数据范围： 1≤n≤1061 \le n \le 10^6 。

保证字符串只包含大小写字母。

参考实现

解题思路

KMP 算法 + 贪心。注意不能用 String#indexOf()（不能只找第一个）。

参考代码

import java.util.Scanner;

public class Main {
    static int n;
    static String s;
    static char[] t;

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        n = scanner.nextInt();
        s = scanner.next();
        t = scanner.next().toCharArray();
        System.out.println(solve());
    }

    private static String solve() {
        for (int i = 0; i < n; i++) {
            if (Character.isUpperCase(t[i])) t[i] = Character.toLowerCase(t[i]);
            else t[i] = Character.toUpperCase(t[i]);
        }

        char[] txt = (s + s).toCharArray();
        char[] pat = t;
        int[] pi = prefix_function(pat);

        int ans = n;
        for (int i = 0, j = 0; i < txt.length; i++) {
            while (j > 0 && txt[i] != pat[j]) j = pi[j - 1];
            if (txt[i] == pat[j]) j++;
            if (j == n) {
                ans = Math.min(ans, Math.min(i - n + 1, n * 2 - i - 1));
                j = pi[j - 1];
            }
        }
        return ans == n ? "No" : "Yes" + System.lineSeparator() + ans;
    }

    private static int[] prefix_function(char[] s) {
        int n = s.length;
        int[] pi = new int[n];
        for (int i = 1; i < n; i++) {
            int j = pi[i - 1];
            while (j > 0 && s[i] != s[j]) j = pi[j - 1];
            if (s[i] == s[j]) j++;
            pi[i] = j;
        }
        return pi;
    }
}

T6. 奇怪的线段【算法赛】

问题描述

在一维数轴上，小蓝画了 nn 个闭区间线段，小桥会多次询问你，每次给定两个点 a,ba,b ，问有多少个区间包含 aa 点，但是不包含 bb 点。

输入格式

第一行输入两个整数 n,qn, q ， nn 代表区间个数， qq 代表询问个数。

接下来 nn 行，每行两个整数 li,ril_i, r_i ，代表一个左右端点为 li,ril_i, r_i 的闭区间。

接下来 qq 行，每行两个整数 ai,bia_i, b_i ，代表询问存在多少个区间，包含 aia_i 点，但不包含 bib_i 点。

输出格式

输出 qq ，第 ii 行代表第 ii 个询问的答案。

样例输入

4 3
1 3
2 5
3 7
4 8
1 5
2 9
5 1

样例输出

1
2
3

评测数据范围

1≤n≤2×1051 \le n \le 2 \times 10^5 ， 1≤q≤2×1051 \le q \le 2 \times 10^5 ， 1≤li<ri≤2×1051 \le l_i \lt r_i \le 2 \times 10^5 ， 1≤ai,bi≤2×1051 \le a_i,b_i \le 2 \times 10^5 。

参考实现

解题思路

离线 + 树状数组。

注意要使用快读，不然会 TLE。

在思考本道题前，我们先思考弱化版本。

如果只有一个点，即我们仅仅考虑覆盖 aa 点的区间有多少个。

考虑离线算法，我们对于每一个区间的左端点维护一个 vector 容器，装下对应的右端> 点，同时维护一个全局的线段树，从左向右扫描，扫描到一个区间的左端点时，将对应> 的右端点加入到线段树中，当扫描到一个右端点时，将右端点从线段树中移除，到扫描> 到一个 aa 时，查询线段树中节点数量，即为答案。

那么此题相似，只不过查询的不是全局区间和，而是局部区间和。

具体如下：

总共分为三种情况：

  1. 如果 a==ba == b ，答案为 00。

  2. 如果 a<ba \lt b ，对区间按照左区间排序，从左向右扫描，并且维护一个区间和> 线段树，扫描到一个区间的左端点时，将对应的右端点加入到线段树中，当扫描到一个> 右端点时，将右端点从线段树中移除，到扫描到一个 aa 时，查询线段树中 [a,b)>[a, b)> 的区间和，即为答案。

  3. 如果 a>ba \gt b ，对区间按照右区间排序，从右向左扫描，并且维护一个区间和> 线段树，扫描到一个区间的右端点时，将对应的左端点加入到线段树中，当扫描到一个> 左端点时，将左端点从线段树中移除，到扫描到一个 aa 时，查询线段树中 (b,a]>(b,a]> 的区间和，即为答案。

实际上，我们需要维护的是动态区间和，代码中用树状数组来代替维护区间和。

参考代码

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Scanner;
import java.util.StringTokenizer;
import java.util.stream.Collectors;

public class Main {
    static int n, q;

    public static void main(String[] args) {
        FastReader scanner = new FastReader();
        n = scanner.nextInt();
        q = scanner.nextInt();

        posL = new ArrayList[N];
        Arrays.setAll(posL, e -> new ArrayList<>());
        posR = new ArrayList[N];
        Arrays.setAll(posR, e -> new ArrayList<>());
        for (int i = 0; i < n; i++) {
            int l = scanner.nextInt();
            int r = scanner.nextInt();
            posL[l].add(r);
            posR[r].add(l);
        }
        query = new ArrayList[N];
        Arrays.setAll(query, e -> new ArrayList<>());
        for (int i = 0; i < q; i++) {
            int a = scanner.nextInt();
            int b = scanner.nextInt();
            query[a].add(new int[]{b, i});
        }
        System.out.println(solve());
    }

    private static final int N = (int) (2e5 + 5);
    static List<Integer>[] posL, posR;
    static List<int[]>[] query;

    private static String solve() {
        int[] ans = new int[q];

        Fenwick l2r = new Fenwick(N);
        for (int i = 1; i < N; i++) {
            for (Integer r : posL[i]) {
                l2r.add(r, 1);
            }
            for (int[] p : query[i]) {
                int b = p[0], id = p[1];
                if (b > i) {
                    ans[id] = l2r.getSum(b - 1);
                }
            }
            l2r.add(i, -posR[i].size());
        }

        Fenwick r2l = new Fenwick(N);
        for (int i = N - 1; i > 0; i--) {
            for (Integer l : posR[i]) {
                r2l.add(l, 1);
            }
            for (int[] p : query[i]) {
                int b = p[0], id = p[1];
                if (b < i) {
                    ans[id] = r2l.getSum(N) - r2l.getSum(b);
                }
            }
            r2l.add(i, -posL[i].size());
        }

        return Arrays.stream(ans).mapToObj(String::valueOf).collect(Collectors.joining(System.lineSeparator()));
    }

    static class Fenwick {
        private final int n;
        private final int[] tree;

        public Fenwick(int n) {
            this.n = n;
            this.tree = new int[n + 1];
        }

        int lowbit(int x) {
            return x & -x;
        }

        // nums[x] add k
        void add(int x, int k) {
            while (x <= n) {
                tree[x] += k;
                x += lowbit(x);
            }
        }

        // nums [1,x] 的和
        int getSum(int x) {
            int ans = 0;
            while (x > 0) {
                ans += tree[x];
                x -= lowbit(x);
            }
            return ans;
        }
    }

    static class FastReader {
        private final BufferedReader bufferedReader;
        private StringTokenizer stringTokenizer;

        public FastReader() {
            bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        }

        public String next() {
            while (stringTokenizer == null || !stringTokenizer.hasMoreElements()) {
                try {
                    stringTokenizer = new StringTokenizer(bufferedReader.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return stringTokenizer.nextToken();
        }

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

        public long nextLong() {
            return Long.parseLong(next());
        }

        public double nextDouble() {
            return Double.parseDouble(next());
        }

        public String nextLine() {
            String str = "";
            try {
                if (stringTokenizer.hasMoreTokens()) {
                    str = stringTokenizer.nextToken("\n");
                } else {
                    str = bufferedReader.readLine();
                }
            } catch (IOException e) {
                e.printStackTrace();
            }
            return str;
        }
    }
}

（全文完）

Copyright © 2018-2023 gdut-yy