蓝桥杯小白测试题

2024-04-07数据结构与算法4 分钟141 次阅读
AI 摘要salmon-ai

本文介绍了蓝桥杯小白测试题中的前两道典型题解思路:盖印章题通过统计网格中被覆盖的格子数,结合两种印章分别占 3 格和 2 格、总使用次数为 K,列出二元一次方程求出 A、

题目链接:https://www.lanqiao.cn/oj-contest/newbie-9

1、盖印章

问题描述

小Z喜欢盖印章。

有一天,小 Z 得到了一个 n×mn \times m 的网格图,与此同时,他的手上有两种印章(分别称为 A,B),如下图所示。
image.png

他想将这两种印章盖在这个网格图上。

由于小 Z 是一个有原则的人,他将按照以下规则进行操作。

  1. 每个印章所形成的图案的边必须和网格图边重合。
  2. 对于网格图上的每一个格子,最多只能被一个印章图案覆盖。
  3. 对于每个印章,可以将印章顺时针旋转 90°,180°,270°。
  4. 印章的图案在网格图上必须是完整的。

给定小 Z 所盖完印章的网格图以及两种印章的使用次数 KK,请你分别求出两种印章的使用次数。可以证明,在这种情况下二者的使用次数是唯一的。

数据保证存在一种方案达到要求。

具体例子可以參考样例。

输入格式
第一行包含三个正整数 n,m,K(2≤n×m≤106,0≤K≤n×m)n,m,K(2\leq n\times m\leq 10^6,0\leq K\leq n \times m). 具体意义如题面所示。

接下来有 nn 行长度为 mm 的 01 串,其中 1 表示这个位置被印章图案覆盖。否则表示这个位置没有被覆盖。

输出格式
输出两个整数,第一个整数为 A 出现的次数,第二个整数为 B 出现的次数。

样例输入1

sh 复制代码
3 3 3
110
110
110

样例输出1

sh 复制代码
0 3

样例输入2

sh 复制代码
3 3 2
110
110
110

样例输出2

sh 复制代码
2 0

说明

上述样例图如图所示:

image.png

运行限制

image.png

题解

这道题我们无需考虑印章摆放的位置,题目告诉我们保证有解,那说明格子图案一定是可以使用A印章或B印章盖出来的。

我们知道一个A印章占用3个格子,而一个B印章占用2个格子,而知道网格图中的格子数有多少个是盖章过的,我们也知道两个印章盖章了多少次。

故可以设二元一次方程:3a+2b=count(盖章过的格子数),a+b=k(盖章了多少次),那就可以解决该问题啦。

java 复制代码
import java.util.Scanner;

/**
 * 盖印章
 *
 * @author Salmon
 * @since 2024-04-06
 */
public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        int k = sc.nextInt(); // 两种印章的使用次数

        // 盖章的格子数
        int count = 0;

        for (int i = 1; i <= n; i++) {
            String str = sc.next();
            count += str.replaceAll("0", "").length();
        }

        // 一个印章 A 占用 3个格子
        // 一个印章 B 占用 2个格子
        // 设:A印章改了a次,B印章 b次
        // 方程:count = 3a + 2b
        //       k = a + b
        // count = 3a + 2(k-a) = 2k + a
        int a = count - 2 * k;
        int b = k - a;
        System.out.println(a + " " + b);
    }
}

2、字符迁移

问题描述

小蓝最近获得了一个长度为 NN 的字符串 SS,他对它爱不释手。

小桥为了考验小蓝对字符串的处理能力,决定给他提出一个挑战,她会进行 QQ 次操作:

  • 每次操作给定三个整数 l,r,ll,r,l,将 SS 的第 ll 个字符到第 rr 个字符都循环右移 kk 次。

小桥想让小蓝回答她在操作完成后 SS 是多少?小蓝陷入了困境,于是请你帮帮他!

字符右移表示为按字母表进行移动,例如 a 右移 1 次变为 b,b 右移 2 次变为 d。特别地,z 右移 1 次变回为 a。

输入格式

第一行输入两个整数 N,Q(1≤N,Q≤2×105)N,Q(1\leq N,Q\leq2\times10^5) 表示字符串 SS 的长度和小桥操作次数。

第二行输入一个字符串 SS,保证 SS 只包含小写字符。

接下来 QQ 行每行输入三个整数l,r,k(1≤l≤r≤N,1≤k≤109)l,r,k(1\leq l\leq r\leq N,1\leq k\leq10^9) 表示一次操作。

输出格式

输出一个字符串表示答案。

输入样例

sh 复制代码
5 3
abcde
1 5 3
1 2 4
2 5 3

输出样例

sh 复制代码
hlijk

运行限制

image.png

题解

由于题目给的数据量较大,每次都对字符串中同一个字符做多次运算,会很耗时,我们使用差分前缀和来进行求解,那么每个字符只需要计算一次就可以了。

差分前缀和的思想简单的理解就是:区间的起点记录要加的值,终点后一位的位置要减去加的值,来抵消,因为在计算前缀和时,相当于起点后所有元素都会加上这个值,故在我们的结束区间那减去来抵消。

这题还有一点注意k 的范围很大,我们要避免加的值溢出范围,故要做取模。

java 复制代码
import java.util.Scanner;

/**
 * 字符串迁移
 *
 * @author Salmon
 * @since 2024-04-06
 */
public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(); // 字符串长度
        long q = sc.nextInt(); // 小乔操作数

        String str = sc.next();
        char[] arr = str.toCharArray();
        int[] b = new int[n + 2]; // 差分数组

        while (q-- > 0) {
            int l = sc.nextInt(); // 开始下标
            int r = sc.nextInt(); // 结束下标
            int k = sc.nextInt(); // 右移
            // 差分的起始与结束
            b[l] += k % 26;
            b[r + 1] -= k % 26;
        }

        for (int i = 1; i <= n; i++) {
            // 计算前缀和
            b[i] = b[i - 1] + b[i];

            // 从原来的字母右移改为 从字符 a 右移
            // 得出原来这个字母与字符a的差值,'z' - 'a' = 25
            int offset = arr[i - 1] - 'a';

            // 要从 a 右移多少步,注意取模,防止溢出    
            offset = (b[i] + offset) % 26;

            arr[i - 1] = (char) ('a' + offset);
        }
        System.out.println(new String(arr));
    }
}

3、字典树考试

题解

java 复制代码

4、无理数位数查询

问题描述
设 f(m)f(m) 为所有 mm 进制正整数连接起来构造的一个 mm 进制无理数。

f(10)f(10) 如下所示:

0.123456789101112131415161718192021..0.123456789101112131415161718192021..

可以看出小数点后第 12 位数字是 1。

给定若干次询问,每次询问给出两个整数n,mn,m,求 f(m)f(m) 的第 nn 位的数字。

输入格式

第一行包含一个正整数 T(1≤T≤104)T(1\leq T\leq10^4),表示测试用例的数量。

每个测试用例只有一行,包含两个正整数n,m(1≤n≤1018,2≤m≤10)n,m(1\leq n\leq 10^{18},2\leq m\leq 10)。具体意义如题面所示。

输出格式

对于每个测试用例,输出一行一个整数,表示答案。

样例输入

sh 复制代码
4
1000 10
200 3
300 4
10 5

样例输出

sh 复制代码
3
2
1
2

运行限制

image.png

题解

java 复制代码

5、贝贝的集合

题解

java 复制代码
觉得有用就点个赞,不用登录也能读

评论

0 条
登录 之后才能评论
—
还没有评论,来说第一句