6
挑战赛27题解
本次题目的总体难度如下，各位选手可以借此评估一下自身的技术水平
题目编号 题目标题 难度 T1 午枫的矩形 入门 T2 午枫的字符串移动2 入门 T3 午枫打砖块 普及/提高- T4 午枫的子序列之和 普及/提高- T5 午枫的星星树 普及- T6 午枫的数字华容道 普及/提高-
T1 午枫的矩形
题目大意
给定一个矩阵，判断这个矩阵的任意子矩阵是否满足 左上角的数+右下角的数≤左下角的数+右上角的数左上角的数+右下角的数\leq 左下角的数+右上角的数左上角的数+右下角的数≤左下角的数+右上角的数 。
解题思路
由于数据范围只有 1≤n,m≤501\leq n,m\leq 501≤n,m≤50 ，所有直接四层循环嵌套枚举左上角和右下角，同时也能知道左下角和右上角的坐标，直接计算判断即可。
参考代码
T2 午枫的字符串移动2
题目大意
给定一个字符串，可以进行左移和右移的操作任意次，找到所有可以得到的字符串中字典序最小以及最大的字符串。
解题思路
因为可以操作任意次，所以只要单独往一个方向不断移动并且更新字典序最小和最大的字符串即可。
这里可以直接使用 string 类型进行移动的操作，并且也可以使用 min 和 max 函数进行比较字典序大小。
参考答案
T3 午枫打砖块
题目大意
给定 nnn 行砖块，每行向右无限延伸并且有且有一段连续的区间为奖励砖，每次可以选择一个区间长度 ddd ，并且将这 ddd 列每行所有的砖块都破坏，奖励砖只要被破坏一个格子就会被全部破坏，求将所有奖励砖都破坏需要的最少操作次数。
解题思路
这是一道经典的贪心问题，在排序时我们会想到，如果破坏一个奖励砖的最右端，那么就会破坏更多的奖励砖，所以我们按照右端点排序，模拟每次打破当前剩余第一个奖励砖的最右端即可。
参考答案
T4 午枫的子序列之和
题目大意
给定一个长度为 nnn 的数组和一个整数 kkk ，求数组 aaa 的所有连续子序列中，元素之和等于 kkk 的个数。
解题思路
首先我们可以预处理前缀和数组 sss ，即需要求区间满足 sr−sl−1=ks_r-s_{l-1}=ksr −sl−1 =k 的区间个数。问题就转化成了非常经典的问题。
枚举区间右端点 rrr ，同时统计已枚举前缀每个 sls_lsl 的个数，那么对于这个 rrr ，对答案贡献为满足 sl−1=sr−ks_{l-1} = s_r - ksl−1 =sr −k 的所有 lll 的个数。那么问题又进一步简化为：统计 si=xs_i = xsi =x 的个数。注意到数据范围无法用桶数组直接记录元素个数，考虑使用离散化或 map 直接统计都可完成。
参考代码
方法一：map
方法二：离散化
T5 午枫的星星树
题目大意
给定一棵树，问是否存在一个点与其他所有点直接相连。
解题思路
记录所有点的度数，判断是否存在一个点的度数为 n−1n-1n−1 即可。
参考代码
T6 午枫的数字华容道
题目大意
有 999 个点 mmm 条边的无向图，其中有 888 个数字放置在不同点上，有一个没有数字的点，可以通过移动将数字移动到相邻没有数字的点上，求最终将数字 1∼81\sim 81∼8 分别放在顶点 1∼81\sim 81∼8 上的最少操作次数。
解题思路
我们可以将 999 个顶点上所存放的数字用字符串表示状态，例如 254806137 表示顶点 111 存放数字 222 ，顶点 222 存放数字 555 ，依此类推，特殊地，数字 000 表示该点为空。那么终点就可以用 123456780 表示。
由于每次移动都会从一种状态变为另一种状态，我们不妨将每种状态看作一个结点，那么所有状态以及状态与状态之间的变换就可以形成一张无向图，于是我们只需要在图上用 bfsbfsbfs 跑最短路即可。由于结点是以字符串表示的，所以可以使用 map 存储从起点状态到达所有状态结点的最短路径长度。
参考代码
？
有帮助，赞一个