6.18

CF1154B Make Them Equal

题意:

  给一个长度为n的序列,求一个最小的数D,序列中的所有元素加上D,减去D或者不变,使修改后的序列所有元素都相等。

思路:

  一种数就d=0,两种数,如果差为偶数,d就是差的一半,否则就是差值,三种数如果是等差的就是差值,否则输出-1,三种以上的数字都是-1

 

CF1408D Searchlights

题意:

  给出n个强盗的二维坐标和m盏灯的二维坐标,如果强盗i的横/纵坐标大于灯j的横/纵坐标就不被看见,每次可以让所有强盗的x+1或y+1,求最小操作数使所有强盗都不被看见。

思路:

  因为n和m都很小,所以对于每个强盗,暴力枚举向上走的步数,再算出向右走的最小步数,其中取个最小值,再在所有强盗中取最大值

 

CF1399E1 Weights Division (easy version)

题意:

  给出一棵以1为根的数,每次可以选择一条边减半,求最少操作后使根到各节点距离之和小于S

思路:

  很明显可以贪心,每条边操作可以减少的值为(x-x/2)*son,直接从大到小选

 

CF1379C Choosing flowers

题意:

  有m种物品,每种物品有无限个,求购买n个物品的最大价值。对于第i种物品,第一次买时的贡献是ai ,接下来每次购买的贡献都是bi

思路:

  因为可以购买无数个,如果再贪心中选择了一个贡献bi的物品,那么剩下的都会买bi,所以bi最多会选择一个,所以枚举购买的bi,把所有大于bi的a都买了,剩下的买bi

 

CF1385E Directing Edges

题意:

  给一个由有向边与无向边组成的图,需要你把无向边变成有向边,且图中没有环。

思路:

  首先判断没有解的情况, 如果a到b有一条无向边,无论a->b还是b->a都会形成环的话,那么原图中就已经存在环,直接输出no,然后按照有向边的出度和入度进行拓扑排序,无向边反向连接

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