以上是本人猜测题目难度,仅供参考:
题号 题目 难度 T1 大大和1 入门 T2 午枫的博弈 普及- T3 小午的请求 入门 T4 小枫爬山 普及- T5 午枫的双人挑战 普及/提高- T6 大大和2 普及+/提高
以上为猜测 一定正确 以官方(@NOONMAPLE)为准。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
T1. 大大和1
题目大意:
给你一个数组aaa,让你求出是否存在任何一个(i,j)(i, j)(i,j)数对满足以下条件:
max(ai,ai+1,…,aj−1,aj)≥ai+ai+1+⋯+aj−1+ajmax(a_i, a_{i + 1}, \dots,a_{j-1},a_j) \geq a_i + a_{i + 1} + \dots + a_{j - 1} + a_{j}max(ai ,ai+1 ,…,aj−1 ,aj )≥ai +ai+1 +⋯+aj−1 +aj 。
解题思路:
这题里面,(i,j)(i, j)(i,j)数对可以满足一个条件,就是i≤ji \leq ji≤j,所以i=ji = ji=j是可能的,max(aimax(a_imax(ai 至 aj)a_j)aj )的结果自然就是aia_iai 或者aja_jaj (是一样的),而ai+ai+1+⋯+aj−1+aja_i + a_{i + 1} + \dots + a_{j - 1} + a_{j}ai +ai+1 +⋯+aj−1 +aj 就自然是aia_iai 或者aja_jaj ,aia_iai 必定 = aia_iai ,所以不论是什么数,结果都是YES。
参考代码:
时间复杂度:O(n)O(n)O(n)
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
T2. 午枫的博弈
题目大意:
给你nnn个数的数组AAA,小午只能隐藏奇数下标的数,小枫只能隐藏偶数下标的数,当场上只剩下一个数未被隐藏时,如果数字本身是奇数,小午胜;反之,小枫胜。
解题思路:
题目说了双方都足够聪明,所以双方都会尽量让剩下的数是 奇数/偶数。而小午是先隐藏的,所以我们可以得出这样的结论:
奇数下标有没有奇数 偶数下标有没有偶数 胜利方 解释 有 有 偶数数量多则小枫;反之,小午 -- 有 没有 小午 -- 没有 有 小枫 -- 没有 没有 小枫 由于小枫是后翻牌的,所以翻到最后剩下偶数就可以了
总结出后,就可以写出以下代码。
参考代码:
时间复杂度:O(n)O(n)O(n)
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
T3. 小午的请求
题目大意:
给出你nnn个数,求最大的和,结果为偶数
解题思路:
我们可以将所有数相加,如果是偶数,那就肯定是最大的。反之,则减去最小奇数即可。
例如:
所有数相加结果是15,不为偶数,所以减去最小奇数(1),结果为14。
参考代码:
时间复杂度:O(nlogn)O(n logn)O(nlogn)
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
T4. 小枫爬山
小枫有病,爬山看别人腿长
题目大意:
现在有nnn级台阶,mmm个爬山者(腿长),请问这mmm个爬山者最高能爬到的高度。
解题思路:
如果一个一个判断会TLE 别问我怎么知道,所以我们可以使用一个巧妙的方法!给爬山者的腿长排序,上一个爬山者能爬到的高度,这一个肯定可以,就判断是不是能 更上一层楼 再爬多几层。
参考代码:
时间复杂度:O(n+mlogm)O(n + m log m)O(n+mlogm)
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
T5. 午枫的双人挑战
题目大意:
观众要求小午和小枫完成kkk个关卡。要是完成这个关卡的战斗部分,就算完成了一个关卡。但是,如果你要完成战斗部分的关卡,必须先完成本关解密部分的关卡。示意图如下:
解题思路:
在这题里面,我们可以先用前缀和优化,然后使用priority_queue [1]。在这题里面,要求是尽量小,所以每次弹出的是最大的元素。因此,可以求出最小值。
为什么不用QUEUE?
其实,用queue也是可行的,不过时间复杂度会更高,因为每次都要找出最大值/排序。
参考代码:
时间复杂度:O(n+q⋅nlogx)O(n+q⋅nlogx)O(n+q⋅nlogx)
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
T6. 大大和2
题目大意:
给你一个数组aaa,让你求出是否所有(i,j)(i, j)(i,j)的数对都满足以下条件:
max(ai,ai+1,…,aj−1,aj)≥ai+ai+1+⋯+aj−1+ajmax(a_i, a_{i + 1}, \dots,a_{j-1},a_j) \geq a_i + a_{i + 1} + \dots + a_{j - 1} + a_{j}max(ai ,ai+1 ,…,aj−1 ,aj )≥ai +ai+1 +⋯+aj−1 +aj 。
解题思路:
这题分出几种情况。
1. 最大值是负数,那答案肯定是YES。不论什么区间,负数加起来肯定是更小的。例如:
随便拿取任何区间,都能满足条件。
2. 相邻的数是整数,答案肯定是NO。因为任何的整数加起来肯定是更大的。例如:
例如2 3,max(2,3)<2+3max(2, 3) < 2 + 3max(2,3)<2+3,所以是NO。
3. 遍历所有数组里面的正整数,遍历 (左十,右十)(左十, 右十)(左十,右十) 这个区间是否满足条件。
(测试点有点水,不然不能这么做)\COLOR{YELLOW}{(测试点有点水,不然不能这么做)}(测试点有点水,不然不能这么做)
参考代码:
时间复杂度:O(t⋅n)O(t \cdot n)O(t⋅n)
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
写的好的话点个赞吧!第一次写,写的不好见谅
午枫这次出题变简单了\COLOR{YELLOW}{午枫这次出题变简单了}午枫这次出题变简单了
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
1. priority_queue,是一种STL容器,他并非queue一样是FIFO(First In Fist Out) ,而每次弹出的是最高优先级的元素。 ↩︎