标签: 贪心

10 篇文章

CF878E Numbers on the blackboard
题目链接:CF878E 给出 $n$ 个数字,每次询问一个区间 $[l,r]$,对这个区间内部的点进行操作。 每次操作可以合并相邻两个数 $x,y$ 其中 $x$ before $y$,将它们变成 $x+2y$ 对于每次询问输出当最后只剩下一个数字时,这个数字的最大值。 询问互相独立,答案对 $10^9+7$ 取模。 $1\leq n,q\leq …
义乌中学暑假集训 2021.07.15 D
白云在白兔的城市,打算在这里住 $n$ 天,这 $n$ 天,白云计划找白兔订购水。 白云给出了接下来的 $n$​ 天,每天的需水量,第 $i$​ 天为 $D_i$ 升。 白兔给出了接下来的 $n$ 天,每天水的价格,第 $i$ 天为 $P_i$ 元每升。 白云的小区有一个共用水壶,最大容量为 $V$ 升,初始为空。 接下来每天,白云可以进行如下操作…
义乌中学暑假集训 2021.07.15 B
白云建立了 $n$ 个商店,白兔打算按照编号 $1\sim n$ 的顺序访问这些商店。商店 $i$ 有一个价格 $ai$ 表示交易商品所需的代价。 白兔在按顺序走时,每到达一个商店,可以花费代价购买一件商品,并放入自己手中。也可以出售手上的商品,并获得利润。 白兔的力量有限,同一时刻只能携带一个商品。问它遍历完所有商店后能够获得的利润最大是多少? …
bzoj 2006. [NOI2010]超级钢琴 题解
Description 题目链接 给定一个长度为 $n$ 的序列,选出 $k$ 个长度在 $[L,R]$ 之间的子段(不可重复),求 $k$ 个子段和的最大值。 $N\leq 500,000,k\leq 500,000,-1000\leq A_i \leq 1000,1\leq L\leq R\leq N$ Solution 由于 $n$ 十分巨大…
Luogu P1514 引水入城 题解
题目链接 Describe 在一个遥远的国度,一侧是风景秀美的湖泊,另一侧则是漫无边际的沙漠。该国的行政区划十分特殊,刚好构成一个$N$行$\times M$列的矩形,如上图所示,其中每个格子都代表一座城市,每座城市都有一个海拔高度。 为了使居民们都尽可能饮用到清澈的湖水,现在要在某些城市建造水利设施。水利设施有两种,分别为蓄水厂和输水站。蓄水厂的…
Luogu P1084 疫情控制 题解
Link Luogu Problem view Describe 有一棵以$1$为根节点的树,现在要在除根节点外的点设立阻拦,使得没有一条路径可以从根节点到任意一个叶子节点。这些阻拦需要$m$个军队来设立,这$m$个军队中第$i$个一开始在点$q_i$上,军队移动的时间等于移动经过的边权之和,问最少要多少时间才能设立完阻拦。注意:不同的军队可以同时…