蓝桥杯小白测试题
本文介绍了蓝桥杯小白测试题中的前两道典型题解思路:盖印章题通过统计网格中被覆盖的格子数,结合两种印章分别占 3 格和 2 格、总使用次数为 K,列出二元一次方程求出 A、
题目链接:https://www.lanqiao.cn/oj-contest/newbie-9
1、盖印章
问题描述
小Z喜欢盖印章。
有一天,小 Z 得到了一个 的网格图,与此同时,他的手上有两种印章(分别称为 A,B),如下图所示。

他想将这两种印章盖在这个网格图上。
由于小 Z 是一个有原则的人,他将按照以下规则进行操作。
- 每个印章所形成的图案的边必须和网格图边重合。
- 对于网格图上的每一个格子,最多只能被一个印章图案覆盖。
- 对于每个印章,可以将印章顺时针旋转 90°,180°,270°。
- 印章的图案在网格图上必须是完整的。
给定小 Z 所盖完印章的网格图以及两种印章的使用次数 ,请你分别求出两种印章的使用次数。可以证明,在这种情况下二者的使用次数是唯一的。
数据保证存在一种方案达到要求。
具体例子可以參考样例。
输入格式
第一行包含三个正整数 . 具体意义如题面所示。
接下来有 行长度为 的 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
说明
上述样例图如图所示:

运行限制

题解
这道题我们无需考虑印章摆放的位置,题目告诉我们保证有解,那说明格子图案一定是可以使用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、字符迁移
问题描述
小蓝最近获得了一个长度为 的字符串 ,他对它爱不释手。
小桥为了考验小蓝对字符串的处理能力,决定给他提出一个挑战,她会进行 次操作:
- 每次操作给定三个整数 ,将 的第 个字符到第 个字符都循环右移 次。
小桥想让小蓝回答她在操作完成后 是多少?小蓝陷入了困境,于是请你帮帮他!
字符右移表示为按字母表进行移动,例如 a 右移 1 次变为 b,b 右移 2 次变为 d。特别地,z 右移 1 次变回为 a。
输入格式
第一行输入两个整数 表示字符串 的长度和小桥操作次数。
第二行输入一个字符串 ,保证 只包含小写字符。
接下来 行每行输入三个整数 表示一次操作。
输出格式
输出一个字符串表示答案。
输入样例
sh
5 3
abcde
1 5 3
1 2 4
2 5 3
输出样例
sh
hlijk
运行限制

题解
由于题目给的数据量较大,每次都对字符串中同一个字符做多次运算,会很耗时,我们使用差分前缀和来进行求解,那么每个字符只需要计算一次就可以了。
差分前缀和的思想简单的理解就是:区间的起点记录要加的值,终点后一位的位置要减去加的值,来抵消,因为在计算前缀和时,相当于起点后所有元素都会加上这个值,故在我们的结束区间那减去来抵消。
这题还有一点注意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、无理数位数查询
问题描述
设 为所有 进制正整数连接起来构造的一个 进制无理数。
如下所示:
可以看出小数点后第 12 位数字是 1。
给定若干次询问,每次询问给出两个整数,求 的第 位的数字。
输入格式
第一行包含一个正整数 ,表示测试用例的数量。
每个测试用例只有一行,包含两个正整数。具体意义如题面所示。
输出格式
对于每个测试用例,输出一行一个整数,表示答案。
样例输入
sh
4
1000 10
200 3
300 4
10 5
样例输出
sh
3
2
1
2
运行限制

题解
java
5、贝贝的集合
题解
java