Menci

眉眼如初,岁月如故

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


  1. 「SDOI2010」古代猪文 - 费马小定理 + Lucas + CRT

    远古时期猪王国有 n n 个文字,现有的文字数量为远古时期的 1/k 1 / k k k n n 的一个正约数),剩余的 n/k n / k 个文字有很多种情况,假设有 p p 种情况,则研究这些文字的代价为 gp g ^ p ,求这个代价对 999911659 999911659 取模后的结果。

    于  BZOJ, CRT, Lucas 定理, SDOI, 费马小定理 继续阅读

  2. 「SDOI2013」随机数生成器 - 数学 + BSGS

    给定 p p a a b b x1 x_1 ,现有一数列

    求最小的 i i 满足 xi=t x_i = t

    于  BSGS, BZOJ, SDOI, 数学, 数论 继续阅读

  3. 「SDOI2008」Sandy 的卡片 - 差分 + SAM

    相同的定义为:两个子串长度相同且一个串的全部元素加上一个数就会变成另一个串。给 n n 个串,求它们相同的子串最大长度。

    于  BZOJ, SAM, SDOI, 差分 继续阅读

  4. 「SDOI2014」LIS - 最小割 + 网络流退流

    给定序列 A A ,序列中的每一项 Ai A_i 有删除代价 Bi B_i 和附加属性 Ci C_i 。请删除若干项,使得 A A 的最长上升子序列长度减少至少 1 1 ,且付出的代价之和最小,并输出方案。

    如果有多种方案,请输出将删去项的附加属性排序 Ci C_i 之后,字典序最小的一种。

    于  BZOJ, SDOI, 最小割, 网络流 继续阅读

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

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

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

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

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

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

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

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

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

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

  8. 「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, 数据结构, 线段树 继续阅读

  9. 「SDOI2009」晨跑 - 费用流

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

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

  10. 「SDOI2010」地精部落 - DP

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

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

    于  BZOJ, DP, SDOI 继续阅读