首页 > 代码库 > Codeforces Round #379(div 2)

Codeforces Round #379(div 2)

A、B:=w=

C:

  题意:

      你需要制作n瓶药水,每一瓶药水需要x秒。

      你现在有m种A魔法,花费b[i],使得每一瓶药水的花费代价降为a[i],只能用一次。

      有K种B魔法,花费d[i],使得瞬间制作好c[i]瓶药水,只能用一次。

      你最多花费s的魔法值

      问你最快完成要多少秒。

  分析:题目所给的B魔法都是递增的,容易想到枚举用哪个A魔法,二分对应的B魔法,因为在MP充足的情况下,减少的药水越多对ans越有利

D:

  题意:一个无限大的平面,给你一个King的位置,再给你其他棋子的位置,问你这个King是不是正在被人将军。一共三种棋子R B Q,R只能够直走,B只能斜走,Q能斜走也能直走,但它们都无法跳子

  分析:记录下King的八个方向离其最近的点,根据属性判断是否被将军。

E:

  题意:给你一棵树,每个树上的节点要么是1,要么是0,每次操作你可以指定任何一个节点,然后使得这个节点周围的同色连通块变色。问你最少花费多少次,使得整个树都是一个颜色。

  分析:首先肯定先缩一波点,然后就成了一颗树,这棵树是黑点、白点相间的。

     如果正好是个链,那么我们可以每次从中间点开始变色,答案就是len/2

     对于一般的树而言,考察树的最长链,其他的树边看作挂在链周围,那么发现我们如果也是每次从中间点开始变色,那么len/2操作后所有的点都成了同一颜色。

       所以ans=树的直径/2

Codeforces Round #379(div 2)