Menci

眉眼如初,岁月如故

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


  1. 「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, 数据结构, 最近公共祖先, 树链剖分, 莫队 继续阅读

  2. 「NOIP2016」天天爱跑步 - 树链剖分 + 前缀和

    小 C 同学认为跑步非常有趣,于是决定制作一款叫做《天天爱跑步》的游戏。《天天爱跑步》是一个养成类游戏,需要玩家每天按时上线,完成打卡任务。

    这个游戏的地图可以看作一棵包含 n n 个结点和 n1 n - 1 条边的树,每条边连接两个结点,且任意两个结点存在一条路径互相可达。树上结点编号为从 1 1 n n 的连续正整数。

    现在有 m m 个玩家,第 i i 个玩家的起点为 Si S_i ,终点为 Ti T_i 。每天打卡任务开始时,所有玩家在第 0 0 秒同时从自己的起点出发,以每秒跑一条边的速度,不间断地沿着最短路径向着自己的终点跑去,跑到终点后该玩家就算完成了打卡任务。(由于地图是一棵树,所以每个人的路径是唯一的)

    小 C 想知道游戏的活跃度,所以在每个结点上都放置了一个观察员。在结点 j j 的观察员会选择在第 Wj W_j 秒观察玩家,一个玩家能被这个观察员观察到当且仅当该玩家在第 Wj W_j 秒也理到达了结点 j j 。小 C 想知道每个观察员会观察到多少人?

    注意:我们认为一个玩家到达自己的终点后该玩家就会结束游戏,他不能等待一段时间后再被观察员观察到。即对于把结点 j j 作为终点的玩家:若他在第 Wj W_j 秒前到达终点,则在结点 j j 的观察员不能观察到该玩家;若他正好在第 Wj W_j 秒到达终点,则在结点 j j 的观察员可以观察到这个玩家。

    于  NOIP, 前缀和, 树链剖分 继续阅读

  3. 「BZOJ 3881」Divljak - AC 自动机 + 树上路径并

    n n 个字符串 S1,S2,,Sn S_1, S_2, \ldots, S_n ,另有一个集合 T T ,初始为空。
    q q 次操作,每次向 T T 中添加一个字符串 P P ,或询问 T T 中有多少串能匹配 Si S_i

    于  AC 自动机, BZOJ, COCI, 字符串, 树上路径并, 树链剖分 继续阅读

  4. 「SDOI2014」旅行 - 树链剖分

    给一棵树,每个点有其初始颜色和权值,每次修改一个点的颜色或权值,查询路径上颜色与起点相同点权值的和或最大值。

    于  BZOJ, SDOI, 数据结构, 树链剖分 继续阅读

  5. 「HNOI2016」树 - 最近公共祖先 + 主席树

    小 A 想做一棵很大的树,但是他手上的材料有限,只好用点小技巧了。开始,小 A 只有一棵结点数为 N N 的树,结点的编号为 ,其中结点 1 1 为根;我们称这颗树为模板树。小 A 决定通过这棵模板树来构建一颗大树。构建过程如下:

    1. 将模板树复制为初始的大树;
    2. 以下 3,4,5 步循环执行 M M 次;
    3. 选择两个数字 a, b a,\ b ,其中 1aN 1 \leq a \leq N 1b 1 \leq b \leq 当前大树的结点数;
    4. 将模板树中以结点 a a 为根的子树复制一遍,挂到大树中结点 b b 的下方(也就是说,模板树中的结点 a a 为根的子树复制到大树中后,将成为大树中结点 b b 的子树);
    5. 将新加入大树的结点按照在模板树中编号的顺序重新编号。例如,假设在进行 4 步之前大树有 L L 个结点,模板树中以 a a 为根的子树共有 C C 个结点,那么新加入模板树的 C C 个结点在大树中的编号将是 ;大树中这 C C 个结点编号的大小顺序和模板树中对应的 C C 个结点的大小顺序是一致的。

    现在他想问你,树中一些结点对的距离是多少。

    于  BZOJ, COGS, HNOI, 主席树, 最近公共祖先, 树链剖分 继续阅读

  6. 「HNOI2016」网络 - 树链剖分 + DFS 序

    一个简单的网络系统可以被描述成一棵无根树。两个服务器进行数据的交互时,数据会经过连接这两个服务器的路径上的所有服务器(包括这两个服务器自身)。当路径上的某个服务器出现故障,无法正常运行时,数据便无法交互。此外,每个数据交互请求都有一个重要度。在每一个时刻,只有可能出现下列三种事件中的一种:

    1. 在某两个服务器之间出现一条新的数据交互请求;
    2. 某个数据交互结束请求;
    3. 某个服务器出现故障。

    系统会在任何故障发生后立即修复。也就是在出现故障的时刻之后,这个服务器依然是正常的。但在服务器产生故障时依然会对需要经过该服务器的数据交互请求造成影响。你的任务是在每次出现故障时,维护未被影响的请求中重要度的最大值。

    于  BZOJ, COGS, DFS 序, HNOI, 树链剖分 继续阅读

  7. 「SDOI2016」游戏 - 树链剖分

    Alice 和 Bob 在玩一个游戏。
    游戏在一棵有 n n 个点的树上进行。最初,每个点上都只有一个数字,那个数字是 123456789123456789 123456789123456789
    有时,Alice 会选择一条从 s s t t 的路径,在这条路径上的每一个点上都添加一个数字。对于路径上的一个点 r r ,若 r r s s 的距离是 dis dis ,那么 Alice 在点 r r 上添加的数字是 a×dis+b a \times dis + b
    有时,Bob 会选择一条从 s s t t 的路径。他需要先从这条路径上选择一个点,再从那个点上选择一个数字。
    Bob 选择的数字越小越好,但大量的数字让 Bob 眼花缭乱。Bob 需要你帮他找出他能够选择的最小的数字。

    于  BZOJ, COGS, SDOI, 数学, 数据结构, 最近公共祖先, 树链剖分, 线段树 继续阅读

  8. 用 std::stack 实现非递归 DFS

    众所周知,在有些省份(比如山东、河南),省选时使用 Windows 垃圾系统评测,而 Windows 下默认的系统栈非常小(只有 1M),这造成了有些 DFS 相关算法无法通过极端数据,而是发生『栈溢出』的错误。一种解决方法是使用非递归的 DFS。

    于  DFS, STL, Tarjan, 强连通分量, 树链剖分, 算法模板 继续阅读

  9. 「HAOI2015」树上操作 - 树链剖分 + DFS序

    有一棵点数为 N N 的树,以点 1 1 为根,且树点有边权。然后有 M M 个操作,分为三种:

    1. 把某个节点 x x 的点权增加 a a
    2. 把某个节点 x x 为根的子树中所有点的点权都增加 a a
    3. 询问某个节点 x x 到根的路径中所有点的点权和。

    于  BZOJ, DFS 序, HAOI, 树链剖分, 线段树 继续阅读

  10. 「省选模拟赛」染色 - 树链剖分

    给定一棵 n n 个节点的树,树的节点标号从 0 0 开始。每个节点可以是白色或黑色,初始时每个节点的颜色为白色。要求支持以下两种操作:

    1. 将节点 x x 涂黑;
    2. 查询节点 x x 到所有黑点距离之和。

    于  安徽集训, 数据结构, 树链剖分, 线段树, 高级数据结构 继续阅读