T1:午枫的翻转
本题太水,就直接放代码了哈
T2:午枫的卡片交换
思路解析
题目要求:最多一次交换相邻字符,能否使字符串 sss 变成 ttt。
情况分析
* 如果 sss 和 ttt 已经相同,则不需要交换,直接输出 Yes。
* 否则,只能交换一次相邻字符,意味着 sss 和 ttt 最多只能有两处不同(交换的那一对位置及其相邻影响)。
* 更简单的做法:直接枚举所有相邻交换,检查是否得到 ttt。
由于 ∣s∣≤100|s| \leq 100∣s∣≤100,O(n2)O(n^2)O(n2) 枚举完全可行。
代码实现
T3: 午枫的石头剪刀布大赛
思路解析
这是一个模拟 + 排序的问题。
* 有 2n2n2n 名选手,编号 1∼2n1 \sim 2n1∼2n,进行 mmm 轮比赛。
* 每轮根据上一轮的排名进行配对:排名 2k−12k-12k−1 和 2k2k2k 对战。
* 每场比赛根据手势决定胜负(G石头、C剪刀、P布),胜者胜场 +1+1+1。
* 每轮结束后重新排名:先按胜场数降序,相同则编号小的靠前。
* 最终输出 mmm 轮后的最终排名(即第 mmm 轮结束后的排名)。
实现步骤
1. 读入 n,mn,mn,m 和每个选手每轮的手势(2n2n2n 行,每行 mmm 个字符)。
2. 用一个数组或结构体记录每个选手的编号和胜场数,初始胜场为 000。
3. 对每一轮 jjj(从 111 到 mmm):
* 按照当前排名(胜场降序,编号升序)排序。
* 两两配对进行比赛,根据手势更新胜场。
4. 最后按排名输出选手编号。
代码实现
T4:午枫的复制魔法
思路解析
数组 aaa 无限复制得到数组 bbb,求累加和第一次超过 xxx 的位置。
关键思路
1. 先计算一轮的总和 sum=∑i=1naisum = \sum_{i=1}^n a_isum=∑i=1n ai 。
2. 如果 sum≤0sum \le 0sum≤0(本题保证 ai≥1a_i \ge 1ai ≥1,所以 sum>0sum > 0sum>0),不需要考虑这种情况。
3. 完整轮数 full=⌊x/sum⌋full = \lfloor x / sum \rfloorfull=⌊x/sum⌋,这些完整轮贡献的位置数为 full×nfull \times nfull×n,总和为 full×sumfull \times sumfull×sum。
4. 剩余需要累加的量 remain=x−full×sumremain = x - full \times sumremain=x−full×sum。
5. 从 a1a_1a1 开始依次累加,直到累加和 >remain> remain>remain,此时总位置 = full×n+ifull \times n + ifull×n+i(iii 是当前累加到的位置)。
代码实现
T5: 午枫的用户记录
思路解析
我们需要统计:恰好有 kkk 个用户同时登录的天数,k=1,2,…,nk = 1, 2, \dots, nk=1,2,…,n。
关键观察
* 每个用户的登录区间是 [bgi,bgi+cnti)[bg_i, bg_i + cnt_i)[bgi ,bgi +cnti )(左闭右开,因为最后一天是 bgi+cnti−1bg_i + cnt_i - 1bgi +cnti −1,所以结束时间是 bgi+cntibg_i + cnt_ibgi +cnti )。
* 我们可以使用差分数组的思想,但 bgibg_ibgi 和 cnticnt_icnti 高达 10910^9109,不能直接开数组。
* 用 map 存储差分:在 bgibg_ibgi 处 +1+1+1,在 bgi+cntibg_i + cnt_ibgi +cnti 处 −1-1−1。
* 遍历 map(天然按时间排序),维护当前登录人数 curcurcur,以及上一时间点 lastlastlast。
* 每一段 [last,pos)[last, pos)[last,pos) 长度 pos−lastpos - lastpos−last 的区间内,登录人数都是 curcurcur。
* 将该段长度累加到 ans[cur]ans[cur]ans[cur] 中。
代码实现
T6:午枫的数字分离
思路解析
题目要求:将 nnn 的各位数字重新排列,分成两个正整数(不能有前导零),使得它们的乘积最大。
关键观察
* n≤109n \le 10^9n≤109,最多 10 位数字,可以暴力枚举所有划分方式。
* 枚举所有子集分配,检查是否满足无前导零(两个数的首位不能是 0)。
* 对每个子集,将分配给第一个数的数字降序排列得到最大可能的数,第二个数同理。
* 计算乘积,更新最大值。
优化
* 由于数字可能重复,可以用 multiset 或直接排序。
* 枚举所有非空真子集(至少给每个数一个数字)。
代码实现
我可爱的马蜂