Menci

眉眼如初,岁月如故

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


  1. 「CQOI2009」跳舞 - 网络流

    一次舞会有 n n 个男孩和 n n 个女孩。每首曲子开始时,所有男孩和女孩恰好配成 n n 对跳交谊舞。每个男孩都不会和同一个女孩跳两首(或更多)舞曲。有一些男孩女孩相互喜欢,而其他相互不喜欢(不会「单向喜欢」)。每个男孩最多只愿意和 k k 个不喜欢的女孩跳舞,而每个女孩也最多只愿意和 k k 个不喜欢的男孩跳舞。给出每对男孩女孩是否相互喜欢的信息,舞会最多能有几首舞曲?

    于  BZOJ, CQOI, 二分答案, 网络流 继续阅读

  2. 「TJOI2015」组合数学 - DP + 结论

    给出一个网格图,其中某些格子有财宝,每次从左上角出发,只能向下或右走。问至少走多少次才能将财宝捡完。此对此问题变形,假设每个格子中有好多财宝,而每一次经过一个格子至多只能捡走一块财宝,至少走多少次才能把财宝全部捡完。

    于  BZOJ, DP, TJOI, 结论 继续阅读

  3. 「BZOJ 3062」Taxi - 贪心

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

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

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

    于  BZOJ, 贪心 继续阅读

  4. 「BZOJ 3376」Cube Stacking - 带权并查集

    约翰和贝茜在玩一个方块游戏。编号为 1 1 n n n n 个方块正放在地上.每个构成一个立方柱。

    游戏开始后,约翰会给贝茜发出 m m 个指令。指令有两种:

    1. 移动:将包含 x x 的立方柱移动到包含 y y 的立方柱上;
    2. 统计:统计名含 x x 的立方柱中,在 x x 下方的方块数目。

    写个程序帮贝茜完成游戏。

    于  BZOJ, 并查集, 数据结构 继续阅读

  5. 「SDOI2009」HH 的项链 - 莫队

    给一个长度为 n n 的序列,每次查询一个区间中不同的数的个数。

    于  BZOJ, SDOI, 数据结构, 莫队 继续阅读

  6. 「WC2013」糖果公园 - 树链剖分 + 莫队

    Candyland 有一座糖果公园,公园里不仅有美丽的风景、好玩的游乐项目,还有许多免费糖果的发放点,这引来了许多贪吃的小朋友来糖果公园玩。

    糖果公园的结构十分奇特,它由 n n 个游览点构成,每个游览点都有一个糖果发放处,我们可以依次将游览点编号为 1 1 n n 。有 n1 n - 1 双向道路连接着这些游览点,并且整个糖果公园都是连通的,即从任何一个游览点出发都可以通过这些道路到达公园里的所有其它游览点。

    糖果公园所发放的糖果种类非常丰富,总共 m m 种,它们的编号依次为 1 1 m m 。每一个糖果发放处都只发放某种特定的糖果,我们用 ci c_i 来表示 i i 号游览点的糖果。

    来到公园里游玩的游客都不喜欢走回头路,他们总是从某个特定的游览点出发前往另一个特定的游览点,并游览途中的景点,这条路线一定是唯一的。他们经过每个游览点,都可以品尝到一颗对应种类的糖果。

    大家对不同类型的糖果的喜爱程度都不尽相同。根据游客们的反馈打分,我们得到了糖果的美味指数,第 i i 种糖果的美味指数为 vi v_i 。另外,如果一位游客反复地品尝同一种类的糖果,他肯定会觉得有一些腻。根据量化统计,我们得到了游客第 i i 次品尝某类糖果的新奇指数 wi w_i ,如果一位游客第 i i 次品尝第 j j 种糖果,那么他的愉悦指数 H H 将会增加对应的美味指数与新奇指数的乘积,即 vjwi v_j w_i 。这位游客游览公园的愉悦指数最终将是这些乘积的和。

    当然,公园中每个糖果发放点所发放的糖果种类不一定是一成不变的。有时,一些糖果点所发放的糖果种类可能会更改(也只会是 m m 种中的一种),这样的目的是能够让游客们总是感受到惊喜。 糖果公园的工作人员小 A 接到了一个任务,那就是根据公园最近的数据统计出每位游客游玩公园的愉悦指数。但数学不好的小 A 一看到密密麻麻的数字就觉得头晕,作为小 A 最好的朋友,你决定帮他一把。

    于  BZOJ, WC, 数据结构, 最近公共祖先, 树链剖分, 莫队 继续阅读

  7. 「BZOJ 2724」蒲公英 - 分块

    给一个长度为 n n 的序列,每次查询一个区间 [l,r] [l, r] 内的众数(如果有多个众数,取最小的一个),强制在线。

    于  BZOJ, 分块, 数据结构 继续阅读

  8. 「NOI2005」维修数列 - Splay

    请写一个程序,要求维护一个数列,支持以下 6 6 种操作。

    操作 输入格式 说明
    插入 INSERT pos cnt a[1] a[2] ...... a[cnt] 在当前数列的第 pos \text{pos} 个数字后插入 cnt \text{cnt} 个数字:a1,a2,acnt a_1, a_2 \ldots, a_{\text{cnt}} ,如果 pos=0 \text{pos} = 0 ,则在首部插入
    删除 DELETE pos cnt 从当前数列的第 pos \text{pos} 个数字开始,删除连续的 cnt \text{cnt} 个数字
    修改 MAKE-SAME pos cnt x 将当前数列的第 pos \text{pos} 个数字开始的连续 cnt \text{cnt} 个数字统一修改为 x x
    翻转 REVERSE pos cnt 取出当前数列的第 pos \text{pos} 个数字开始的连续 cnt \text{cnt} 个数字,翻转后放入原来的位置
    求和 GET-SUM pos cnt x 计算从当前数列的第 pos \text{pos} 个数字开始的连续 cnt \text{cnt} 个数字的和并输出
    最大子段和 MAX-SUM 求出当前数列中和最大的一段子序列,并输出其和

    于  BZOJ, Splay, 数据结构 继续阅读

  9. 「BZOJ 3674」可持久化并查集加强版 - 可持久化线段树

    n n 个集合,m m 个操作:

    • 1 a b 合并 a a b b 所在集合;
    • 2 k 回到第 k k 次操作之后的状态(查询算作操作);
    • 3 a b 询问 a a b b 是否属于同一集合,是则输出 1 1 否则输出 0 0

    于  BZOJ, 可持久化并查集, 可持久化数据结构, 可持久化线段树, 数据结构, 线段树 继续阅读

  10. 「BZOJ 3673」可持久化并查集 - 可持久化线段树

    n n 个集合,m m 个操作:

    • 1 a b 合并 a a b b 所在集合;
    • 2 k 回到第 k k 次操作之后的状态(查询算作操作);
    • 3 a b 询问 a a b b 是否属于同一集合,是则输出 1 1 否则输出 0 0

    于  BZOJ, 可持久化并查集, 可持久化数据结构, 可持久化线段树, 数据结构, 线段树 继续阅读