Menci

眉眼如初,岁月如故

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


  1. 「SDOI2013」森林 - LCA + 主席树 + 启发式合并

    森林中有 n n 个点,m m 条边,每个点有点权,执行 T T 次操作:

    1. 查询两点间点权的第 k k 小;
    2. 连接两个点,保证图在操作后仍然为森林。

    于  BZOJ, SDOI, 主席树, 启发式合并, 并查集, 最近公共祖先 继续阅读

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

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

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

  3. 「SDOI2008」校门外的区间 - 线段树

    受校门外的树这道经典问题的启发,A 君根据基本的离散数学的知识,抽象出 5 5 种运算维护集合 S S S S 初始为空)并最终输出 S S 。现在,请你完成这道校门外的树之难度增强版 —— 校门外的区间。

    5 5 种运算如下:

    1. A=AB A = A \cup B
    2. A=AB A = A \cap B
    3. A={xxA and xB} A = \{ x \mid x \in A \ \mathrm{and} \ x \notin B \}
    4. A={xxA and xB} A = \{ x \mid x \notin A \ \mathrm{and} \ x \in B \}
    5. A={xxA and xB}{xxA and xB} A = \{ x \mid x \in A \ \mathrm{and} \ x \notin B \} \cup \{ x \mid x \notin A \ \mathrm{and} \ x \in B \}

    于  BZOJ, SDOI, 数据结构, 线段树 继续阅读

  4. 「SDOI2009」晨跑 - 费用流

    现在给出一张地图,地图中包含 N N 个十字路口和 M M 条街道,Elaxia 只能从一个十字路口跑向另外一个十字路口,街道之间只在十字路口处相交。Elaxia 每天从寝室出发跑到学校,保证寝室编号为 1 1 ,学校编号为 N N 。 Elaxia 的晨跑计划是按周期(包含若干天)进行的,由于他不喜欢走重复的路线,所以在一个周期内,每天的晨跑路线都不会相交(在十字路口处),寝室和学校不算十字路口。
    他希望在一个周期内跑的路程尽量短,但是又希望训练周期包含的天数尽量长。

    于  BZOJ, Edmonds-Karp, SDOI, 网络流, 费用流 继续阅读

  5. 「SDOI2010」地精部落 - DP

    我们称一个排列是合法的,当且仅当每一个数都满足这个数比它相邻的数都要大或都要小。

    求长度为 N N 的合法排列数量。

    于  BZOJ, DP, SDOI 继续阅读

  6. 「SDOI2011」计算器 - 快速幂 + EXGCD + BSGS

    你被要求设计一个计算器完成以下三项任务:

    1. 给定 y y z z p p ,计算 的值;
    2. 给定 y y z z p p ,计算满足 的最小非负整数 x x
    3. 给定 y y z z p p ,计算满足 的最小非负整数 x x

    于  BSGS, BZOJ, EXGCD, SDOI, 快速幂, 数学 继续阅读

  7. 「SDOI2015」序列统计 - 生成函数 + NTT

    小 C 有一个集合 S S ,里面的元素都是小于 M M 的非负整数。他用程序编写了一个数列生成器,可以生成一个长度为 N N 的数列,数列中的每个数都属于集合 S S

    小 C 用这个生成器生成了许多这样的数列。但是小 C 有一个问题需要你的帮助:给定整数 x x ,求所有可以生成出的,且满足数列中所有数的乘积 的值等于 x x 的不同的数列的有多少个。小 C 认为,两个数列 {Ai} \{ A_i \} {Bi} \{B_i\} 不同,当且仅当至少存在一个整数 i i ,满足 AiBi A_i \neq B_i 。另外,小 C 认为这个问题的答案可能很大,因此他只需要你帮助他求出答案 的值就可以了。

    于  BZOJ, FFT, NTT, SDOI, 原根, 快速幂, 数学, 生成函数 继续阅读

  8. 「SDOI2016」储能表 - 二进制

    有一个 n n m m 列的表格,行从 0 0 n1 n - 1 编号,列从 0 0 m1 m - 1 编号。
    每个格子都储存着能量。最初,第 i i 行第 j j 列的格子储存着 点能量。所以,整个表格储存的总能量是,

    随着时间的推移,格子中的能量会渐渐减少。一个时间单位,每个格子中的能量都会减少 1 1 。显然,一个格子的能量减少到 0 0 之后就不会再减少了。
    也就是说,k k 个时间单位后,整个表格储存的总能量是,

    给出一个表格,求 k k 个时间单位后它储存的总能量。
    由于总能量可能较大,输出时对 p p 取模。

    于  BZOJ, COGS, SDOI, 二进制, 位运算, 异或 继续阅读

  9. 「SDOI2016」征途 - 斜率优化 DP

    Pine 开始了从 S S 地到 T T 地的征途。
    S S 地到 T T 地的路可以划分成 n n 段,相邻两段路的分界点设有休息站。
    Pine 计划用 m m 天到达 T T 地。除第 m m 天外,每一天晚上 Pine 都必须在休息站过夜。所以,一段路必须在同一天中走完。
    Pine 希望每一天走的路长度尽可能相近,所以他希望每一天走的路的长度的方差尽可能小。
    帮助 Pine 求出最小方差是多少。

    设方差是 v v ,可以证明,v×m2 v \times m ^ 2 是一个整数。为了避免精度误差,输出结果时输出 v×m2 v \times m ^ 2

    于  BZOJ, COGS, DP, SDOI, 单调队列, 斜率优化 继续阅读

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