首页 > 代码库 > 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)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。