Menci

眉眼如初,岁月如故

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


  1. 「CQOI2015」任务查询系统 - 主席树

    最近实验室正在为其管理的超级计算机编制一套任务管理系统,而你被安排完成其中的查询部分。超级计算机中的任务用三元组 (Si,Ei,Pi) (S_i, E_i, P_i) 描述,(Si,Ei,Pi) (S_i, E_i, P_i) 表示任务从第 Si S_i 秒开始,在第 Ei E_i 秒后结束(第 Si S_i 秒和 Ei E_i 秒任务也在运行),其优先级为 Pi P_i 。同一时间可能有多个任务同时执行,它们的优先级可能相同,也可能不同。调度系统会经常向查询系统询问,第 Xi X_i 秒正在运行的任务中,优先级最小的 Ki K_i 个任务(即将任务按照优先级从小到大排序后取前 Ki K_i 个)的优先级之和是多少。特别的,如果 Ki K_i 大于第 Xi X_i 秒正在运行的任务总数,则直接回答第 Xi X_i 秒正在运行的任务优先级之和。上述所有参数均为整数,时间的范围在 1 1 n n 之间(包含 1 1 n n )。

    于  BZOJ, CQOI, 主席树, 数据结构 继续阅读

  2. 「CQOI2009」跳舞 - 网络流

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

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

  3. 「CQOI2011」动态逆序对 - CDQ

    对于序列 A A ,它的逆序对数定义为满足 i<j i < j ,且 Ai>Aj A_i > A_j 的数对 (i, j) (i,\ j) 的个数。给 1 1 n n 的一个排列,按照某种顺序依次删除 m m 个元素,你的任务是在每次删除一个元素之前统计整个序列的逆序对数。

    于  BZOJ, CDQ, CQOI, 分治, 数据结构, 树状数组 继续阅读

  4. 「CQOI2016」手机号码 - 数位 DP

    工具需要检测的号码特征有两个:号码中要出现至少 3 3 个相邻的相同数字,号码中不能同时出现 8 8 4 4 。号码必须同时包含两个特征才满足条件。满足条件的号码例如:3000988721 3000988721 23333333333 23333333333 14444101000 14444101000 。而不满足条件的号码例如:1015400080 1015400080 10010012022 10010012022

    手机号码一定是 11 11 位数,前不含前导的 0 0 。工具接收两个数 L L R R ,自动统计出 [L,R] [L, R] 区间内所有满足条件的号码数量。L L R R 也是 11 11 位的手机号码。

    于  BZOJ, CQOI, DP, 数位 DP 继续阅读

  5. 「CQOI2016」不同的最小割 - 分治 + 网络流

    对于一个图,某个对图中结点的划分将图中所有结点分成两个部分,如果结点 s s t t 不在同一个部分中,则称这个划分是关于 s s t t 的割。对于带权图来说,将所有顶点处在不同部分的边的权值相加所得到的值定义为这个割的容量,而 s s t t 的最小割指的是在关于 s s t t 的割中容量最小的割。

    考虑有 N N 个点的无向连通图中所有点对的最小割的容量,共能得到 个数值。这些数值中互不相同的有多少个呢?

    于  BZOJ, CQOI, Dinic, 分治, 网络流 继续阅读