蓝桥杯国赛试题解析
Last Update:
第十四届Python大学C组
跑步计划
问题描述
小蓝计划在某天的日期中出现 $1$ 时跑 $5$ 千米,否则只跑 $1$ 千米。注意日期中出现 $1$ 不仅指年月日也指星期。
请问按照小蓝的计划,$2023$ 年小蓝总共会跑步锻炼多少千米?例如,$5$ 月 $1$ 日、$1$ 月 $13$ 日、$11$ 月 $5$ 日、$4$ 月 $3$ 日 (星期一) 小蓝会跑 $5$ 千米,而 $5$ 月 $23$ 日小蓝会跑 $1$ 千米 (示例日期均为 $2023$ 年)
答案提交
这是一道结果填空的题,你只需要算出结果后提交即可。本题的结果为一个整数,在提交答案时只填写这个整数,填写多余的内容将无法得分。
运行限制
语言 | 最大运行时间 | 最大运行内存 |
---|---|---|
C++ | 1s | 256M |
C | 1s | 256M |
Java | 2s | 256M |
Python3 | 3s | 256M |
PyPy3 | 3s | 256M |
Go | 3s | 256M |
JavaScript | 3s | 256M |
总通过次数: 714 | 总提交次数: 778 | 通过率: 91.8%
难度: 中等 标签: 2023, 国赛, 日期问题
版权声明
部分题目由用户贡献,若您是著作权持有人,请与我们联系。
解题思路
1 |
|
1 |
|
混乘数字
问题描述
混乘数字的定义如下: 对于一个正整数 $n$,如果存在正整数 $a, b$,使得 $n = a \times b$,而且 $a$ 和 $b$ 的十进制数位中每个数字出现的次数之和与 $n$ 中对应数字出现次数相同,则称 $n$ 为混乘数字。
例如,对于正整数 $n = 126$,存在 $a = 6$, $b = 21$ 满足条件,因此 $126$ 是一个混乘数字。
又如,对于正整数 $n = 180225$,存在 $a = 225$, $b = 801$ 满足条件,因此 $180225$ 是一个混乘数字。
请你帮助计算出,$1 \sim 1000000$ (含)之间一共有多少个数字是混乘数字。
答案提交
这是一道结果填空的题,你只需要算出结果后提交即可。本题的结果为一个整数,在提交答案时只填写这个整数,填写多余的内容将无法得分。
运行限制
语言 | 最大运行时间 | 最大运行内存 |
---|---|---|
C++ | 1s | 256M |
C | 1s | 256M |
Java | 2s | 256M |
Python3 | 5s | 256M |
PyPy3 | 5s | 256M |
Go | 5s | 256M |
JavaScript | 5s | 256M |
解题思路
1 |
|
1 |
|
整数变换
问题描述
小蓝有一个整数 $n$。每分钟,小蓝的数都会发生变化,变为上一分钟的数减去上一分钟的数的各个数位和。
例如,如果小蓝开始时的数为 $23$,则下一分钟变为 $23 − (2 + 3) = 18$,再下一分钟变为 $18 − (1 + 8) = 9$,再下一分钟变为 $9 − 9 = 0$,共经过了 $3$ 分钟变为 $0$。
给定一个正整数,请问这个数多少分钟后变为 $0$。
输入格式
输入一行包含一个整数 $n$。
输出格式
输出一个整数,表示答案。
样例输入
1 |
|
样例输出
1 |
|
评测用例规模与约定
对于 $30%$ 的评测用例,$1 ≤ n ≤ 1000$;
对于 $60%$ 的评测用例,$1 ≤ n ≤ 10^6$;
对于所有评测用例,$1 ≤ n ≤ 10^9$。
运行限制
语言 | 最大运行时间 | 最大运行内存 |
---|---|---|
C++ | 1s | 256M |
C | 1s | 256M |
Java | 2s | 256M |
Python3 | 3s | 256M |
PyPy3 | 3s | 256M |
Go | 3s | 256M |
JavaScript | 3s | 256M |
解题思路
这道题目需要使用pypy3,否则会超时
1 |
|
定时任务
问题描述
Cron 表达式在定时任务中经常被使用,在这里我们用了一种简化后的版本 SimpleCron 表达式:SimpleCron 表达式是一个具有时间含义的字符串,字符串以 $4$ 个空格隔开,分为 $5$ 个域,格式为 $X X X X X$,其中 $X$ 是一个域的占位符。$5$ 个域从左至右依次为秒 $(0 - 59)$、分钟 $(0 - 59)$、小时 $(0 - 23)$、日期 $(1 - 31)$、月份 $(1 - 12)$,其中括号内为他们各自的取值范围。同时域内取值也可以使用一些特殊字符(每个域内只能使用一种特殊字符):
- 特殊字符 $*$ (ASCII 码为 $42$)表示所有可能的值。例如:在分钟域内表示每一分钟;在日期域内表示月内的每一天。
- 特殊字符 $,$ (ASCII 码为 $44$)表示列出枚举值。例如:在秒域内,$3,20$ 表示分别在 $3$ 秒和 $20$ 秒执行一次任务。
- 特殊字符 $-$ (ASCII 码为 $45$)表示范围,可以视为连续的若干个枚举值。例如:$1-5$ 等价于 $1,2,3,4,5$。
例如,$4 2 1,3,15 1-31 *$ 表示的含义是每个月份中的每一天中的 $01:02:04$、$03:02:04$、$15:02:04$ 这三个时刻各执行一次,在 $2023$ 年一共会执行 $1095$ 次。
现在给出你一个合法的 SimpleCron 表达式,其中用到的所有数字均没有前导零。请问在 $2023$ 一整年当中,使用了这个表达式的定时任务总计会执行多少次?
输入格式
输入一行,包含一个 SimpleCron 字符串。
输出格式
输出一行,包含一个整数表示答案。
样例输入
4 2 1,3,15 1-31 *
样例输出
1095
评测用例规模与约定
对于所有评测用例,$0 ≤$ 秒域的取值 $≤ 59$,$0 ≤$ 分钟域的取值 $≤ 59$,$0 ≤$ 小时域的取值 $≤ 23$,$1 ≤$ 日期域的取值 $≤ 31$,$1 ≤$ 月份域的取值 $≤ 12$。
运行限制
语言 | 最大运行时间 | 最大运行内存 |
---|---|---|
C++ | 1s | 256M |
C | 1s | 256M |
Java | 2s | 256M |
Python3 | 3s | 256M |
PyPy3 | 3s | 256M |
Go | 3s | 256M |
JavaScript | 3s | 256M |
总通过次数: 181 | 总提交次数: 251 | 通过率: 72.1%
难度: 中等 标签: 2023, 国赛, 日期问题
版权声明
部分题目由用户贡献,若您是著作权持有人,请与我们联系。
解题思路
1 |
|
2023
问题描述
给定 $n$, $m$,请求出所有 $n$ 位十进制整数中有多少个数中恰好出现了 $m$ 个 $2023$。
例如 $00202312023$ 是一个 $11$ 位的出现了 $2$ 个 $2023$ 的十进制整数。由于结果可能很大,请输出答案对 $998244353$ 取模的结果。
输入格式
输入一行包含两个整数 $n$, $m$,用一个空格分隔。
输出格式
输出一行包含一个整数表示答案。
样例输入
5 1
样例输出
1 |
|
评测用例规模与约定
对于 $40%$ 的评测用例,$n ≤ 10^5$,$m ≤ 10$;
对于所有评测用例,$4 ≤ n ≤ 10^5$,$0 ≤ 4m ≤ n$。
运行限制
语言 | 最大运行时间 | 最大运行内存 |
---|---|---|
C++ | 1s | 256M |
C | 1s | 256M |
Java | 2s | 256M |
Python3 | 3s | 256M |
PyPy3 | 3s | 256M |
Go | 3s | 256M |
JavaScript | 3s | 256M |
总通过次数: 34 | 总提交次数: 232 | 通过率: 14.7%
难度: 中等 标签: 2023, 国赛, 排列组合, 二项式定理
版权声明
部分题目由用户贡献,若您是著作权持有人,请与我们联系。
解题思路
1 |
|
最大算式
问题描述
给定 $n$ 个非负整数 $A_i$ ,你可以在不改变这些数顺序的前提下任意在他们之间插入 $+,*,(,)$ 四种符号 。
请问在得到的算式合法的前提下,算式的结果最大可以是多少?
由于结果很大,你只需要输出答案对 $10^9+7$ 取模的结果即可。
输入描述
输入的第一行包含一个整数 $n$ 。
第二行包含 $n$ 个整数,分别表示 $A_1, A_2, \cdots, A_n$ ,相邻两个整数之间使用一个空格分隔。
输出描述
输出一行包含一个整数表示答案。
样例输入
1 |
|
样例输出
1 |
|
样例说明
$(1+2)\times(1+1+1)\times(2+1)=27$ .
评测用例规模
对于 $40%$ 的评测用例, $n \leq 5000$ ;
对于所有评测用例, $1 \leq n \leq 10^5$ , $0 \leq A_i \leq 10^9$ 。
运行限制
语言 | 最大运行时间 | 最大运行内存 |
---|---|---|
C++ | 1s | 256M |
C | 1s | 256M |
Java | 2s | 256M |
Python3 | 3s | 256M |
PyPy3 | 3s | 256M |
Go | 3s | 256M |
JavaScript | 3s | 256M |
总通过次数: 22 | 总提交次数: 38 | 通过率: 57.9%
难度: 中等 标签: 2023, 贪心, 国赛, 数学
版权声明
部分题目由用户贡献,若您是著作权持有人,请与我们联系。
解题思路
1 |
|
躲炮弹
问题描述
小蓝正在玩一个躲炮弹的游戏。游戏中有一个人物和一个炮塔,它们的初始距离为 $n$。
炮塔可能选择在区间 $[L, R]$ 上的任意一个整数 $x$,然后发射的炮弹会飞向小蓝操控的人物。但炮弹只会在飞出 $x$ 的倍数的距离($x, 2x, 3x, \ldots$)时落地,然后弹回到空中。如果小蓝操控的人物恰好站在了炮弹落地的位置,那么游戏就会结束。
小蓝只能在炮弹发射前移动他的人物,每移动一步,可以使得人物和炮塔的距离增加 $1$ 或者减少 $1$。他想知道最少要移动多少步才能保证自己的人物一定能躲过炮弹。
输入格式
输入一行包含三个整数 $n, L, R$,相邻的整数之间使用一个空格分隔。
输出格式
输出一行包含一个整数,表示小蓝操纵的人物最少需要移动的步数。
样例输入
10 2 13
样例输出
1 |
|
评测用例规模与约定
对于 $40%$ 的评测用例,$n, L, R \leq 10^6$;
对于所有评测用例,$1 \leq n, L, R \leq 10^9$,$2 \leq L \leq R$。
运行限制
语言 | 最大运行时间 | 最大运行内存 |
---|---|---|
C++ | 1s | 256M |
C | 1s | 256M |
Java | 2s | 256M |
Python3 | 3s | 256M |
PyPy3 | 3s | 256M |
Go | 3s | 256M |
JavaScript | 3s | 256M |
总通过次数: 38 | 总提交次数: 94 | 通过率: 40.4%
难度: 中等 标签: 2023, 国赛, 质因子分解
版权声明
部分题目由用户贡献,若您是著作权持有人,请与我们联系。
解题思路
1 |
|
走方格
问题描述
给定一个 $N$ 行 $N$ 列的方格,第 $i$ 行第 $j$ 列的方格坐标为 $(i, j)$,高度为 $H_{i, j}$。小蓝从左上角坐标 $(0, 0)$ 出发,目的地是右下角坐标 $(N - 1, N - 1)$。
当小蓝位于第 $r$ 行第 $c$ 列时,他有如下的移动方式:
- 若 $r + 1 < N$,可以移动到 $(r + 1, c)$,花费 $1$ 秒;
- 若 $c + 1 < N$,可以移动到 $(r, c + 1)$,花费 $1$ 秒;
- 对于任意整数 $L$,若 $H_{r,c} > H_{r,c+1} > \dots > H_{r,c+L}$,可以移动到 $(r, c + L)$,花费 $1$ 秒;
- 对于任意整数 $L$,若 $H_{r,c} > H_{r,c-1} > \dots > H_{r,c-L}$,可以移动到 $(r, c - L)$,花费 $1$ 秒。
现在给出方格,请问小蓝从 $(0, 0)$ 移动到 $(N - 1, N - 1)$ 最少需要多少秒?
输入格式
输入的第一行包含一个整数 $N$ 表示方格大小。
接下来 $N$ 行,每行包含 $N$ 个整数,表示每个方格上的数字。
输出格式
输出一个整数表示答案。
样例输入
4
0 1 9 3
2 9 3 7
8 4 8 9
9 8 0 7
样例输出
1 |
|
样例说明
移动顺序为: $(0,0) \rightarrow (1,0) \rightarrow (2,0) \rightarrow (3,0) \rightarrow (3,2) \rightarrow (3,3)$,其中坐标 $(3,0)$、$(3,1)$、$(3,2)$ 处的数字分别为 $9 > 8 > 0$,所以可以花费 $1$ 秒从 $(3,0)$ 移动到 $(3, 2)$。
评测用例规模与约定
对于 $20%$ 的评测用例,$1 \leq N \leq 10$;
对于 $50%$ 的评测用例,$1 \leq N \leq 100$;
对于所有评测用例,$1 \leq N \leq 1000$,$0 \leq H_{i,j} \leq 100$。
运行限制
语言 | 最大运行时间 | 最大运行内存 |
---|---|---|
C++ | 1s | 256M |
C | 1s | 256M |
Java | 3s | 256M |
Python3 | 5s | 256M |
PyPy3 | 5s | 256M |
Go | 5s | 256M |
JavaScript | 5s | 256M |
解题思路
1 |
|
1 |
|
等腰三角形
问题描述
给定一个包含 $n$ 个数的序列 $A_i$ ,每次操作可以选择其中任意一个数将其 $+1$ 或 $-1$ 。
我们要让这个序列满足能够从中任选三个数,这三个数对应长度的三条边总能组成一个等腰三角形。问最少需要多少次操作才能让序列满足条件。
输入描述
输入的第一行包含一个整数 $n$ 。
第二行包含 $n$ 个整数,分别表示 $A_1, A_2, \cdots, A_n$ ,相邻两个整数之间使用一个空格分隔。
输出描述
输出一行包含一个整数,表示最少的操作次数。
样例输入
1 |
|
样例输出
1 |
|
样例说明
将原序列修改为 $4,4,4,7,7$ 即可。
评测用例规模
对于 $40%$ 的评测用例, $n \leq 5000$ , $A_i \leq 5000$ ;
对于 $70%$ 的评测用例, $n \leq 2\times 10^5$ , $A_i \leq 10^6$ ;
对于所有评测用例, $1 \leq n \leq 2\times 10^5$ , $1 \leq A_i \leq 10^9$ 。w
运行限制
语言 | 最大运行时间 | 最大运行内存 |
---|---|---|
C++ | 1s | 256M |
C | 1s | 256M |
Java | 2s | 256M |
Python3 | 3s | 256M |
PyPy3 | 3s | 256M |
Go | 3s | 256M |
JavaScript | 3s | 256M |
总通过次数: 7 | 总提交次数: 69 | 通过率: 10.1%
难度: 中等 标签: 2023, 国赛, 数学, 分类讨论
版权声明
部分题目由用户贡献,若您是著作权持有人,请与我们联系。
单词分类
问题描述
在遥远的 $\text{LQ}$ 国,只存在三种字符:$\text{l、q }$和 $\text{b}$ (ASCII 码分别为 $108、113、98$),所有的单词都由这三种字符组合而来。小蓝为了更加快速的记忆单词,决定将词典上所有的单词按照单词前缀将其分为 $K$ 类,具体的要求是:
- 选出 $K$ 个不同的单词前缀作为 $K$ 类;
- 对于字典上的每个单词,只能属于 $K$ 类中的某一个类,不能同时属于多个类;
- 对于 $K$ 类中的每个类,至少包含有一个单词。
现在已知字典上一共有 $N$ 个单词,小蓝想要知道将这 $N$ 个单词按照上述要求分为 $K$ 类,一共有多少种不同的方案。两个方案不同指的是两个方案各自选出的 $K$ 个单词前缀不完全相同。答案可能过大,所以你需要将答案对 $1000000007$ (即 $10^9 + 7$)取模后输出。
输入格式
输入的第一行包含两个整数 $N$ 和 $K$;
接下来 $N$ 行,每行包含一个单词,由 $\text{l、q、b}$ 三种字符组成。
输出格式
输出一个整数表示答案。答案可能很大,请输出答案对 $1000000007$ 取模的值。
样例输入
4 2
lqb
lql
qqq
qql
样例输出
1 |
|
样例说明
方案 1:$\text{l=lqb,lql、q=qqq,qql}$; 方案 2:$\text{lq=lqb,lql、q=qqq,qql}$; 方案 3:$\text{l=lqb,lql、qq=qqq,qql}$; 方案 4:$\text{lq=lqb,lql、qq=qqq,qql}$。
以方案 1 为例,他表示选出的两类对应的前缀分别是 $\text{l}$ 和 $text{q}$,属于前缀 $\text{l}$ 的单词有 $\text{lqb、lql}$,属于前缀 $\text{q}$ 的单词有 $\text{qqq、qql}$,方案 1 将四个单词按照前缀分成了两类,且每类至少包含一个单词,每个单词仅属于一类,所以方案 1 满足题意。
评测用例规模与约定
对于 $30%$ 的评测用例,$1 \leq N \leq 10$,$1 \leq K \leq 5$;
对于 $50%$ 的评测用例,$1 \leq N \leq 50$,$1 \leq K \leq 10$;
对于所有评测用例,$1 \leq N \leq 200$,$1 \leq K \leq 100$,$1 \leq$ 单词长度 $\leq 10$。
运行限制
语言 | 最大运行时间 | 最大运行内存 |
---|---|---|
C++ | 1s | 256M |
C | 1s | 256M |
Java | 2s | 256M |
Python3 | 3s | 256M |
PyPy3 | 3s | 256M |
Go | 3s | 256M |
JavaScript | 3s | 256M |
总通过次数: 9 | 总提交次数: 28 | 通过率: 32.1%
难度: 中等 标签: 2023, 字典树, 国赛, 动态规划
版权声明
部分题目由用户贡献,若您是著作权持有人,请与我们联系。
第十四届Python大学B组
弹珠堆放
题解
(89)
问题描述
小蓝有 20230610 颗磁力弹珠,他对金字塔形状尤其感兴趣,如下图所示:
高度为 $1$ 的金字塔需要 $1$ 颗弹珠;
高度为 $2$ 的金字塔需要 $4$ 颗弹珠;
高度为 $3$ 的金字塔需要 $10$ 颗弹珠;
高度为 $4$ 的金字塔需要 $20$ 颗弹珠。
小蓝想要知道用他手里的弹珠可以摆出的最高的金字塔的高度是多少?
答案提交
这是一道结果填空的题,你只需要算出结果后提交即可。本题的结果为一个整数,在提交答案时只填写这个整数,填写多余的内容将无法得分。
运行限制
语言 | 最大运行时间 | 最大运行内存 |
---|---|---|
C++ | 1s | 256M |
C | 1s | 256M |
Java | 2s | 256M |
Python3 | 3s | 256M |
PyPy3 | 3s | 256M |
Go | 3s | 256M |
JavaScript | 3s | 256M |
总通过次数: 723 | 总提交次数: 767 | 通过率: 94.3%
难度: 中等 标签: 2023, 前缀和, 国赛
版权声明
部分题目由用户贡献,若您是著作权持有人,请与我们联系。
解题思路
1 |
|
划分
问题描述
给定 $40$ 个数,请将其任意划分成两组,每组至少一个元素。每组的权值为组内所有元素的和。划分的权值为两组权值的乘积。请问对于以下 $40$ 个数,划分的权值最大为多少。
1 |
|
在试题包中有一个名为 \verb|nums.txt| 的文本文件,文件中的数与题面上的数相同。
答案提交
这是一道结果填空的题,你只需要算出结果后提交即可。本题的结果为一个整数,在提交答案时只填写这个整数,填写多余的内容将无法得分。
运行限制
语言 | 最大运行时间 | 最大运行内存 |
---|---|---|
C++ | 1s | 256M |
C | 1s | 256M |
Java | 2s | 256M |
Python3 | 3s | 256M |
PyPy3 | 3s | 256M |
Go | 3s | 256M |
JavaScript | 3s | 256M |
总通过次数: 186 | 总提交次数: 248 | 通过率: 75%
难度: 中等 标签: 2023, 国赛, 动态规划, 背包问题
版权声明
部分题目由用户贡献,若您是著作权持有人,请与我们联系。
解题思路
1 |
|
偶串
问题描述
小蓝特别喜欢偶数,当他看到字符串时,他总数要检查一下是不是每种字符都是出现偶数次。给定一个字符串,请帮助小蓝检查一下该字符串是否满足要求。
输入描述
输入一行包含一个字符串,由小写英文字母组成。
输出描述
如果字符串中的每种字符都是出现偶数次,输出大写英文单词 $\verb|YES|$ ,否则输出大写英文单词 $\verb|NO|$ 。
样例输入
1 |
|
样例输出
1 |
|
样例输入
1 |
|
样例输出
1 |
|
评测用例规模
对于 $50%$ 的评测用例, $1\le$ 字符串长度 $\le 1000$;
对于所有评测用例,$1\le$ 字符串长度 $\le 10^6$ 。
运行限制
语言 | 最大运行时间 | 最大运行内存 |
---|---|---|
C++ | 1s | 256M |
C | 1s | 256M |
Java | 2s | 256M |
Python3 | 3s | 256M |
PyPy3 | 3s | 256M |
Go | 3s | 256M |
JavaScript | 3s | 256M |
总通过次数: 386 | 总提交次数: 429 | 通过率: 90%
难度: 中等 标签: 2023, 国赛, 语法
版权声明
部分题目由用户贡献,若您是著作权持有人,请与我们联系。
解题思路
常规思路
直接模拟直接求
1 |
|
使用异或
根据异或的性质我们可以知道:任意两个相同的数异或的值为0,故偶数个相同的数异或的值也是0
所以最后我们走一遍循环,最后异或值只要为0那说明所有数字出现的次数为偶数次,反之则存在一个数字出现了奇数次
最后由于异或只能在数字之间,所以我们用字符的ascii码(ord)来代表这个字符
1 |
|
交易账本
问题描述
小蓝最近研发了一种新的记账方式,并邀请了一些用户参加测试。交易账本可以看作是交易记录的集合,每条交易记录都有着一个独一无二的交易编号 $txId$ (编号大小反映了交易记录产生的时间顺序, $txId$ 小的交易记录先发生于 $txId$ 大的交易记录),每条交易记录包含一个或多个输入信息以及一个或多个输出信息。
其中输入来自于已经发生过的某比交易的某个输出,可以理解为这笔钱从某比交易输出后继续输入到了当前这比交易中,输入信息主要包含以下数据:$fromTxId$、$fromTxOutNumber$ ,这表示当前输入来自于交易编号为 $fromTxId$ 的第 $fromTxOutNumber$ $(fromTxOutNumber=0,1,2,\cdots )$ 个输出;输出信息主要包含以下数据:$account$、$val$ ,表示将 $val$ 数目的钱转移到了账户编号为 $account$ 的账户上。注意,当 $fromTxId$ 和 $fromTxOutNumber$ 都为 $-1$ 时,表明这是一笔特殊交易,由系统账户直接产生输出,特殊交易只含有一个输入和一个输出,可以认为系统账户拥有无限多数目的钱,特殊交易一定可以成功。
一个合法的账本应满足以下条件:1)对于每笔交易记录,所有的输入中涉及到的钱的总数目应和所有输出中钱的总数目相等;2)交易中的一个输出要么不使用,要使用的话输出中的钱应该全部分配给下一个输入,而不能分配给多个输入(特殊交易除外);3)交易按照顺序进行,不可以在某比交易中引用还未发生的交易。
现在已知一共有 $N$ 个不同的账户,初始时所有账户钱数目都为 $0$ ,账本上总计有 $M$ 条交易记录(按照交易完成的顺序进行记录),请你来判断下账本上的记录是否是合法的。
输入描述
输入的第一行包含一个整数 $T$ ,表示有 $T$ 组输入数据。
对于每组输入数据:
第一行包含两个整数 $N,M$ ,用一个空格分隔,分别表示账户的数目和账本的交易记录数目,其中账户编号为 $0,1,2,\cdots,N-1$ ,交易记录编号为 $0,1,2,\cdots ,M-1$ 。
接下来 $M$ 行,每行包含一条交易记录的信息,交易记录编号依次为 $0, 1, 2, \cdots, M-1$ 。第一个整数 $inCount$ 表示输入的个数,接下来包含 $inCount$ 个输入信息,每个输入信息包含 $fromTxId$ 和 $fromTxOutNumber$ 两个整数;接下来包含一个整数 $outCount$ 表示输出的个数,然后接着包含 $outCount$ 个输出信息,每个输出信息包含 $account$ 和 $val$ 两个整数。
输出描述
对于每组输入数据输出一行,如果账本记录合法则输出英文单词 $\verb|YES|$ ,否则输出英文单词 $\verb|NO|$。
样例输入
1 |
|
样例输出
1 |
|
样例说明
对于第一个数据:第一条交易 $(txId=0)$ 为特殊交易,给账户 $0$ 转入了 $100$;第二条交易 $(txId=1)$ 将上一条交易的唯一一个输出作为当前交易的输入,有两个输出,分别给账户 $1$ 和 $2$ 转入了 $50$ ;最后一条交易 $(txId=2)$ 将上一条交易的两个输出作为当前交易的输入,给账户 $2$ 转入了 $100$ 。
对于第二个数据,第三条交易中输入与输出总额不相等。
对于第三个数据,第一条交易中的输出被使用了超过一次。
对于第四个数据,第二条交易中引用了还未发生的交易的输出。
评测用例规模
对于所有评测用例, $1\le T\le 10$ , $1\le N\le 100$ , $1\le M\le 1000$ , $1\le inCount, outCount\le 100$ , $1\le$ 交易中涉及到钱的数目$\le 10000$ , $0\le account\le N-1$ , $0\le fromTxId\le M-1$ 。
运行限制
语言 | 最大运行时间 | 最大运行内存 |
---|---|---|
C++ | 1s | 256M |
C | 1s | 256M |
Java | 2s | 256M |
Python3 | 3s | 256M |
PyPy3 | 3s | 256M |
Go | 3s | 256M |
JavaScript | 3s | 256M |
解题思路
1 |
|
背包问题
问题描述
小蓝是一位狂热的积木爱好者,家里堆满了自己用积木组装的建筑模型。最近,有两款新出的积木组件上市,小蓝自然不会错过,他带上了自己的三个背包来到了积木商城,打算将尽可能多的积木组件带回家,每个背包都有一个固定的空间大小。小蓝只会购买这两种新出的积木组件 $A$ 和 $B$ , $A$ 和 $B$ 各自会占用背包的一部分空间,但对于同一种类型的积木占用的空间是相同的。小蓝想知道自己最多能带走多少数量的积木组件。
可以认为小蓝有足够的货币,只要背包可以装下的积木他都有能力购买。商场内的积木数量也是有限制的。
输入描述
输入的第一行包含一个整数 $T$ ,表示有 $T$ 组独立的询问。
每一组询问由三行组成。
每组询问的第一行包含三个整数 $B_1, B_2, B_3$ ,相邻的整数之间使用一个空格分隔,表示三个背包的空间大小。
每组询问的第二行包含两个整数 $cnt_A, cnt_B$ ,用一个空格分隔,分别表示商场内积木组件 $A$ 和 $B$ 的总量。
每组询问的第三行包含两个整数 $V_A, V_B$ ,用一个空格分隔,分别表示每个积木组件 $A$ 和 $B$ 所占用的空间大小。
输出描述
输出 $T$ 行,每行包含一个整数表示答案。
样例输入
1 |
|
样例输出
1 |
|
样例说明
对于第一组询问,第一个背包装一个 B 积木,无剩余空间;第二个背包装一个 B 积木,无剩余空间;第三个背包装一个 A 积木,剩余 2 空间,但积木已经没有了;最终答案是 $3$ ,可以带走所有的积木。
对于第二组询问,第一个背包和第三个背包各自装一个 B 组件,第二个背包装两个 B 组件和一个 A 组件,答案是 $5$ 。
对于第三组询问,第一个背包:1A+1B;第二个背包:8B;第三个背包:1A+1B。答案是 $12$ 。
评测用例规模
对于 $30%$ 的评测用例, $1\le cnt_A,cnt_B\le 100$ ;
对于所有评测用例, $1\le T\le 100$ , $1\le B_1,B_2,B_3\le 10^9$ , $1\le V_A,V_B\le 10^9$ , $1\le cnt_A,cnt_B\le 1,000$ 。
运行限制
语言 | 最大运行时间 | 最大运行内存 |
---|---|---|
C++ | 1s | 256M |
C | 1s | 256M |
Java | 2s | 256M |
Python3 | 3s | 256M |
PyPy3 | 3s | 256M |
Go | 3s | 256M |
JavaScript | 3s | 256M |
解题思路
1 |
|
翻转
问题描述
小蓝制作了 $n$ 个工件,每个工件用一个由小写英文字母组成的,长度为 $2$ 的字符串表示,第 $i$ 个工件表示为 $s_i$ 。小蓝想把 $n$ 个工件拼接到一起,方便转移到另一个地方完成下一道工序,而拼接后的工件用字符串 $S=s_1+s_2+…+s_n$ 表示,其中 $+$ 表示一种奇特的拼接方式:对于 $c=a+b$ 来说,如果 $a$ 的第二个字符和 $b$ 的第一个字符相同,则拼接后的结果 $c$ 长度为 $3$ 而不是 $4$ ,中间相同的字符可以省略一个,比如 $xy+yz=xyz$ 而 $xy+zy=xyzy$ 。小蓝为了让拼接后的字符串 $S$ 的长度尽量小,可以将若干个工件进行左右翻转之后再进行拼接,请问拼接后的字符串 $S$ 的最小长度是多少?
请注意所有工件必须按出现顺序依次拼接,可以翻转任意工件。
输入描述
输入的第一行包含一个正整数 $n$ 。
接下来 $n$ 行,每行包含一个长度为 $2$ 字符串,依次表示 $s_1, s_2, \cdots, s_n$ 。
输出描述
输出一行,包含一个整数表示答案。
样例输入
1 |
|
样例输出
1 |
|
样例说明
将 $s_2$ 翻转后,拼接结果为 $abczz$ ,长度为 $5$ 。
评测用例规模
对于 $20%$ 的评测用例, $n\le20$;
对于所有评测用例,$1\le n \le 10^5$ 。
运行限制
语言 | 最大运行时间 | 最大运行内存 |
---|---|---|
C++ | 1s | 256M |
C | 1s | 256M |
Java | 2s | 256M |
Python3 | 3s | 256M |
PyPy3 | 3s | 256M |
Go | 3s | 256M |
JavaScript | 3s | 256M |
总通过次数: 204 | 总提交次数: 253 | 通过率: 80.6%
难度: 中等 标签: 2023, 国赛, 动态规划
版权声明
部分题目由用户贡献,若您是著作权持有人,请与我们联系。
解题思路
1 |
|
最大阶梯
问题描述
小蓝特别喜爱阶梯图案,阶梯图案可以看做是由若干个大小和颜色都相同的方格组成的,对于大小为 $N$ 的阶梯图案,包含了 $N$ 个连续的列,其中第 $i$ 列恰好有 $i$($1\le i\le N$)个方格,将这 $N$ 列的底部对齐后便组成了一个阶梯图案,将其按照 $90$ 度旋转若干次后仍是阶梯图案,下图展示了几个不同大小的阶梯图案:
小蓝有一块大小为 $H\times H$ 的布匹,由 $H\times H$ 个大小相同的方格区域组成,每一个方格都有自己的颜色。小蓝可以沿着方格的边缘对布匹进行裁剪,他想要知道自己能得到的最大的同色阶梯图案的大小是多少?
输入描述
输入的第一行包含一个整数 $H$ 表示布匹大小。
接下来输入 $H$ 行,每行包含 $H$ 个整数,相邻的整数之间使用一个空格分隔,表示每个方格的颜色。
输出描述
输出一行包含一个整数表示答案。
样例输入
1 |
|
样例输出
1 |
|
样例说明
如下图所示,最大的同色阶梯图案用红色边框标出。
评测用例规模
对于 $30%$ 的评测用例, $1\le H\le 10$;
对于 $60%$ 的评测用例, $1\le H\le 100$;
对于所有评测用例, $1\le H\le 1000$ , $0\le$ 方格颜色$\le 10$ 。
运行限制
语言 | 最大运行时间 | 最大运行内存 |
---|---|---|
C++ | 1s | 256M |
C | 1s | 256M |
Java | 5s | 256M |
Python3 | 5s | 256M |
PyPy3 | 5s | 256M |
Go | 5s | 256M |
JavaScript | 5s | 256M |
总通过次数: 96 | 总提交次数: 158 | 通过率: 60.8%
难度: 中等 标签: 2023, 国赛, 动态规划
版权声明
部分题目由用户贡献,若您是著作权持有人,请与我们联系。
解题思路
1 |
|