【蓝桥杯】练习题目汇总
门牌制作
题目描述
本题为填空题，只需要算出结果后，在代码中使用输出语句将所填结果输出即可。
小蓝要为一条街的住户制作门牌号。
这条街一共有 $2020$ 位住户，门牌号从 $1$ 到 $2020$ 编号。
小蓝制作门牌的方法是先制作 $0$ 到 $9$ 这几个数字字符，最后根据需要将字符粘贴到门牌上，例如门牌 1017 需要依次粘贴字符 $1、0、1、7$，即需要 $1$ 个字符 $0$，$2$ 个字符 $1$，$1$ 个字符 $7$。
请问要制作所有的 $1$ 到 $2020$ 号门牌，总共需要多少个字符 $2$？
运行限制
- 最大运行时间：1s
- 最大运行内存: 128M
常规思路
1 | |
1 | |
似乎熟悉了python之后，用python求解也很快。
简单方法
使用excel的功能
使用序列
使用快捷键CTRL+H，唤出替换，替换所有的2。
可以快速得到结果624，准确又省时间。
迷宫
题目描述
本题为填空题，只需要算出结果后，在代码中使用输出语句将所填结果输出即可。
X 星球的一处迷宫游乐场建在某个小山坡上。它是由 $10 \times 10$ 相互连通的小房间组成的。
房间的地板上写着一个很大的字母。我们假设玩家是面朝上坡的方向站立，则：
- $L$ 表示走到左边的房间，
- $R$ 表示走到右边的房间，
- $U$ 表示走到上坡方向的房间，
- $D$ 表示走到下坡方向的房间。
X 星球的居民有点懒，不愿意费力思考。他们更喜欢玩运气类的游戏。这个游戏也是如此！
开始的时候，直升机把 $100$ 名玩家放入一个个小房间内。玩家一定要按照地上的字母移动。
迷宫地图如下：
1 | |
请你计算一下，最后，有多少玩家会走出迷宫，而不是在里边兜圈子？
如果你还没明白游戏规则，可以参看下面一个简化的 4x4 迷宫的解说图：
运行限制
| 语言 | 最大运行时间 | 最大运行内存 |
|---|---|---|
| C++ | 1s | 128M |
| C | 1s | 128M |
| Python3 | 1s | 128M |
| Java | 1s | 128M |
解题思路
1 | |
DFS解法：
1 | |
1 | |
星期一
题目描述
本题为填空题，只需要算出结果后，在代码中使用输出语句将所填结果输出即可。
整个 $20$ 世纪（$1901$ 年 $1$ 月 $1$ 日至 $2000$ 年 $12$ 月 $31$ 日之间），一共有多少个星期一？(不要告诉我你不知道今天是星期几)
运行限制
| 语言 | 最大运行时间 | 最大运行内存 |
|---|---|---|
| C++ | 1s | 128M |
| C | 1s | 128M |
| Python3 | 1s | 128M |
| Java | 1s | 128M |
解题思路
直接用 Python datetime 库求解，第 6 行可以输出某个日期是星期几。
1 | |
乘积尾零
题目描述
本题为填空题，只需要算出结果后，在代码中使用输出语句将所填结果输出即可。
如下的 $10$ 行数据，每行有 $10$ 个整数，请你求出它们的乘积的末尾有多少个零？
1 | |
运行限制
| 语言 | 最大运行时间 | 最大运行内存 |
|---|---|---|
| C++ | 1s | 128M |
| C | 1s | 128M |
| Python3 | 1s | 128M |
| Java | 1s | 128M |
解题思路
将字符串转换成表格，先计算乘积，然后结果由int整数型转换成str字符型，再存入列表中，这时候使用pop方法和列表切片，简单的遍历一下，就能得到结果。
1 | |
当然，也可以不使用列表
付账问题
题目描述
几个人一起出去吃饭是常有的事。但在结帐的时候，常常会出现一些争执。
现在有 $n$ 个人出去吃饭，他们总共消费了 $S$ 元。其中第 $i$ 个人带了 $a_i$元。幸运的是，所有人带的钱的总数是足够付账的，但现在问题来了：每个人分别要出多少钱呢？
为了公平起见，我们希望在总付钱量恰好为 $S$ 的前提下，最后每个人付的钱的标准差最小。这里我们约定，每个人支付的钱数可以是任意非负实数，即可以不是 1 分钱的整数倍。你需要输出最小的标准差是多少。
标准差的介绍：标准差是多个数与它们平均数差值的平方平均数，一般用于刻画这些数之间的”偏差有多大”。形式化地说，设第 $i$ 个人付的钱为 $b_i$ 元，那么标准差为 :
$S=\sqrt{\frac{1}{n}\sum_{i=1}^{n}(b_i-\frac{1}{n}\sum_{i=1}^{n}b_i)^{2}}$
输入描述
第一行包含两个整数 $n、S$；
第二行包含 $n$ 个非负整数 $a_1, \cdots, a_n$。
其中，$n \leq 5 \times 10^5, 0 \leq a_i \leq 10^9$ 。
输出描述
输出最小的标准差，四舍五入保留 4 位小数。
保证正确答案在加上或减去 $10^{−9}$ 后不会导致四舍五入的结果发生变化。
输入输出样例
示例
输入
1 | |
输出
1 | |
运行限制
| 语言 | 最大运行时间 | 最大运行内存 |
|---|---|---|
| C++ | 1s | 256M |
| C | 1s | 256M |
| Python3 | 1s | 256M |
| Java | 1s | 256M |
解题思路
1 | |
数字三角形
题目描述
上图给出了一个数字三角形。从三角形的顶部到底部有很多条不同的路径。对于每条路径，把路径上面的数加起来可以得到一个和，你的任务就是找到最大的和（路径上的每一步只可沿左斜线向下或右斜线向下走）。
输入描述
输入的第一行包含一个整数 $N\ (1 \leq N \leq 100)$，表示三角形的行数。
下面的 $N$ 行给出数字三角形。数字三角形上的数都是 $0$ 至 $99$ 之间的整数。
输出描述
输出一个整数，表示答案。
输入输出样例
示例
输入
1 | |
输出
1 | |
运行限制
| 语言 | 最大运行时间 | 最大运行内存 |
|---|---|---|
| C++ | 1s | 128M |
| C | 1s | 128M |
| Python3 | 1s | 128M |
| Java | 1s | 128M |
42点问题
题目描述
请你设计一个程序对该问题进行解答。
众所周知在扑克牌中，有一个老掉牙的游戏叫做 $24$ 点，选取 $4$ 张牌进行加减乘除，看是否能得出 $24$ 这个答案。
现在小蓝同学发明了一个新游戏，他从扑克牌中依次抽出6张牌，注意不是一次抽出，进行计算，看是否能够组成 $42$ 点,满足输出 YES，反之输出 NO。
最先抽出来的牌作为第一个操作数，抽出牌做第二个操作数，运算结果再当作第一个操作数，继续进行操作。
注：除不尽的情况保留整数，而且扑克牌的四张 $10$ 都丢了，不会出现 $10$。
请设计一个程序对该问题进行解答。
输入描述
输出仅一行包含 $6$ 个字符。
保证字符 $\in$ 3 4 5 6 7 8 9 10 J Q K A 2。
输出描述
若给出到字符能够组成 $42$ 点 , 满足输出 YES，反之输出 NO。
输入输出样例
示例
输入
1 | |
输出
1 | |
样例说明
- $K\times A=K$ 即 $13\times 1=13$
- $13/12=1$ 保留整数
- $1+6=7$
- $7*2=14$
- $14*3=42$
运行限制
| 语言 | 最大运行时间 | 最大运行内存 |
|---|---|---|
| C++ | 1s | 128M |
| C | 1s | 128M |
| Python3 | 1s | 128M |
| Java | 1s | 128M |
数的划分
题目描述
将整数 $n$ 分成 $k$ 份，且每份不能为空，任意两份不能相同(不考虑顺序)。
例如：$n=7，k=3$，下面三种分法被认为是相同的。
$1，1，5; 1，5，1; 5，1，1;$
问有多少种不同的分法。
输入描述
输入一行，$2$ 个整数 $n,k\ (6 \leq n \leq 200，2 \leq k \leq 6)$。
输出描述
输出一个整数，即不同的分法。
输入输出样例
示例 1
输入
1 | |
输出
1 | |
运行限制
| 语言 | 最大运行时间 | 最大运行内存 |
|---|---|---|
| C++ | 1s | 128M |
| C | 1s | 128M |
| Python3 | 1s | 128M |
| Java | 1s | 128M |
数的计算
题目描述
输入一个自然数 $n\ (n \leq 1000)$，我们对此自然数按照如下方法进行处理:
不作任何处理;
在它的左边加上一个自然数,但该自然数不能超过原数的一半;
加上数后,继续按此规则进行处理,直到不能再加自然数为止。
问总共可以产生多少个数。
输入描述
输入一个正整数 $n$。
输出描述
输出一个整数，表示答案。
输入输出样例
示例 1
输入
1 | |
输出
1 | |
运行限制
| 语言 | 最大运行时间 | 最大运行内存 |
|---|---|---|
| C++ | 1s | 128M |
| C | 1s | 128M |
| Python3 | 1s | 128M |
| Java | 1s | 128M |
N皇后问题
题目描述
在 $N\times N$ 的方格棋盘放置了 $N$ 个皇后，使得它们不相互攻击（即任意 $2$ 个皇后不允许处在同一排，同一列，也不允许处在与棋盘边框成 $45$ 角的斜线上。你的任务是，对于给定的 $N$，求出有多少种合法的放置方法。
输入描述
输入中有一个正整数 $N≤10$，表示棋盘和皇后的数量
输出描述
为一个正整数，表示对应输入行的皇后的不同放置数量。
输入输出样例
示例 1
输入
1 | |
输出
1 | |
运行限制
| 语言 | 最大运行时间 | 最大运行内存 |
|---|---|---|
| C++ | 1s | 128M |
| C | 1s | 128M |
| Python3 | 1s | 128M |
| Java | 1s | 128M |
路径之谜
题目描述
小明冒充 $X$ 星球的骑士，进入了一个奇怪的城堡。
城堡里边什么都没有，只有方形石头铺成的地面。
假设城堡地面是 $n \times n$ 个方格。如下图所示。
按习俗，骑士要从西北角走到东南角。可以横向或纵向移动，但不能斜着走，也不能跳跃。每走到一个新方格，就要向正北方和正西方各射一箭。（城堡的西墙和北墙内各有 $n$ 个靶子）同一个方格只允许经过一次。但不必走完所有的方格。如果只给出靶子上箭的数目，你能推断出骑士的行走路线吗？有时是可以的，比如上图中的例子。
本题的要求就是已知箭靶数字，求骑士的行走路径（测试数据保证路径唯一）
输入描述
第一行一个整数 $N$ ($0 \leq N \leq 20$)，表示地面有 $N \times N$ 个方格。
第二行 $N$ 个整数，空格分开，表示北边的箭靶上的数字（自西向东）
第三行 $N$ 个整数，空格分开，表示西边的箭靶上的数字（自北向南）
输出描述
输出一行若干个整数，表示骑士路径。
为了方便表示，我们约定每个小格子用一个数字代表，从西北角开始编号: 0,1,2,3 $\cdots$
比如，上图中的方块编号为：
0 1 2 3
4 5 6 7
8 9 10 11
12 13 14 15
输入输出样例
示例
输入
1 | |
输出
1 | |
运行限制
| 语言 | 最大运行时间 | 最大运行内存 |
|---|---|---|
| C++ | 5s | 256M |
| C | 5s | 256M |
| Python3 | 5s | 256M |
| Java | 5s | 256M |
最大数字
问题描述
给定一个正整数 $N$ 。你可以对 $N$ 的任意一位数字执行任意次以下 2 种操 作：
将该位数字加 1 。如果该位数字已经是 9 , 加 1 之后变成 0 。
将该位数字减 1 。如果该位数字已经是 0 , 减 1 之后变成 9 。
你现在总共可以执行 1 号操作不超过 $A$ 次, 2 号操作不超过 $B$ 次。 请问你最大可以将 $N$ 变成多少?
输入格式
第一行包含 3 个整数: $N, A, B$ 。
输出格式
一个整数代表答案。
样例输入
1 | |
样例输出
1 | |
样例说明
对百位数字执行 2 次 2 号操作, 对十位数字执行 1 次 1 号操作。
评测用例规模与约定
对于 $30 %$ 的数据, $1 \leq N \leq 100 ; 0 \leq A, B \leq 10$。
对于 $100 %$ 的数据, $1 \leq N \leq 10^{17} ; 0 \leq A, B \leq 100$
运行限制
| 语言 | 最大运行时间 | 最大运行内存 |
|---|---|---|
| C++ | 1s | 512M |
| C | 1s | 512M |
| Python3 | 1s | 512M |
| Java | 1s | 512M |
长草
题目描述
小明有一块空地，他将这块空地划分为 $n$ 行 $m$ 列的小块，每行和每列的长度都为 1。
小明选了其中的一些小块空地，种上了草，其他小块仍然保持是空地。
这些草长得很快，每个月，草都会向外长出一些，如果一个小块种了草，则它将向自己的上、下、左、右四小块空地扩展，
这四小块空地都将变为有草的小块。请告诉小明，$k$ 个月后空地上哪些地方有草。
输入描述
输入的第一行包含两个整数 $n, m$。
接下来 $n$ 行，每行包含 $m$ 个字母，表示初始的空地状态，字母之间没有空格。如果为小数点，表示为空地，如果字母为 $g$，表示种了草。
接下来包含一个整数 $k$。 其中，$2 \leq n, m \leq 1000，1 \leq k \leq 1000$。
输出描述
输出 $n$ 行，每行包含 $m$ 个字母，表示 $k$ 个月后空地的状态。如果为小数点，表示为空地，如果字母为 $g$，表示长了草。
输入输出样例
示例
输入
1 | |
输出
1 | |
运行限制
| 语言 | 最大运行时间 | 最大运行内存 |
|---|---|---|
| C++ | 1s | 256M |
| C | 1s | 256M |
| Python3 | 1s | 256M |
| Java | 1s | 256M |
走迷宫
题目描述
给定一个 $N\times M$ 的网格迷宫 $G$。$G$ 的每个格子要么是道路，要么是障碍物（道路用 $1$ 表示，障碍物用 $0$ 表示）。
已知迷宫的入口位置为 $(x_1,y_1)$，出口位置为 $(x_2 , y_2)$。问从入口走到出口，最少要走多少个格子。
输入描述
输入第 $1$ 行包含两个正整数 $N,M$，分别表示迷宫的大小。
接下来输入一个 $N\times M$ 的矩阵。若 $G_{i,j}=1$ 表示其为道路，否则表示其为障碍物。
最后一行输入四个整数 $x_1,y_1,x_2,y_2$，表示入口的位置和出口的位置。
$1\leq N,M\leq10^2$，$0\leq G_{i,j}\leq 1$，$1\leq x_1,x_2\leq N$，$1\leq y_1,y_2\leq M$。
输出描述
输出仅一行，包含一个整数表示答案。
若无法从入口到出口，则输出 $-1$。
输入输出样例
示例 1
输入
1 | |
输出
1 | |
运行限制
| 语言 | 最大运行时间 | 最大运行内存 |
|---|---|---|
| C++ | 1s | 128M |
| C | 1s | 128M |
| Python3 | 1s | 128M |
| Java | 1s | 128M |
迷宫
题目描述
本题为填空题，只需要算出结果后，在代码中使用输出语句将所填结果输出即可。
下图给出了一个迷宫的平面图，其中标记为 $1$ 的为障碍，标记为 $0$ 的为可以通行的地方。
1 | |
迷宫的入口为左上角，出口为右下角，在迷宫中，只能从一个位置走到这 个它的上、下、左、右四个方向之一。
对于上面的迷宫，从入口开始，可以按 DRRURRDDDR 的顺序通过迷宫， 一共 $10$ 步。其中 $D、U、L、R$ 分别表示向下、向上、向左、向右走。 对于下面这个更复杂的迷宫（$30$ 行 $50$ 列），请找出一种通过迷宫的方式，其使用的步数最少，在步数最少的前提下，请找出字典序最小的一个作为答案。
请注意在字典序中 $D<L<R<U$。
1 | |
运行限制
| 语言 | 最大运行时间 | 最大运行内存 |
|---|---|---|
| C++ | 1s | 256M |
| C | 1s | 256M |
| Python3 | 1s | 256M |
| Java | 1s | 256M |
公共抽签
题目描述
小$A$的学校，蓝桥杯的参赛名额非常有限，只有 $m$ 个名额，但是共有 $n$ 个人报名。
作为老师非常苦恼，他不知道该让谁去，他在寻求一个绝对公平的方式。
于是他准备让大家抽签决定，即 $m$ 个签是去，剩下的是不去。
小 $A$ 非常想弄明白最后的抽签结果会有多少种不同到情况，请你设计一个程序帮帮小 $A$！
输入描述
输入第一行包含两个字符 $n,m$，其含义如题所述。
接下来第二行到第 $n+1$ 行每行包含一个字符串 $S$ ，表示个人名。
$1\leq m\leq n\leq 15$。
输出描述
输出共若干行，每行包含 $m$ 个字符串，表示该结果被选中到人名（需按字符串的输入顺序大小对结果进行排序）。
输入输出样例
示例
输入
1 | |
输出
1 | |
运行限制
| 语言 | 最大运行时间 | 最大运行内存 |
|---|---|---|
| C++ | 1s | 128M |
| C | 1s | 128M |
| Python3 | 1s | 128M |
| Java | 1s | 128M |
座次问题
题目描述
小 $A$ 的学校，老师好不容易解决了蓝桥杯的报名问题，现在老师又犯愁了。
现在有 $N$ 位同学参加比赛，但是老师想给他们排座位，但是排列方式太多了。
老师非常想弄明白最后的排座次的结果是什么样子的，到底有多少种结果。
请设计一个程序帮助老师。
最后输出各种情况的人名即可，一行一种情况，每种情况的名字按照报名即输入顺序排序。
输入描述
输入第一行包含一个整数 $N$。
接下来 $N$ 行每行包含一个字符串 $S_i$，表示人名。
$1\leq N \leq 10$，$\sum\limits_{i=1}^{N} |S_i| \leq 10^2$。
输出描述
输出共若干行，每行输出各种情况的人名。一行一种情况，每种情况的名字按照报名即输入顺序排序。
输入输出样例
示例
输入
1 | |
输出
1 | |
运行限制
| 语言 | 最大运行时间 | 最大运行内存 |
|---|---|---|
| C++ | 1s | 128M |
| C | 1s | 128M |
| Python3 | 1s | 128M |
| Java | 1s | 128M |
CLZ银行问题
题目描述
$CLZ$ 银行只有两个接待窗口，$VIP$ 窗口和普通窗口，$VIP$ 用户进入 $VIP$ 窗口排队，剩下的进入普通窗口排队。现有 $M$ 次操作，操作有四种类型，如下：
IN name V：表示一名叫name的用户到 $VIP$ 窗口排队OUT V：表示 $VIP$ 窗口队头的用户离开排队IN name N：表示一名叫name的用户到普通窗口排队OUT N：表示普通窗口队头的用户离开排队
求 $M$ 次操作结束后 $VIP$ 窗口队列和普通窗口队列中的姓名。
输入描述
第一行是一个整数 $M（1\leq M \leq 1000）$，表示一共有 $M$ 次操作。
第二行到第 $M+1$ 行输入操作，格式如下：
IN name VOUT VIN name NOUT N
输出描述
输出 $M$ 次操作后 $VIP$ 窗口队列和普通窗口队列中的姓名（从头到尾），先输出 $VIP$ 窗口队列后输出普通窗口队列。
输入输出样例
示例 1
输入
1 | |
输出
1 | |
运行限制
| 语言 | 最大运行时间 | 最大运行内存 |
|---|---|---|
| C++ | 1s | 128M |
| C | 1s | 128M |
| Python3 | 1s | 128M |
| Java | 1s | 128M |
费里的语言
题目描述
小发明家弗里想创造一种新的语言，众所周知，发明一门语言是非常困难的，首先你就要克服一个困难就是，有大量的单词需要处理，现在弗里求助你帮他写一款程序，判断是否出现重复的两个单词。
输入描述
第 $1$ 行，输入 $N$，代表共计创造了多少个单词。
第 $2$ 行至第 $N+1$ 行，输入 $N$ 个单词。
$1\leq N \leq 10^4$，保证字符串的总输入量不超过 $10^6$。
输出描述
输出仅一行。若有重复的单词，就输出重复单词，没有重复单词，就输出 NO，多个重复单词输出最先出现的。
输入输出样例
示例1
输入
1 | |
输出
1 | |
示例2
输入
1 | |
输出
1 | |
运行限制
| 语言 | 最大运行时间 | 最大运行内存 |
|---|---|---|
| C++ | 3s | 512M |
| C | 3s | 512M |
| Python3 | 3s | 512M |
| Java | 3s | 512M |
快递分拣
题目描述
蓝桥王国的每个快递都包含两个参数：1.快递单号 2.快递城市。
小李是蓝桥王国的一名快递员，每天的快递分拣让他苦不堪言。
于是他想要你帮他设计一个程序用于快递的分拣（将不同快递按城市信息分开）。
输入描述
输入第一行包含一个整数 $N$,表示快递的个数。
接下来第 $2 \sim N+1$ 行每行包含一个字符串 $S$ 和一个字符串 $P$，分别快递单号以及快递对应的城市。
$1\leq N \leq 10^3$，保证数据量不超过 $10^6$。
输出描述
输出共若干行。按城市的输入顺序依次输出城市的名称以及城市的快递个数，以及该城市的所有快递单号（单号按照输入顺序排序）。
输入输出样例
示例
输入
1 | |
输出
1 | |
运行限制
| 语言 | 最大运行时间 | 最大运行内存 |
|---|---|---|
| C++ | 1s | 256M |
| C | 1s | 256M |
| Python3 | 1s | 256M |
| Java | 1s | 256M |
大学里到树木要打药
题目描述
教室外有 $N$ 棵树（树的编号从 $0\sim N-1$），根据不同的位置和树种，学校要对其上不同的药。
因为树的排列成线性，且非常长，我们可以将它们看作一条直线给他们编号。
对于树的药是成区间分布，比如 $3 \sim 5$ 号的树靠近下水道，所以他们要用驱蚊虫的药， $20 \sim 26$ 号的树，他们排水不好，容易涝所以要给他们用点促进根系的药 $\cdots$诸如此类。
每种不同的药要花不同的钱。
现在已知共有 $M$ 个这样的区间，并且给你每个区间花的钱，问最后这些树木要花多少药费。
输入描述
每组输入的第一行有两个整数 $N$和 $M$。$N$ 代表马路的共计多少棵树，$M$ 代表区间的数目，$N$ 和 $M$ 之间用一个空格隔开。
接下来的 $M$ 行每行包含三个不同的整数，用一个空格隔开，分别表示一个区域的起始点 $L$ 和终止点 $R$ 的坐标，以及花费。
$1\leq L\leq R \leq N \leq 10^6,1\leq M\leq 10^5$，保证花费总和不超过 int 范围。
输出描述
输出包括一行，这一行只包含一个整数，所有的花费。
输入输出样例
示例
输入
1 | |
输出
1 | |
运行限制
| 语言 | 最大运行时间 | 最大运行内存 |
|---|---|---|
| C++ | 1s | 128M |
| C | 1s | 128M |
| Python3 | 1s | 128M |
| Java | 1s | 128M |
大学里的树木要维护
题目描述
教室外有 $N$ 棵树（树的编号从 $1\sim N$），根据不同的位置和树种，学校已经对其进行了多年的维护。
因为树的排列成线性，且非常长，我们可以将它们看作一条直线给他们编号。
由于已经维护了多年，每一个树都由学校的园艺人员进行了维护费用的统计。
每棵树的前期维护费用各不相同，但是由于未来需要要打药，所以有些树木的维护费用太高的话，就要重新种植。
由于维护费用也称区间分布，所以常常需要统一个区间里的树木的维护开销。
现给定一个长度为 $N$ 的数组 $A$ 以及 $M$ 个查询，$A_i$ 表示第 $i$ 棵树到维护费用。对于每个查询包含一个区间，园艺人员想知道该区间内的树木维护的开销是多少。
请你编写程序帮帮他！
输入描述
每组输入的第一行有两个整数 $N$和 $M$。$N$ 代表马路的共计多少棵树，$M$ 代表区间的数目，$N$ 和 $M$ 之间用一个空格隔开。
接下来的一行，包含 $N$ 个数 $A_1,A_2,\cdots,A_N$，分别表示每棵树的维护费用，每个数之间用空格隔开。
接下来的 $M$ 行每行包含两个不同的整数，用一个空格隔开，表示一个区域的起始点 $L$ 和终止点 $R$ 的坐标。
输出描述
输出包括 $M$ 行，每一行只包含一个整数，表示维护的开销。
输入输出样例
示例
输入
1 | |
输出
1 | |
运行限制
| 语言 | 最大运行时间 | 最大运行内存 |
|---|---|---|
| C++ | 1s | 128M |
| C | 1s | 128M |
| Python3 | 1s | 128M |
| Java | 1s | 128M |
合根植物
题目描述
$w$ 星球的一个种植园，被分成 $m \times n$ 个小格子（东西方向 $m$ 行，南北方向 $n$ 列）。每个格子里种了一株合根植物。
这种植物有个特点，它的根可能会沿着南北或东西方向伸展，从而与另一个格子的植物合成为一体。
如果我们告诉你哪些小格子间出现了连根现象，你能说出这个园中一共有多少株合根植物吗？
输入描述
第一行，两个整数 $m,n$，用空格分开，表示格子的行数、列数（$1 \leq m,n \leq 1000$）。
接下来一行，一个整数 $k$ ($0 \leq k \leq 10^5$ )，表示下面还有 $k$ 行数据。
接下来 $k$ 行，每行两个整数 $a，b$，表示编号为 $a$ 的小格子和编号为 $b$ 的小格子合根了。
格子的编号一行一行，从上到下，从左到右编号。
比如：$5 \times 4$ 的小格子，编号：
1 | |
输出描述
输出植物数量。
输入输出样例
示例
输入
1 | |
输出
1 | |
样例说明
其合根情况参考下图：
运行限制
| 语言 | 最大运行时间 | 最大运行内存 |
|---|---|---|
| C++ | 2s | 256M |
| C | 2s | 256M |
| Python3 | 2s | 256M |
| Java | 2s | 256M |
修改数组
题目描述
给定一个长度为 $N$ 的数组 $A = [A_1,A_2,··· ,A_N]$，数组中有可能有重复出现的整数。
现在小明要按以下方法将其修改为没有重复整数的数组。小明会依次修改$A_2,A_3,··· ,A_N$。
当修改 $A_i$ 时，小明会检查 $A_i$ 是否在 $A_1$ ∼ $A_i−1$ 中出现过。如果出现过，则小明会给 $A_i$ 加上 1 ；如果新的 $A_i$ 仍在之前出现过，小明会持续给 $A_i$ 加 1 ，直 到 $A_i$ 没有在 $A_1$ ∼ $A_i−1$ 中出现过。
当 $A_N$ 也经过上述修改之后，显然 $A$ 数组中就没有重复的整数了。
现在给定初始的 $A$ 数组，请你计算出最终的 $A$ 数组。
输入描述
第一行包含一个整数 $N$。
第二行包含 $N$ 个整数 $A_1,A_2,··· ,A_N$。
其中，$1 \leq N \leq 10^5，1 \leq A_i \leq 10^6$。
输出描述
输出 $N$ 个整数，依次是最终的 $A_1,A_2,··· ,A_N$。
输入输出样例
示例
输入
1 | |
输出
1 | |
运行限制
| 语言 | 最大运行时间 | 最大运行内存 |
|---|---|---|
| C++ | 1s | 256M |
| C | 1s | 256M |
| Python3 | 1s | 256M |
| Java | 1s | 256M |
分巧克力
题目描述
儿童节那天有 K 位小朋友到小明家做客。小明拿出了珍藏的巧克力招待小朋友们。
小明一共有 $N$ 块巧克力，其中第 $i$ 块是 $H_i \times Wi$ 的方格组成的长方形。为了公平起见，
小明需要从这 $N$ 块巧克力中切出 K 块巧克力分给小朋友们。切出的巧克力需要满足：
形状是正方形，边长是整数;
大小相同;
例如一块 6x5 的巧克力可以切出 6 块 2x2 的巧克力或者 2 块 3x3 的巧克力。
当然小朋友们都希望得到的巧克力尽可能大，你能帮小明计算出最大的边长是多少么？
输入描述
第一行包含两个整数 $N,K$ ($1 \leq N, K \leq 10^5$)。
以下 N 行每行包含两个整数 $H_i,W_i$ ($1 \leq H_i, W_i \leq 10^5$)。
输入保证每位小朋友至少能获得一块 1x1 的巧克力。
输出描述
输出切出的正方形巧克力最大可能的边长。
输入输出样例
示例
输入
1 | |
输出
1 | |
运行限制
| 语言 | 最大运行时间 | 最大运行内存 |
|---|---|---|
| C++ | 2s | 256M |
| C | 2s | 256M |
| Python3 | 2s | 256M |
| Java | 2s | 256M |
M次方根
题目描述
小$A$最近在学高等数学，他发现了一道题，求三次根号下 $27$。
现在已知，小$A$开始计算，$1$ 的三次方得 $1$， $2$ 的三次方得 $8$ ，$3$ 的三次方得 $27$，然后他很高兴的填上了 $3$。接着他要求 $5$ 次根号下 $164$。
然后他开始 $1$ 的三次方得 $1$， $2$ 的三次方得 $8$ ，$3$ 的三次方得$27\cdots$
直到他算到了秃头，也没有找到答案。
这时一旁的小$B$看不下去了，说这题答案又不是个整数。
小$A$震惊，原来如此。
作为程序高手的小$A$，打算设计一个程序用于求解 $M$ 次跟下 $N$ 的值。
但是由于要考虑精度范围，答案必须要保留 $7$ 位小数，三次根号下 $27$ 都要掰手指的小$A$又怎么会设计呢。
请你帮小$A$设计一个程序用于求解 $M$ 次根号 $N$。
输入描述
每组输入的第一行有两个整数 $N$ 和 $M$，数据间用空格隔开。
$1\leq N \leq 10^5$，$1\leq M \leq 10^2$，$M < N$。
输出描述
输出一个实数表示答案（请保留小数点后 $7$ 位）。
输入输出样例
示例
输入
1 | |
输出
1 | |
运行限制
| 语言 | 最大运行时间 | 最大运行内存 |
|---|---|---|
| C++ | 1s | 128M |
| C | 1s | 128M |
| Python3 | 1s | 128M |
| Java | 1s | 128M |
找零问题
题目描述
蓝桥商店的老板需要找零 $n$ 元钱。
钱币的面额有：$100$ 元、$50$ 元、$20$ 元、$5$ 元、$1$ 元，问如何找零使得所需钱币的数量最少？
注意：$n$ 可能为 $0$，也能为几百元（别问，问就是来着里微信提现来了）
输入描述
在第一行给出测试例个数 $N$，代表需要找零的钱数。
$1\leq N \leq 10^5$。
输出描述
输出共有 $5$ 行，每一行输出数据输出找零的金额与数量，详情看样例。
示例
输入
1 | |
输出
1 | |
运行限制
| 语言 | 最大运行时间 | 最大运行内存 |
|---|---|---|
| C++ | 1s | 128M |
| C | 1s | 128M |
| Python3 | 1s | 128M |
| Java | 1s | 128M |
小B的宿舍
题目描述
小B的宿舍楼沿着走廊南北向的两边各有 $200$ 个房间，如下所示：
1 | |
最近，由于转专业和专业分流的原因，宿舍将迎来新的调整，以便组成新的班级后方便管理。
但是由于走廊狭窄，走廊里只能通过一个搬运的物品（可以同向也可以反向），因此必须指定高效的搬运计划。
老师给了每位同学下达了以下要求，让同学们体现收拾好行李，然后给每位同学 $10$ 分钟的时间搬运。
当从房间 $i$ 搬运行李到 $j$ 时，$i$ 与 $j$ 之间的走廊都会被占用。所以，$10$ 分钟之内同一段走廊最多 $1$ 个人同时搬运，不重叠的走廊也可以同时搬运。
小B的老师是个数学老师，经过运筹学一通计算他得到了最优的搬运计划。
虽然计划不唯一，但是最优值唯一，请问这个最短时间是多少？
输入描述
输入数据有 $T$ 组测试例，在第一行给出测试例个数 $T$。
每个测试例的第一行是一个整数 $N$（$1\leq N \leq 200$)，表示要搬运行李的人数。
接下来 $N$ 行，每行两个正整数 $s$ 和 $t$，表示一个人，要将行李是从房间 $s$ 移到到房间 $t$。
输出描述
每组输入都有一行输出数据，为一整数 $Time$，表示完成任务所花费的最小时间。
示例
输入
1 | |
输出
1 | |
运行限制
| 语言 | 最大运行时间 | 最大运行内存 |
|---|---|---|
| C++ | 1s | 128M |
| C | 1s | 128M |
| Python3 | 1s | 128M |
| Java | 1s | 128M |
数字三角形
题目描述
上图给出了一个数字三角形。从三角形的顶部到底部有很多条不同的路径。对于每条路径，把路径上面的数加起来可以得到一个和，你的任务就是找到最大的和。
路径上的每一步只能从一个数走到下一层和它最近的左边的那个数或者右 边的那个数。此外，向左下走的次数与向右下走的次数相差不能超过 1。
输入描述
输入的第一行包含一个整数 $N\ (1 \leq N \leq 100)$，表示三角形的行数。
下面的 $N$ 行给出数字三角形。数字三角形上的数都是 0 至 100 之间的整数。
输出描述
输出一个整数，表示答案。
输入输出样例
示例
输入
1 | |
输出
1 | |
运行限制
| 语言 | 最大运行时间 | 最大运行内存 |
|---|---|---|
| C++ | 1s | 256M |
| C | 1s | 256M |
| Python3 | 1s | 256M |
| Java | 1s | 256M |
游戏中的学问
题目描述
大家应该都见过很多人手拉手围着篝火跳舞的场景吧？一般情况下，大家手拉手跳舞总是会围成一个大圈，每个人的左手拉着旁边朋友的右手，右手拉着另一侧朋友的左手。
不过，如果每一个人都随机的拉住两个不同人的手，然后再慢慢散开，事情就变得有趣多了——此时大家依旧会形成圈，不过却可能会形成多个独立的圈。当然这里我们依然要求一个人的右手只能拉另一个人的左手，反之亦然。
班里一共有 $N$ 个同学，由 $1$ 到 $N$ 编号。Will 想知道，究竟有多少种本质不同的拉手方案，使得最终大家散开后恰好形成 $k$ 个圈呢？
给定两种方案，若存在一个人和他的一只手，满足在这两种方案中，拉着这只手的人的编号不同，则这两种方案本质不同。
输入描述
输入一行包含三个正整数$N,k,P$。
其中，$3 \leq k \leq N \leq 3000$，$10^4 \leq p \leq 2 \times 10^9$。
输出描述
输出一行一个整数，表示本质不同的方案数对 $p$ 的余数。保证 $p$ 一定是一个质数。
输入输出样例
示例 1
输入
1 | |
输出
1 | |
运行限制
| 语言 | 最大运行时间 | 最大运行内存 |
|---|---|---|
| C++ | 2s | 128M |
| C | 2s | 128M |
| Python3 | 2s | 128M |
| Java | 2s | 128M |
跳跃
题目描述
小蓝在一个 $n$ 行 $m$ 列的方格图中玩一个游戏。
开始时，小蓝站在方格图的左上角，即第 $1$ 行第 $1$ 列。
小蓝可以在方格图上走动，走动时，如果当前在第 $r$ 行第 $c$ 列，他不能走到行号比 $r$ 小的行，也不能走到列号比 $c$ 小的列。同时，他一步走的直线距离不超过 $3$。
例如，如果当前小蓝在第 $3$ 行第 $5$ 列，他下一步可以走到第 $3$ 行第 $6$ 列、第 $3$ 行第 $7$ 列、第 $3$ 行第 $8$ 列、第 $4$ 行第 $5$ 列、第 $4$ 行第 $6$ 列、第 $4$ 行第 $7$ 列、第 $5$ 行第 $5$ 列、第 $5$ 行第 $6$ 列、第 $6$ 行第 $5$ 列之一。
小蓝最终要走到第 $n$ 行第 $m$ 列。
在图中，有的位置有奖励，走上去即可获得，有的位置有惩罚，走上去就要接受惩罚。奖励和惩罚最终抽象成一个权值，奖励为正，惩罚为负。
小蓝希望，从第 $1$ 行第 $1$ 列走到第 $n$ 行第 $m$ 列后，总的权值和最大。请问最大是多少？
输入描述
输入的第一行包含两个整数 $n, m$，表示图的大小。
接下来 $n$ 行，每行 $m$ 个整数，表示方格图中每个点的权值。
其中，$1 \leq n \leq 100，-10^4 \leq 权值 \leq 10^4$。
输出描述
输出一个整数，表示最大权值和。
输入输出样例
示例 1
输入
1 | |
输出
1 | |
运行限制
| 语言 | 最大运行时间 | 最大运行内存 |
|---|---|---|
| C++ | 1s | 128M |
| C | 1s | 128M |
| Python3 | 1s | 128M |
| Java | 1s | 128M |
小明的背包1
题目描述
小明有一个容量为 $V$ 的背包。
这天他去商场购物，商场一共有 $N$ 件物品，第 $i$ 件物品的体积为 $w_i$，价值为 $v_i$。
小明想知道在购买的物品总体积不超过 $V$ 的情况下所能获得的最大价值为多少，请你帮他算算。
输入描述
输入第 $1$ 行包含两个正整数 $N,V$，表示商场物品的数量和小明的背包容量。
第 $2\sim N+1$ 行包含 $2$ 个正整数 $w,v$，表示物品的体积和价值。
$1\leq N\leq10^2$，$1\leq V \leq 10^3$，$1 \leq w_i,v_i \leq10^3$。
输出描述
输出一行整数表示小明所能获得的最大价值。
输入输出样例
示例 1
输入
1 | |
输出
1 | |
运行限制
| 语言 | 最大运行时间 | 最大运行内存 |
|---|---|---|
| C++ | 1s | 128M |
| C | 1s | 128M |
| Python3 | 1s | 128M |
| Java | 1s | 128M |
小明的背包2
题目描述
小明有一个容量为 $V$ 的背包。
这天他去商场购物，商场一共有 $N$ 种物品，第 $i$ 种物品的体积为 $w_i$，价值为 $v_i$，每种物品都有无限多个。
小明想知道在购买的物品总体积不超过 $V$ 的情况下所能获得的最大价值为多少，请你帮他算算。
输入描述
输入第 $1$ 行包含两个正整数 $N,V$，表示商场物品的数量和小明的背包容量。
第 $2\sim N+1$ 行包含 $2$ 个正整数 $w,v$，表示物品的体积和价值。
$1\leq N\leq10^3$，$1\leq V \leq 10^3$，$1 \leq w_i,v_i \leq10^3$。
输出描述
输出一行整数表示小明所能获得的最大价值。
输入输出样例
示例 1
输入
1 | |
输出
1 | |
运行限制
| 语言 | 最大运行时间 | 最大运行内存 |
|---|---|---|
| C++ | 1s | 256M |
| C | 1s | 256M |
| Python3 | 1s | 256M |
| Java | 1s | 256M |
小明的背包3
题目描述
小明有一个容量为 $V$ 的背包。
这天他去商场购物，商场一共有 $N$ 种物品，第 $i$ 种物品的体积为 $w_i$，价值为 $v_i$，数量为 $s_i$。
小明想知道在购买的物品总体积不超过 $V$ 的情况下所能获得的最大价值为多少，请你帮他算算。
输入描述
输入第 $1$ 行包含两个正整数 $N,V$，表示商场物品的数量和小明的背包容量。
第 $2\sim N+1$ 行包含 $3$ 个正整数 $w,v,s$，表示物品的体积和价值。
$1\leq N\leq10^2$，$1\leq V \leq 2\times10^2$，$1 \leq w_i,v_i,s_i \leq 2\times10^2$。
输出描述
输出一行整数表示小明所能获得的最大价值。
输入输出样例
示例 1
输入
1 | |
输出
1 | |
运行限制
| 语言 | 最大运行时间 | 最大运行内存 |
|---|---|---|
| C++ | 1s | 256M |
| C | 1s | 256M |
| Python3 | 1s | 256M |
| Java | 1s | 256M |
蓝肽子序列
题目描述
L 星球上的生物由蛋蓝质组成，每一种蛋蓝质由一类称为蓝肽的物资首尾连接成一条长链后折叠而成。
生物学家小乔正在研究 L 星球上的蛋蓝质。她拿到两个蛋蓝质的蓝肽序列，想通过这两条蓝肽序列的共同特点来分析两种蛋蓝质的相似性。
具体的，一个蓝肽可以使用 $1$ 至 $5$ 个英文字母表示，其中第一个字母大写，后面的字母小写。一个蛋蓝质的蓝肽序列可以用蓝肽的表示顺序拼接而成。
在一条蓝肽序列中，如果选取其中的一些位置，把这些位置的蓝肽取出，并按照它们在原序列中的位置摆放，则称为这条蓝肽的一个子序列。蓝肽的子序列不一定在原序列中是连续的，中间可能间隔着一些未被取出的蓝肽。
如果第一条蓝肽序列可以取出一个子序列与第二条蓝肽序列中取出的某个子序列相等，则称为一个公共蓝肽子序列。
给定两条蓝肽序列，找出他们最长的那个公共蓝肽子序列的长度。
输入描述
输入两行，每行包含一个字符串，表示一个蓝肽序列。字符串中间没有空格等分隔字符。
其中有 ，两个字符串的长度均不超过 $1000$。
输出描述
输出一个整数，表示最长的那个公共蓝肽子序列的长度。
输入输出样例
示例
输入
1 | |
输出
1 | |
运行限制
| 语言 | 最大运行时间 | 最大运行内存 |
|---|---|---|
| C++ | 1s | 128M |
| C | 1s | 128M |
| Python3 | 1s | 128M |
| Java | 1s | 128M |
合唱队形
题目描述
$N$ 位同学站成一排，音乐老师要请其中的 $(N-K)$ 位同学出列，使得剩下的 $K$ 位同学排成合唱队形。
合唱队形是指这样的一种队形：设 $K$ 位同学从左到右依次编号为 $1，2，\cdots K$，他们的身高分别为 $T_1，T_2，\cdots，T_K$， 则他们的身高满足 $T_1< \cdots < T_i> T_{i+1}> \cdots >T_K(1 \leq i \leq K)$。
你的任务是，已知所有 $N$ 位同学的身高，计算最少需要几位同学出列，可以使得剩下的同学排成合唱队形。
输入描述
输入两行。
第一行是一个整数 $N\ (2 \leq N \leq 100)$，表示同学的总数。
第二行有 $n$ 个整数，用空格分隔，第 $i$ 个整数 $T_i(130 \leq T_i \leq 230)$ 是第 $i$ 位同学的身高(厘米)。
输出描述
输出一个整数，就是最少需要几位同学出列。
输入输出样例
示例 1
输入
1 | |
输出
1 | |
运行限制
| 语言 | 最大运行时间 | 最大运行内存 |
|---|---|---|
| C++ | 1s | 128M |
| C | 1s | 128M |
| Python3 | 1s | 128M |
| Java | 1s | 128M |
最优包含
题目描述
我们称一个字符串 $S$ 包含字符串 $T$ 是指 $T$ 是 $S$ 的一个子序列，即可以从字符串 $S$ 中抽出若干个字符，它们按原来的顺序组合成一个新的字符串与 $T$ 完全一样。
给定两个字符串 $S$ 和 $T$，请问最少修改 $S$ 中的多少个字符，能使 $S$ 包含 $T$ ？
其中，$1 \leq |T| \leq |S| \leq 1000$。
输入描述
输入两行，每行一个字符串。
第一行的字符串为 $S$，第二行的字符串为 $T$。
两个字符串均非空而且只包含大写英文字母。
输出描述
输出一个整数，表示答案。
输入输出样例
示例
输入
1 | |
输出
1 | |
运行限制
| 语言 | 最大运行时间 | 最大运行内存 |
|---|---|---|
| C++ | 1s | 256M |
| C | 1s | 256M |
| Python3 | 1s | 256M |
| Java | 1s | 256M |
路径
本题为填空题，只需要算出结果后，在代码中使用输出语句将所填结果输出即可。
小蓝学习了最短路径之后特别高兴，他定义了一个特别的图，希望找到图 中的最短路径。
小蓝的图由 2021 个结点组成，依次编号 1 至 2021。
对于两个不同的结点 a, b，如果 a 和 b 的差的绝对值大于 21，则两个结点 之间没有边相连；如果 a 和 b 的差的绝对值小于等于 21，则两个点之间有一条 长度为 a 和 b 的最小公倍数的无向边相连。
例如：结点 1 和结点 23 之间没有边相连；结点 3 和结点 24 之间有一条无 向边，长度为 24；结点 15 和结点 25 之间有一条无向边，长度为 75。
请计算，结点 1 和结点 2021 之间的最短路径长度是多少。
提示：建议使用计算机编程解决问题。
运行限制
| 语言 | 最大运行时间 | 最大运行内存 |
|---|---|---|
| C++ | 1s | 128M |
| C | 1s | 128M |
| Python3 | 1s | 128M |
| Java | 1s | 128M |
蓝桥王国
题目描述
小明是蓝桥王国的王子，今天是他登基之日。
在即将成为国王之前，老国王给他出了道题，他想要考验小明是否有能力管理国家。
题目的内容如下：
蓝桥王国一共有 $N$ 个建筑和 $M$ 条单向道路，每条道路都连接着两个建筑，每个建筑都有自己编号，分别为 $1\sim N$ 。（其中皇宫的编号为 $1$）
国王想让小明回答从皇宫到每个建筑的最短路径是多少，但紧张的小明此时已经无法思考，请你编写程序帮助小明回答国王的考核。
输入描述
输入第一行包含三个正整数 $N,M$。
第 $2$ 到 $M + 1$ 行每行包含三个正整数 $u,v,w$，表示 $u\rightarrow v$ 之间存在一条距离为 $w$ 的路。
$1\leq N \leq 3\times10^5$，$1 \leq m \leq 10^6$，$1 \leq u_i, v_i\leq N$，$0 \leq w_i \leq 10 ^ 9$。
输出描述
输出仅一行，共 $N$ 个数，分别表示从皇宫到编号为 $1\sim N$ 建筑的最短距离，两两之间用空格隔开。（如果无法到达则输出 $-1$）
输入输出样例
示例 1
输入
1 | |
输出
1 | |
运行限制
| 语言 | 最大运行时间 | 最大运行内存 |
|---|---|---|
| C++ | 2s | 512M |
| C | 2s | 512M |
| Python3 | 2s | 512M |
| Java | 2s | 512M |
随机数据下的最短路问题
题目描述
给定 $N$ 个点和 $M$ 条单向道路，每条道路都连接着两个点，每个点都有自己编号，分别为 $1\sim N$ 。
问你从 $S$ 点出发，到达每个点的最短路径为多少。
输入描述
输入第一行包含三个正整数 $N,M,S$。
第 $2$ 到 $M + 1$ 行每行包含三个正整数 $u,v,w$，表示 $u\rightarrow v$ 之间存在一条距离为 $w$ 的路。
$1\leq N \leq 5\times10^3$，$1 \leq M \leq 5\times 10^4$，$1 \leq u_i, v_i\leq N$，$0 \leq w_i \leq 10 ^ 9$。
本题数据随机生成。
输出描述
输出仅一行，共 $N$ 个数，分别表示从编号 $S$ 到编号为 $1\sim N$ 点的最短距离，两两之间用空格隔开。（如果无法到达则输出 $-1$）
输入输出样例
示例 1
输入
1 | |
输出
1 | |
运行限制
| 语言 | 最大运行时间 | 最大运行内存 |
|---|---|---|
| C++ | 1s | 128M |
| C | 1s | 128M |
| Python3 | 1s | 128M |
| Java | 1s | 128M |
出差
问题描述
$\mathrm{A}$ 国有 $N$ 个城市, 编号为 $1 \ldots N$ 。小明是编号为 1 的城市中一家公司的员 工, 今天突然接到了上级通知需要去编号为 $N$ 的城市出差。
由于疫情原因, 很多直达的交通方式暂时关闭, 小明无法乘坐飞机直接从 城市 1 到达城市 $N$, 需要通过其他城市进行陆路交通中转。小明通过交通信息 网, 查询到了 $M$ 条城市之间仍然还开通的路线信息以及每一条路线需要花费的 时间。
同样由于疫情原因, 小明到达一个城市后需要隔离观察一段时间才能离开 该城市前往其他城市。通过网络, 小明也查询到了各个城市的隔离信息。(由于 小明之前在城市 1 , 因此可以直接离开城市 1 , 不需要隔离）
由于上级要求, 小明希望能够尽快赶到城市 $\mathrm{N}$, 因此他求助于你, 希望你 能帮他规划一条路线, 能够在最短时间内到达城市 $N$ 。
输入格式
第 1 行: 两个正整数 $N, M, N$ 表示 A 国的城市数量, $M$ 表示末关闭的路 线数量
第 2 行: $N$ 个正整数, 第 $i$ 个整数 $C_{i}$ 表示到达编号为 $\mathrm{i}$ 的城市后需要隔离 的时间
第 $3 \ldots M+2$ 行: 每行 3 个正整数, $u, v, c$, 表示有一条城市 $u$ 到城市 $v$ 的 双向路线仍然开通着, 通过该路线的时间为 $c$
输出格式
第 1 行: 1 个正整数, 表示小明从城市 1 出发到达城市 $N$ 的最短时间（到 达城市 $N$, 不需要计算城市 $N$ 的隔离时间）
样例输入
1 | |
样例输出
1 | |
样例说明
评测用例规模与约定
对于 $100 %$ 的数据, $1 \leq N \leq 1000,1 \leq M \leq 10000,1 \leq C_{i} \leq 200,1 \leq u, v \leq$ $N, 1 \leq c \leq 1000$
运行限制
| 语言 | 最大运行时间 | 最大运行内存 |
|---|---|---|
| C++ | 1s | 512M |
| C | 1s | 512M |
| Python3 | 1s | 512M |
| Java | 1s | 512M |
聪明的猴子
题目描述
在一个热带雨林中生存着一群猴子，它们以树上的果子为生。昨天下了一场大雨，现在雨过天晴，但整个雨林的地表还是被大水淹没着，部分植物的树冠露在水面上。猴子不会游泳，但跳跃能力比较强，它们仍然可以在露出水面的不同树冠上来回穿梭，以找到喜欢吃的果实。
现在，在这个地区露出水面的有 $N$ 棵树，假设每棵树本身的直径都很小，可以忽略不计。我们在这块区域上建立直角坐标系，则每一棵树的位置由其所对应的坐标表示(任意两棵树的坐标都不相同)。
在这个地区住着的猴子有 $M$ 个，下雨时，它们都躲到了茂密高大的树冠中，没有被大水冲走。由于各个猴子的年龄不同、身体素质不同，它们跳跃的能力不同。有的猴子跳跃的距离比较远(当然也可以跳到较近的树上)，而有些猴子跳跃的距离就比较近。这些猴子非常聪明，它们通过目测就可以准确地判断出自己能否跳到对面的树上。
现已知猴子的数量及每一个猴子的最大跳跃距离，还知道露出水面的每一棵树的坐标，你的任务是统计有多少个猴子可以在这个地区露出水面的所有树冠上觅食。
输入描述
第 $1$ 行为一个整数，表示猴子的个数 $M(2 \leq M \leq 500)$；
第 $2$ 行为 $M$ 个整数，依次表示猴子的最大跳跃距离（每个整数值在 $1 \sim 1000$之间）；
第 $3$ 行为一个整数表示树的总棵数 $N(2 \leq N \leq 1000)$；
第 $4$ 行至第 $N+3$ 行为 $N$ 棵树的坐标（横纵坐标均为整数，范围为：$-1000 \sim 1000$）。
（同一行的整数间用空格分开）
输出描述
输出一个整数，表示可以在这个地区的所有树冠上觅食的猴子数。
输入输出样例
示例 1
输入
1 | |
输出
1 | |
运行限制
| 语言 | 最大运行时间 | 最大运行内存 |
|---|---|---|
| C++ | 1s | 128M |
| C | 1s | 128M |
| Python3 | 1s | 128M |
| Java | 1s | 128M |
通电
题目描述
2015 年，全中国实现了户户通电。作为一名电力建设者，小明正在帮助一带一路上的国家通电。
这一次，小明要帮助 $n$ 个村庄通电，其中 1 号村庄正好可以建立一个发电站，所发的电足够所有村庄使用。
现在，这 $n$ 个村庄之间都没有电线相连，小明主要要做的是架设电线连接这些村庄，使得所有村庄都直接或间接的与发电站相通。
小明测量了所有村庄的位置（坐标）和高度，如果要连接两个村庄，小明需要花费两个村庄之间的坐标距离加上高度差的平方，形式化描述为坐标为($x_1, y_1$) 高度为 $h_1$ 的村庄与坐标为 ($x_2, y_2$) 高度为 $h_2$ 的村庄之间连接的费用为
$\sqrt{(x_1-x_2)^2+(y_1-y_2)^2}+(h_1-h_2)^2$
高度的计算方式与横纵坐标的计算方式不同。
由于经费有限，请帮助小明计算他至少要花费多少费用才能使这 $n$ 个村庄都通电。
输入描述
输入的第一行包含一个整数 $n$ ，表示村庄的数量。
接下来 $n$ 行，每个三个整数 $x, y,h$，分别表示一个村庄的横、纵坐标和高度，其中第一个村庄可以建立发电站。
其中，$1 \leq n \leq 1000，0 \leq x, y, h \leq 10000$。
输出描述
输出一行，包含一个实数，四舍五入保留 2 位小数，表示答案。
输入输出样例
示例
输入
1 | |
输出
1 | |
运行限制
| 语言 | 最大运行时间 | 最大运行内存 |
|---|---|---|
| C++ | 1s | 256M |
| C | 1s | 256M |
| Python3 | 1s | 256M |
| Java | 1s | 256M |
机房
问题描述
这天, 小明在机房学习。
他发现机房里一共有 $n$ 台电脑, 编号为 1 到 $n$, 电脑和电脑之间有网线连 接, 一共有 $n-1$ 根网线将 $n$ 台电脑连接起来使得任意两台电脑都直接或者间 接地相连。
小明发现每台电脑转发、发送或者接受信息需要的时间取决于这台电脑和 多少台电脑直接相连, 而信息在网线中的传播时间可以忽略。比如如果某台电脑 用网线直接连接了另外 $d$ 台电脑, 那么任何经过这台电脑的信息都会延迟 $d$ 单 位时间 (发送方和接收方也会产生这样的延迟, 当然如果发送方和接收方都是 同一台电脑就只会产生一次延迟)。
小明一共产生了 $m$ 个疑问: 如果电脑 $u_{i}$ 向电脑 $v_{i}$ 发送信息, 那么信息从 $u_{i}$ 传到 $v_{i}$ 的最短时间是多少?
输入格式
输入共 $n+m$ 行, 第一行为两个正整数 $n, m$ 。
后面 $n-1$ 行, 每行两个正整数 $x, y$ 表示编号为 $x$ 和 $y$ 的两台电脑用网线 直接相连。
后面 $m$ 行, 每行两个正整数 $u_{i}, v_{i}$ 表示小明的第 $i$ 个疑问。
输出格式
输出共 $m$ 行, 第 $i$ 行一个正整数表示小明第 $i$ 个疑问的答案。
样例输入
1 | |
样例输出
1 | |
样例说明
这四台电脑各自的延迟分别为 $2,2,1,1$ 。
对于第一个询问, 从 2 到 3 需要经过 $2,1,3$, 所以时间和为 $2+2+1=5$ 。
对于第二个询问, 从 3 到 4 需要经过 $3,1,2,4$, 所以时间和为 $1+2+2+1=6$。
对于第三个询问, 从 3 到 3 只会产生一次延迟, 所以时间为 1 。
评测用例规模与约定
对于 $30 %$ 的数据, 保证 $n, m \leq 1000$;
对于 $100 %$ 的数据, 保证 $n, m \leq 100000$ 。
运行限制
| 语言 | 最大运行时间 | 最大运行内存 |
|---|---|---|
| C++ | 1s | 512M |
| C | 1s | 512M |
| Python3 | 1s | 512M |
| Java | 1s | 512M |
环境治理
问题描述
LQ 国拥有 $n$ 个城市, 从 0 到 $n-1$ 编号, 这 $n$ 个城市两两之间都有且仅有 一条双向道路连接, 这意味着任意两个城市之间都是可达的。每条道路都有一 个属性 $D$, 表示这条道路的灰尘度。当从一个城市 $A$ 前往另一个城市 $B$ 时, 可 能存在多条路线, 每条路线的灰尘度定义为这条路线所经过的所有道路的灰尘 度之和, LQ 国的人都很讨厌灰尘, 所以他们总会优先选择灰尘度最小的路线。
LQ 国很看重居民的出行环境, 他们用一个指标 $P$ 来衡量 LQ 国的出行环 境, $P$ 定义为:
$P=\sum_{i=0}^{n-1} \sum_{j=0}^{n-1} d(i, j)$
其中 $d(i, j)$ 表示城市 $i$ 到城市 $j$ 之间灰尘度最小的路线对应的灰尘度的值。 为了改善出行环境, 每个城市都要有所作为, 当某个城市进行道路改善时, 会将与这个城市直接相连的所有道路的灰尘度都减少 1 , 但每条道路都有一个 灰尘度的下限值 $L$, 当灰尘度达到道路的下限值时, 无论再怎么改善, 道路的 灰尘度也不会再减小了。
具体的计划是这样的:
第 1 天, 0 号城市对与其直接相连的道路环境进行改善;
第 2 天, 1 号城市对与其直接相连的道路环境进行改善;
$\cdots$
第 $n$ 天, $n-1$ 号城市对与其直接相连的道路环境进行改善;
第 $n+1$ 天, 0 号城市对与其直接相连的道路环境进行改善;
第 $n+2$ 天, 1 号城市对与其直接相连的道路环境进行改善;
LQ 国想要使得 $P$ 指标满足 $P \leq Q$ 。请问最少要经过多少天之后, $P$ 指标 可以满足 $P \leq Q$ 。如果在初始时就已经满足条件, 则输出 0 ; 如果永远不可能 满足, 则输出 $-1$ 。
输入格式
输入的第一行包含两个整数 $n, Q$, 用一个空格分隔, 分别表示城市个数和 期望达到的 $P$ 指标。
接下来 $n$ 行, 每行包含 $n$ 个整数, 相邻两个整数之间用一个空格分隔, 其 中第 $i$ 行第 $j$ 列的值 $D_{i j}\left(D_{i j}=D_{j i}, D_{i i}=0\right)$ 表示城市 $i$ 与城市 $j$ 之间直接相连 的那条道路的灰尘度。
接下来 $n$ 行, 每行包含 $n$ 个整数, 相邻两个整数之间用一个空格分隔, 其 中第 $i$ 行第 $j$ 列的值 $L_{i j}\left(L_{i j}=L_{j i}, L_{i i}=0\right)$ 表示城市 $i$ 与城市 $j$ 之间直接相连的 那条道路的灰尘度的下限值。
输出格式
输出一行包含一个整数表示答条。
样例输入
1 | |
样例输出
1 | |
评测用例规模与约定
对于 $30 %$ 的评测用例, $1 \leq n \leq 10 ， 0 \leq L_{i j} \leq D_{i j} \leq 10$ ；
对于 $60 %$ 的评测用例, $1 \leq n \leq 50 ， 0 \leq L_{i j} \leq D_{i j} \leq 100000$;
对于所有评测用例, $1 \leq n \leq 100,0 \leq L_{i j} \leq D_{i j} \leq 100000,0 \leq Q \leq 2^{31}-1$ 。
运行限制
| 语言 | 最大运行时间 | 最大运行内存 |
|---|---|---|
| C++ | 10s | 512M |
| C | 10s | 512M |
| Python3 | 10s | 512M |
| Java | 10s | 512M |
刷题统计
问题描述
小明决定从下周一开始努力刷题准备蓝桥杯竞赛。他计划周一至周五每天 做 $a$ 道题目, 周六和周日每天做 $b$ 道题目。请你帮小明计算, 按照计划他将在 第几天实现做题数大于等于 $n$ 题?
输入格式
输入一行包含三个整数 $a, b$ 和 $n$.
输出格式
输出一个整数代表天数。
样例输入
1 | |
样例输出
1 | |
评测用例规模与约定
对于 $50 %$ 的评测用例, $1 \leq a, b, n \leq 10^{6}$.
对于 $100 %$ 的评测用例, $1 \leq a, b, n \leq 10^{18}$.
运行限制
| 语言 | 最大运行时间 | 最大运行内存 |
|---|---|---|
| C++ | 1s | 256M |
| C | 1s | 256M |
| Python3 | 1s | 256M |
| Java | 1s | 256M |
快速幂
题目描述
输入 $b，p，k$ 的值，求 $b^p \mod k$ 的值。其中 $2 \leq b,p,k \leq 10^9$ 。
输入描述
三个整数 $b,p,k$。
输出描述
输出 $b^p \mod k=s$，$s$ 为运算结果。
输入输出样例
示例
输入
1 | |
输出
1 | |
运行限制
| 语言 | 最大运行时间 | 最大运行内存 |
|---|---|---|
| C++ | 1s | 128M |
| C | 1s | 128M |
| Python3 | 1s | 128M |
| Java | 1s | 128M |
核桃的数量
题目描述
小张是软件项目经理，他带领 3 个开发组。工期紧，今天都在加班呢。为鼓舞士气，小张打算给每个组发一袋核桃（据传言能补脑）。他的要求是：
各组的核桃数量必须相同
各组内必须能平分核桃（当然是不能打碎的）
尽量提供满足 1,2 条件的最小数量（节约闹革命嘛）
输入描述
输入一行 $a,b,c$，都是正整数，表示每个组正在加班的人数，用空格分开$(a,b,c<30)$。
输出描述
输出一个正整数，表示每袋核桃的数量。
输入输出样例
示例
输入
1 | |
输出
1 | |
运行限制
| 语言 | 最大运行时间 | 最大运行内存 |
|---|---|---|
| C++ | 1s | 64M |
| C | 1s | 64M |
| Python3 | 1s | 64M |
| Java | 1s | 64M |
质数
题目描述
给定一个正整数 $N$，请你输出 $N$ 以内（不包含 $N$）的质数以及质数的个数。
输入描述
输入一行，包含一个正整数 $N$。 $1\leq N \leq 10^3$
输出描述
共两行。
第 $1$ 行包含若干个素数，每两个素数之间用一个空格隔开，素数从小到大输出。
第 $2$ 行包含一个整数，表示N以内质数的个数。
输入输出样例
示例
输入
1 | |
输出
1 | |
运行限制
| 语言 | 最大运行时间 | 最大运行内存 |
|---|---|---|
| C++ | 1s | 128M |
| C | 1s | 128M |
| Python3 | 1s | 128M |
| Java | 1s | 128M |
分割立方体
题目描述
给定一个立方体，边长为 $n$，现将其分割成 $n×n×n$ 个单位立方体。
分割后任意两个单位立方体，或者有 $2$ 个公共点，或者有 $4$ 个公共点，或者没有公共点。
请问，没有公共点和有 $2$ 个公共点的立方体，共有多少对？
输入描述
输入一行包含一个整数 $n(1\leq n \leq 30)$。
输出描述
输出一个整数表示答案。
输入输出样例
示例1
输入
1 | |
输出
1 | |
示例2
输入
1 | |
输出
1 | |
示例3
输入
1 | |
输出
1 | |
运行限制
| 语言 | 最大运行时间 | 最大运行内存 |
|---|---|---|
| C++ | 1s | 256M |
| C | 1s | 256M |
| Python3 | 1s | 256M |
| Java | 1s | 256M |
糊涂人寄信
题目描述
有一个糊涂人，写了 $n$ 封信和 $n$ 个信封，到了邮寄的时候，把所有的信都装错了信封。求装错信封可能的种类数。
输入描述
有多行读入，每行输入一个正整数 $n$，表示一种情况。($n\leq 20$)
输出描述
输出相应的答案。
输入输出样例
示例
输入
1 | |
输出
1 | |
运行限制
| 语言 | 最大运行时间 | 最大运行内存 |
|---|---|---|
| C++ | 1s | 256M |
| C | 1s | 256M |
| Python3 | 1s | 256M |
| Java | 1s | 256M |
小蓝吃糖果
题目描述
小蓝有 $n$ 种糖果，每种数量已知。
小蓝不喜欢连续 $2$ 次吃同样的糖果。问有没有可行的吃糖方案。
输入描述
第一行是整数 $n(0<n<1000000)$。
第二行包含 $n$ 个数，表示 $n$ 种糖果的数量 $mi$，$0<mi<1000000$。
输出描述
输出一行，包含一个 Yes 或 No。
输入输出样例
示例
输入
1 | |
输出
1 | |
运行限制
| 语言 | 最大运行时间 | 最大运行内存 |
|---|---|---|
| C++ | 1s | 256M |
| C | 1s | 256M |
| Python3 | 1s | 256M |
| Java | 1s | 256M |