codeforces round #620 题解

每次打得不好就会爆肝补之前落下的题解……只有被生活狠狠击打才能明白菜是原罪……

A. Two Rabbits

坐标差值如果是a+b的倍数则可以,否则不行

B. Longest Palindrome

我写的好复杂……字符串题做得太少了
其实就是:有反串的就输出2的倍数次,如果是串本身是回文串,是可以放中间的,所以如果有剩下的回文串,找一个最长的放在中间
reverse真好用

C. Air Conditioner

维护一个区间,代表到某个时间时空调温度可以达到的最大/最小值,和当前客人要求的温度取交集即可。如果交集为空则输出-1
判断[a,b][x,y]是否有交集:max(a,x) <= min(b,y)则有交集

D. Shortest and Longest LIS

构造题,求n满足条件的两个排列,一个LIS最长,另一个最短。
如果不考虑小于大于,LIS最长和最短的排列就是递增排列1~n和递减排列n~1,在这基础上修改就可以获得满足条件的排列
例如求最长LIS的排列,在1~n的排列基础上进行修改,如果遇到一个大于号,则把两边的数字交换一下;如果遇到一串大于号,则把这个区间反转一下。
最短同理。

E题想起来再补

点赞
  1. AffiliateLabz说道:

    Great content! Super high-quality! Keep it up! :)

发表评论

电子邮件地址不会被公开。 必填项已用*标注