官方题解 | 挑战赛#28
本次题目的总体难度如下,各位选手可以借此评估一下自身的技术水平
题目编号 题目标题 难度 T1 午枫的翻转 入门 T2 午枫的卡片交换 普及- T3 午枫的石头剪刀布大赛 普及- T4 午枫的复制魔法 普及- T5 午枫的用户记录 普及/提高- T6 午枫的数字分离 普及/提高-
T1 午枫的翻转
题目大意
给定一个字符串和一个区间,输出翻转这段区间后的字符串。
解题思路
直接模拟或使用 reverse 函数即可。
参考代码
方法一
方法二
T2 午枫的卡片交换
题目大意
给定两个字符串 s,ts,ts,t ,问能否交换 sss 的相邻两个字符最多一次,使得 s=ts=ts=t 。
解题思路
枚举模拟每个相邻位置的交换,判断是否存在一个位置使得 s=ts=ts=t 即可。
参考代码
T3 午枫的石头剪刀布大赛
题目大意
有 2n2n2n 个人参加石头剪刀布比赛,一共 mmm 轮,每轮结束后重新排名,问最终的排名如何。
解题思路
使用结构体存储每名选手的编号、出拳顺序以及获胜场数,便于后续进行排序。
对每一轮比赛判断每组选手的胜负关系,记录每位选手的胜场数,每轮比赛结束对整体进行排序。
最终输出最终排名即可。
参考代码
T4 午枫的复制魔法
题目大意
给定一个数组 aaa ,将它无限复制得到新的数组 bbb ,从前往后依次累加,找出第一次使得累加和超过 xxx 的位置。
解题思路
直接一个一个累加计算判断很明显是通过不了的。设 sumsumsum 为数组 aaa 所有元素的和,于是可以 O(1)O(1)O(1) 计算出可以用最多多少个 sumsumsum ,剩下的部分一定能被数组 aaa 中某一个前缀超过,O(n)O(n)O(n) 遍历判断即可。
参考答案
T5 午枫的用户记录
题目大意
给出 nnn 名用户的起始登录时间以及连续登录天数,问对于每一个满足 1≤k≤n1\leq k\leq n1≤k≤n 的整数 kkk ,恰好有 kkk 人登录的天数。
解题思路
对于每一名用户,其对应登录的时间为一段连续的区间,不难想到使用差分前缀和来维护每天登录的人数。但由于数据范围较大,无法直接使用数组进行维护,考虑离散化,仅记录差分记录的时间点,因为前缀和后,相邻差分数组元素之间的值都是相等的,所以我们得到这段区间的值 valvalval 后可以直接计算出这段区间的长度 lenlenlen ,即为恰好有 valvalval 人的天数需要增加 lenlenlen 。
参考代码
T6 午枫的数字分离
题目大意
将给出的 nnn 进行重新排列,然后分离成两个不带前导零的正整数,求分离得到的两个数的乘积的最大值。
解题思路
考虑 dfsdfsdfs 或二进制枚举将所有分离情况全都找出来,并且判断分离是否合法,然后记录最大值即可。
参考代码