Menci

眉眼如初,岁月如故

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


  1. 「BZOJ 3511」土地划分 - 最小割

    给定一张 n n 个点 m m 条边的无向连通图,初始时 1 1 号点属于集合 A A n n 号点属于集合 B B 。现在要将其他点划分进两个集合,并使得评分最高,评分方式如下:

    1. 对于点 i i ,划给 A A 集合得 VAi VA_i 分,划给 B B 集合得 VBi VB_i 分;
    2. 对于一条边 i i ,若它连接两个 A A 集合点,则得 EAi EA_i 分,若它连接两个 B B 集合点,则得 EBi EB_i 分,否则将扣除 ECi EC_i 分。

    于  BZOJ, Dinic, 安徽集训, 最小割, 网络流 继续阅读

  2. 「省选模拟赛」完美理论 - 最大权闭合图

    有两棵点集相同的树,顶点编号为 1n 1 \to n ,每个点都有一个权值,你需要选择一个点集的子集,使得这个子集在两棵树上都是一个连通块。你要选出权值和最大的子集,你只需要输出最大的权值和。

    于  Dinic, 安徽集训, 暴力, 最大权闭合图, 树形 DP, 网络流 继续阅读

  3. 「BZOJ 2296」随机种子 - 数论基础

    给定一个数 x x 0x106 0 \leq x \leq 10 ^ 6 ),求一个数 n n 满足:

    1. n n 的十进制表示中包含 0 ~ 9 的所有数;
    2. 0n1016 0 \leq n \leq 10 ^ {16}

    于  BZOJ, 安徽集训, 数论 继续阅读

  4. 「BZOJ 2038」小Z的袜子 - 莫队

    给一个数列 x1 x_1 ~ xn x_n ,给出 m m 个询问,每次询问 xi x_i ~ xj x_j 中,任选两个数相同的概率。

    于  BZOJ, 分块, 安徽集训, 莫队 继续阅读

  5. 「省选模拟赛」扔鸡蛋 - DP

    N N 层楼,第 M M 层以下扔鸡蛋会碎,你有 K K 个鸡蛋,找出这个 M M 需要多少次实验。

    于  DP, 二分查找, 安徽集训 继续阅读

  6. 「SCOI2015」小凸解密码 - set

    给定一个环形数列 A A 和运算符序列 C C ,可以从任意一个位置作为起点计算 B B ,方法为:

    1. B0=A0 B_0 = A_0
    2. Cx=+ C_x = + 时,
    3. Cx= C_x = * 时,

    每次可以修改 A A C C 中的某一个元素,询问以指定起点开始计算 B B 得到的环形数列 B B 中距离 B0 B_0 最远的零区间中距离 B0 B_0 最近的零的距离。

    于  BZOJ, SCOI, set, 乱搞, 安徽集训 继续阅读

  7. 「SCOI2015」小凸玩密室 - 树形 DP

    密室是一棵有 n n 个节点的完全二叉树,每个节点有一个灯泡。点亮所有灯泡即可逃出密室。每个灯泡有个权值 Ai A_i ,每条边也有个权值 Bi B_i 。点亮第 1 1 个灯泡不需要花费,之后每点亮 1 1 个新的灯泡 V V 的花费,等于上一个被点亮的灯泡 U U 到这个点 V V 的距离 Du,v D_{u, v} ,乘以这个点的权值 Av A_v 。在点灯的过程中,要保证任意时刻所有被点亮的灯泡必须连通,在点亮一个灯泡后必须先点亮其子树所有灯泡才能点亮其他灯泡。请告诉他们,逃出密室的最少花费是多少。

    于  BZOJ, DP, SCOI, 安徽集训, 树形 DP 继续阅读

  8. 「BZOJ 2143」飞飞侠 - 最短路

    飞国是一个 NM N * M 的矩形方阵,每个格子代表一个街区。飞国是没有交通工具的。飞侠完全靠地面的弹射装置来移动。每个街区都装有弹射装置。使用弹射装置是需要支付一定费用的。而且每个弹射装置都有自己的弹力。设第 i i 行第 j j 列的弹射装置有 Aij A_{ij} 的费用和 Bij B_{ij} 的弹力。并规定有相邻边的格子间距离是 1 1 。那么,任何飞侠都只需要在 (i,j) (i,j) 支付 Aij A_{ij} 的费用就可以任 意选择弹到距离不超过 Bij B_{ij} 的位置了。

    有三个飞侠,分别叫做 X、Y、Z。现在它们决定聚在一起玩,于是想往其中一人的位置集合。告诉你 3 3 个飞侠的坐标,求往哪里集合大家需要花的费用总和最低。

    于  BZOJ, Dijkstra, 安徽集训, 最短路 继续阅读

  9. 「SCOI2015」国旗计划 - 贪心 + 倍增

    A 国幅员辽阔,边境线上设有 M M 个边防站,顺时针编号 1 1 M M 。每名边防战士常驻两个边防站,并且善于在这两个边防站之间长途奔袭,我们称这两个边防站之间的路程是这个边防战士的奔袭区间。每名战士的奔袭区间都不会被其他战士的奔袭区间所包含。

    现在,局长希望知道,至少需要多少名战士,才能使得他们的奔袭区间覆盖全部的边境线。局长还希望知道对于每一名战士,在他必须参加国旗计划的前提下,至少需要多少名战士才能覆盖全部边境线。

    于  BZOJ, SCOI, 倍增, 安徽集训, 贪心 继续阅读

  10. 「SCOI2015」情报传递 - 离线 + Link-Cut Tree

    奈特公司有着庞大的情报网络。情报网络中共有 n n 名情报员。每名情报员有若干名下线,除 1 名大头目外其余 n1 n - 1 名情报员有且仅有 1 名上线。每名情报员只能与自己的上、下线联系,同时,情报网络中任意两名情报员一定能够通过情报网络传递情报。 奈特公司每天会派发以下两种任务中的一个任务:

    1. 搜集情报:指派 T T 号情报员搜集情报;
    2. 传递情报:将一条情报从 X X 号情报员传递给 Y Y 号情报员。

    情报员最初处于潜伏阶段,危险值为 0;一旦某个情报员开始搜集情报,他的危险值就会持续增加,每天增加 1 点危险值(开始搜集情报的当天危险值仍为 0,第 2 天危险值为 1,以此类推)。传递情报并不会使情报员的危险值增加。

    为了保证传递情报的过程相对安全,每条情报都有一个风险控制值 C C 。公司认为,传递这条情报的所有情报员中,危险值大于 C C 的情报员将对该条情报构成威胁。现在,奈特公司希望知道,对于每个传递情报任务,参与传递的情报员有多少个,其中对该条情报构成威胁的情报员有多少个。

    于  BZOJ, Link-Cut Tree, SCOI, 安徽集训, 数据结构, 离线, 高级数据结构 继续阅读