放透视-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
@AC君,这是本人第一次写题解(真的吗),希望给一个加精。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
现在欢乐赛进化成这种程度了吗,好不容易AK一个欢乐赛,结果就因为吃了亿点点罚时给我干到200多名了,zao
先报个人难度:
题目 难度 T1 红 T2 红 T3 红 T4 红,上位 T5 红 T6 红
T1
不难看出,只要 A,B,CA,B,CA,B,C 三个数中有两个及以上的数是符合题目要求的,那么就直接输出YES:
时间复杂度:O(1)O(1)O(1),空间复杂度:O(1)O(1)O(1)
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
T2
本题可以这么想:要获得最少修改次数,每一个 AIA_IAI 加1的次数自然也要少。那么只有当 SZISZ_ISZI 和 SZI***Z_{I****ZI+1 相等的时候,才可以既满足条件又获得了最少的操作次数。所以我们定义一个变量NUM来统计我们需要改变的数量:每当前面的数大于其后边的数时,我们就将NUM加上这两个数差的绝对值。最后不要忘记将 SZI−1SZ_{I-1}SZI−1 的值赋值给 SZISZ_ISZI
时间复杂度:由于我们只进行了一次从2到A的循环,所以我们的时间复杂度就是 O(A)O(A)O(A),空间复杂度:O(A)O(A)O(A)
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
T3
题目说:忽略大小写的情况下,那么我们只需要将两个字符串都转为大写或小写,之后进行判等即可(某位用PY做的,,早知道我PY多学一点了,Z)这里注意用使用GETLINE进行输入:
时间复杂度: 我们只进行了一个 O(A.SIZE)O(A.SIZE)O(A.SIZE) 的和 O(B.SIZE)O(B.SIZE)O(B.SIZE) 的字符串转换操作,复杂度显而易见,为 O(∣A∣+∣B∣)O(|A|+|B|)O(∣A∣+∣B∣),空间复杂度:O(1)O(1)O(1)
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
T4:
典型的贪心策略,我们优先去那张为4的卡牌,4的那完了我们就那3的,以此类推,直到卡牌拿完或达到选取的数量为止:
时间复杂度:显然是O(1)O(1)O(1),空间复杂度:O(1)O(1)O(1)
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
T5:
本题可以使用暴力破解法(某位大佬用了字符串哈希也是可以的),因为数据较少,完全不用担心TLE:
时间复杂度:O(NM)O(NM)O(NM),空间复杂度:O(N2)O(N^2)O(N2)
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
T6:
板子题,直接从小码王递归里边复制,然后稍加修改,让它返回字符串即可:
时间复杂度:O(LOGA+LOGB)O(\LOG{A}+\LOG{B})O(LOGA+LOGB),这里的 LOGLOGLOG 以 RRR 为底。空间复杂度:O(1)O(1)O(1)
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
最后,特别鸣谢@AAA混泥土批发PPL哥指出本帖的错误,%%%。