6.14

CF1525C Robot Collisions

题意:

  有 n个机器人,每个机器人有一个初始的方向,每一秒走一个单位,到达了边界会掉头。如果相遇,那么它们就会碰撞炸掉,求出每个机器人最早炸掉的时间。

思路:

  因为速度都是1,只有坐标奇偶性相同的机器人才能相遇,不然会穿过去,所以分别处理。处理时用一个栈,扫一遍匹配,如果栈第一个是L,就是撞左墙,把坐标变成-x放入栈中,如果栈最后一个是R,坐标变成2m-x放入和R匹配。

 

CF1536D Omkar and Medians

题意:

  给定一个n*m的矩阵,每次操作可以改变一个字符,求最小的操作,使的每个2×2的子矩阵中都含有AGCT四个字母

思路:

  假设第一个矩阵放的是AG那么第三列也只能放A,所以最后就会变成第一列两个字符轮流,第二列剩下的两个字符交替,所以一共24种组合暴力算一下

            CT         C

 

CF1514D Cut and Stick

题意:

  给出长度问n的序列,m个询问,求出每个询问的区间中最少要分成多少个区间时区间内出现最多的数字不超过x/2

思路:

  在一个区间中,所有的非众数和相同个数的众数放入一个区间,剩下的众数每个自称一个区间,所以就是就求区间内的众数个数,莫队可以解决

 

CF1506G Maximize the Remaining String

题意:

  给出一个字符串,求删除重复的字符后(每种字母只出现一次)字典序最大的字符串

思路:

  考虑贪心,用一个栈从左往右扫,如果前面的字符不止一个的且删除后字典序增大就可以删除

 

CF266C Below the Diagonal

题意:

  n*n的01矩阵,告诉你n-1个1的位置,每次操作可以交换任意两行或两列,任意操作次数后让1都在主对角线以下

思路:

  因为只有n-1个1,最差情况排成一列或一行都可以,所以暴力放即可,把空行和空列放在最上面和最右边,然后扫过去即可

原文地址:https://www.cnblogs.com/Tokisaki-Kurumi/p/14883314.html