比赛链接:

https://acm.ayit.edu.cn/contest/9

A: A+B+C Problem

语言题, 注意三个数相加会爆int, 别的没了

标算代码: 2155

B: 复读机

还是语言题, 每次读一个字符串并检查与上一个是否相等即可

标算代码: 2156

C: 括号序列

经典题, 用栈直接维护即可

对于一个左括号, 我们直接将其压入栈中

对于一个右括号, 我们直接查询栈顶的左括号是否与其匹配

是的话将其弹出, 否则显然序列已经不合法了

注意特判最后有剩余括号的情况

D: 滑雪

10分做法: 直接暴力模拟一步一步地走即可, 复杂度O(n^2)

30分做法: 考虑对10分做法的优化, 我们可以每次走一条边, 复杂度O(n)

80分做法1(假): 考虑到只有一组数据, 我们可以加一些魔法优化(ka chang), 然后复杂度变成O(n/x), 过了

80分做法2: 从外往里走好像很难看, 我们从里往外走试试

很容易就会发现轨迹总是一个矩形 + 一条线段

所以我们先求出终点位置, 然后求出(总步数-走的步数), 然后开个方求出轨迹的正方形部分边长, 然后特判掉线段部分就ok了

具体的话分类讨论可能麻烦一点, 复杂度O(1)

标算代码: 2158

80分做法3: 从外往里走当然也可以大致看做一个等差序列啦

所以我们直接二分环数然后微调位置也是可以的

不过zdw懒所以没有写

E: 数字游戏

20分做法: 首先要发现传递是单向的, 所以我们贪心地把每个多余的数变成最近的缺少的数即可

于是直接模拟就能拿到20了

120分做法: 考虑维护, 可以用堆维护多余/缺少的数然后单向扫描即可

但实际上这里可以不用堆, 直接用两个指针来模拟即可

标算代码: 2159

F: 最长公共前缀

十分经典的题目呢。。。解法非常多, 各种字符串处理工具都可以做

我这里用的是最菜最暴力的二分+哈希

二分公共前缀的长度然后直接比对哈希值就好了(捂脸)

标算代码: 2160

那么这场 Easy Round 各位玩的开心吗 )

欢迎在评论区留言吐槽或者讨论其他解法