Menci

眉眼如初,岁月如故

在那无法确定的未来
只愿真心如现在一般清澈


  1. 「SCOI2016」美味 - 贪心 + 主席树

    一家餐厅有 n n 道菜,编号 1n 1 \ldots n ,大家对第 i i 道菜的评价值为 i i 1in 1 \leq i \leq n )。有 m m 位顾客,第 i i 位顾客的期望值为 bi b_i ,而他的偏好值为 xi x_i 。因此,第 i i 位顾客认为第 j j 道菜的美味度为 xor \text{xor} 表示异或运算)。第 i i 位顾客希望从这些菜中挑出他认为最美味的菜,即美味值最大的菜,但由于价格等因素,他只能从第 li l_i 道到第 ri r_i 道中选择。请你帮助他们找出最美味的菜。

    于  BZOJ, SCOI, 主席树, 贪心 继续阅读

  2. 「BZOJ 3062」Taxi - 贪心

    Bessie 在农场上为其他奶牛提供出租车服务。这些奶牛已经在沿着长度为 M M 的栅栏上不同的地点聚集等候。不幸的是,他们已经厌倦了他们当前所在的位置并且每只奶牛都想要沿着栅栏去别的地方走走。Bessie 必须赶到这些奶牛的起始位置,并把他们带到它们的目的地。Bessie 的车很小,所以她只能一次只能搭载一头奶牛。奶牛可以在同一时刻完成上车和下车。

    为了节省燃气,Bessie 想以尽可能少的燃料完成这次任务。N N 只奶牛的起始位置和结束为止都是已知的,请确定 Bessie 的最少行程。Bessie 意识到,要使所得到的行程最短,Bessie 可能将在沿途中让奶牛上车或下车而并不一定将一头奶牛从起点直接送到中点。

    Bessie 的起点是围栏的最左端,位置记为 0 0 。终点在篱笆的最右边,位置记为 M M

    于  BZOJ, 贪心 继续阅读

  3. 「HAOI2007」上升序列 - DP + 贪心

    对于一个给定的 S={a1,a2,a3,,an} S = \{ a_1, a_2, a_3, \ldots , a_n \} ,若有 P={ax1,ax2,ax3,,axm} P = \{ a_{x_1},a_{x_2}, a_{x_3}, \ldots, a_{x_m} \} ,满足 x1<x2<<xm x_1 < x_2 < \ldots < x_m ax1<ax2<<axm a_{x_1} < a_{x_2} < \ldots < a_{x_m} ,那么就称 P P S S 的一个上升序列。如果有多个 P P 满足条件,那么我们想求字典序最小的那个。

    任务给出 S S 序列,给出若干询问。对于第 i i 个询问,求出长度为 Li L_i 的上升序列,如有多个,求出下标字典序最小的那个。

    于  BZOJ, DP, HAOI, 贪心 继续阅读

  4. 「NOIP2012」疫情控制 - 二分 + 倍增 + 贪心

    H 国有 n n 个城市,这 n n 个城市用 n1 n - 1 条双向道路相互连通构成一棵树,1 1 号城市是首都,也是树中的根节点。

    H 国的首都爆发了一种危害性极高的传染病。当局为了控制疫情,不让疫情扩散到边境城市(叶子节点所表示的城市),决定动用军队在一些城市建立检查点,使得从首都到边境城市的每一条路径上都至少有一个检查点,边境城市也可以建立检查点。但特别要注意的是,首都是不能建立检查点的。

    现在,在 H 国的一些城市中已经驻扎有军队,且一个城市可以驻扎多个军队。一支军队可以在有道路连接的城市间移动,并在除首都以外的任意一个城市建立检查点,且只能在一个城市建立检查点。一支军队经过一条道路从一个城市移动到另一个城市所需要的时间等于道路的长度(单位:小时)。

    请问最少需要多少个小时才能控制疫情。注意,不同的军队可以同时移动。

    于  CodeVS, NOIP, 二分, 倍增, 贪心 继续阅读

  5. 「ZJOI2008」泡泡堂 - 贪心

    两队分别 n n 个选手对战,已知每个选手的实力,实力强的选手一定获胜。每一场胜、平、败的得分分别为 2,1,0 2, 1, 0 。求一个队能获得的最高得分和最低得分。

    于  BZOJ, ZJOI, 贪心 继续阅读

  6. 「JSOI2007」建筑抢修 - 贪心

    部落基地里只有一个修理工人,虽然他能瞬间到达任何一个建筑,但是修复每个建筑都需要一定的时间。同时,修理工人修理完一个建筑才能修理下一个建筑,不能同时修理多个建筑。如果某个建筑在一段时间之内没有完全修理完毕,这个建筑就报废了。你的任务是帮小刚合理的制订一个修理顺序,以抢修尽可能多的建筑。

    于  BZOJ, JSOI, 贪心 继续阅读

  7. 「JSOI2007」麻将 - 枚举 + 贪心

    在这种特殊的麻将里,没有字牌,花色也只有一种。但是,序数 不被限制在一到九的范围内,而是在 1 1 n n 的范围内。同时,也没有每一种牌四张的限制。一组和了的牌由 3m+2 3m + 2 张牌组成,其中两张组成对子,其余 3m 3m 张组成三张一组的 m m 组,每组须为顺子或刻子。现给出一组 3m+1 3m + 1 张的牌,要求判断该组牌是否为听牌(即还差一张就可以和牌)。如果是的话,输出所有可能的等待牌。

    于  BZOJ, JSOI, 枚举, 贪心 继续阅读

  8. 「NOIP2013」花匠 - 贪心

    花匠栋栋种了一排花,每株花都有自己的高度。花儿越长越大,也越来越挤。栋栋决定把这排中的一部分花移走,将剩下的留在原地,使得剩下的花能有空间长大,同时,栋栋希望剩下的花排列得比较别致。

    具体而言,栋栋的花的高度可以看成一列整数 h1,h2,,hn h_1, h_2, \ldots, h_n 。设当一部分花被移走后,剩下的花的高度依次为 g1,g2,,gm g_1, g_2, \ldots, g_m ,则栋栋希望下面两个条件中至少有一个满足:

    条件 A:对于所有的 1<i<m2 1 < i < \frac{m}{2} g2i>g2i1 g_{2i} > g_{2i - 1} g2i>g2i+1 g_{2i} > g_{2i + 1}
    条件 B:对于所有的 1<i<m2 1 < i < \frac{m}{2} g2i<g2i1 g_{2i} < g_{2i - 1} g2i<g2i+1 g_{2i} < g_{2i + 1}

    注意上面两个条件在 m=1 m = 1 时同时满足,当 m>1 m > 1 时最多有一个能满足。
    请问,栋栋最多能将多少株花留在原地。

    于  CodeVS, NOIP, 贪心 继续阅读

  9. 「BZOJ 1692」队列变换 - 后缀数组 + 贪心

    对于一个字符串 S S ,每次从它的首部或尾部弹出一个字符,加入到 T T 的尾部,求可以构造出的字典序最小的 T T

    于  BZOJ, USACO, 后缀数组, 字符串, 贪心 继续阅读

  10. 「NOI2014」起床困难综合征 - 位运算 + 贪心

    drd 有着十分特殊的技能,他的防御战线能够使用一定的运算来改变他受到的伤害。具体说来,drd 的防御战线由 n n 扇防御门组成。每扇防御门包括一个运算 和一个参数 t t ,其中运算一定是 中的一种,参数则一定为非负整数。如果还未通过防御门时攻击力为 x x ,则其通过这扇防御门后攻击力将变为 。最终 drd 受到的伤害为对方初始攻击力 x x 依次经过所有 n n 扇防御门后转变得到的攻击力。 由于 atm 水平有限,他的初始攻击力只能为 0 0 m m 之间的一个整数(即他的初始攻击力只能在 0 0 1 1 m m 中任选,但在通过防御门之后的攻击力不受 m m 的限制)。为了节省体力,他希望通过选择合适的初始攻击力使得他的攻击能让 drd 受到最大的伤害。

    于  BZOJ, NOI, 位运算, 贪心 继续阅读