type
status
date
slug
summary
tags
category
icon
password
祝贺社长致之在 2024 小图灵信息学【提高组】10 月线上赛（原创题）中斩获上海市第一名，全国第七名。
在 CSP-J/S 2024 第二轮来临之际，致之在小图灵月赛中获此佳绩。让我们祝他在 10 月 26 日 RP++，AK 复赛，顺利晋级 NOIP 吧！
致之并非有道小图灵在班学生。小图灵月赛免费参与，题目优质，能够磨练专题能力，不报白不报😋
【正式考试时间】：10月20日（周日）14:00-16:00
月赛专题：动态规划2（各种优化）
📝 题目内容
题目1
题目名称：收集宝物
提交通过率：8%测评方式
标准输入输出
时间限制
1000ms
内存限制
512MB
题目描述
Zeratul 被困在了一个 n×m 的迷宫中。
这时 Zeratul 听到了一个神秘的声音：迷宫中有 k 种宝物，你必须收集所有的 k 种宝物才能离开迷宫。
Zeratul 每次可以向上下左右移动一格，并且不能走到
# 或超出迷宫边界。现在 Zeratul 想要知道，至少经过多少步才能收集所有的宝物。输入描述
第一行包括三个整数 n,m,k，代表迷宫的大小和宝物的种类数。
接下来是一个 n×m 的字符矩阵，代表这个迷宫。
. 代表空地，# 代表墙壁，Z 代表 Zeratul 的初始位置，数字 1 ~ k 代表宝物。输出描述
一个整数代表答案。如果 Zeratul 无法收集全部种类的宝物，输出
-1 。样例1
输入
3 5 2
2#Z#1
##.##
1...2
输出
8
样例2
输入
3 5 3
2#Z#1
##1##
11112
输出
1
提示
对于10%的数据，k=1k=1
对于30%的数据，k≤3k≤3
对于另外20%的数据，n≤2n≤2
对于100%的数据，1≤n,m≤100, 1≤k≤91≤nm≤100, 1≤k≤9
题目2
题目名称：删除子串
提交通过率：2%测评方式
标准输入输出
时间限制
1000ms
内存限制
512MB
题目描述
Zeratul给出了一个长度为 nn 的字符串，你需要依次做 mm 次操作，其中第 ii 次操作需要在当前的字符串中选择一个长度为 2i−12i−1 的子串，并且将它删除。
你需要让 mm 次操作后，剩余字符串的字典序尽可能小。
输入描述
第一行包括两个整数 n,mnm，代表字符串的长度和操作的次数。
第二行包括一个长度为 nn 的，只包括小写字母的字符串，代表初始的字符串。
输出描述
输出一行代表答案。
样例1
输入
7 1
abcdcba
输出
abccba
样例2
输入
8 2
abcdabcd
输出
aabcd
提示
本题共有10个测试点。
对于测试点1，m=1m=1
对于测试点2，3，n≤10n≤10
对于测试点4，5，6，n≤100n≤100
对于全部测试点，1≤2m≤n≤2121≤2m≤n≤212
提示：本题正解确实是状压DP，但你也许需要从贪心开始考虑。
题目3
题目名称：方差
提交通过率：3%测评方式
标准输入输出
时间限制
1000ms
内存限制
512MB
题目描述
输入一个长度为 nn 的数列 a[1...n]a[1...n] 。接下来要把这个数列分成 kk 段，使得这 kk 段的方差最小。
为了避免浮点误差，你应该输出这个方差 ×k2×k2 的值。这个值显然是一个整数。
输入描述
第一行包括两个整数 n,knk ，第二行包括一个长度为nn的数组 a[1...n]a[1...n] 。含义见题目描述。
输出描述
一个整数，代表方差 ×k2×k2 的值。
样例1
输入
6 2
1 1 4 5 1 4
输出
16
提示
对于30%的数据，n≤10n≤10
对于60%的数据，n≤100n≤100
对于100%的数据，1≤k≤n≤30001≤k≤n≤3000，a[1...n]a[1...n]的总和不超过3×1043×104
🤗 总结归纳
总结文章的内容
📎 参考答案
T1
T2
T3
- 作者:DrimTech
- 链接:https://drim.cc/xiao-turing-senior-prize-202410
- 声明:本文采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处。
相关文章
