Menci

眉眼如初,岁月如故

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


  1. 「SCOI2005」王室联邦 - 树分块

    他想把他的国家划分成若干个省,每个省都由他们王室联邦的一个成员来管理。他的国家有 n n 个城市,编号为 1n 1 \ldots n 。一些城市之间有道路相连,任意两个不同的城市之间有且仅有一条直接或间接的道路。

    每个省至少要有 B B 个城市,最多只有 3B 3B 个城市。

    每个省必须有一个省会,这个省会可以位于省内,也可以在该省外。但是该省的任意一个城市到达省会所经过的道路上的城市(除了最后一个城市,即该省省会)都必须属于该省。

    一个城市可以作为多个省的省会。

    于  BZOJ, SCOI, 分块, 数据结构, 树分块 继续阅读

  2. 「SCOI2009」游戏 - 群论 + 背包 DP

    windy 学会了一种游戏。对于 1 1 N N N N 个数字,都有唯一且不同的 1 1 N N 的数字与之对应。最开始 windy 把数字按顺序 1,2,3,,N 1, 2, 3, \ldots, N 写一排在纸上。然后再在这一排下面写上它们对应的数字。然后又在新的一排下面写上它们对应的数字。如此反复,直到序列再次变为 1,2,3,,N 1, 2, 3, \ldots, N

    如:1,2,3,4,5,6 1, 2, 3, 4, 5, 6 对应的关系为

    {122331455466 \begin{cases} 1 \rightarrow 2 \\ 2 \rightarrow 3 \\ 3 \rightarrow 1 \\ 4 \rightarrow 5 \\ 5 \rightarrow 4 \\ 6 \rightarrow 6 \end{cases}

    windy 的操作如下:

    这时,我们就有若干排 1 1 N N 的排列,上例中有 7 7 排。现在 windy 想知道,对于所有可能的对应关系,有多少种可能的排数。

    于  BZOJ, DP, SCOI, 数学, 群论, 背包 DP 继续阅读

  3. 「SCOI2009」生日快乐 - 搜索

    windy 的生日到了,为了庆祝生日,他的朋友们帮他买了一个边长分别为 X X Y Y 的矩形蛋糕。现在包括 windy,一共有 N N 个人来分这块大蛋糕,要求每个人必须获得相同面积的蛋糕。windy 主刀,每一切只能平行于一块蛋糕的一边(任意一边),并且必须把这块蛋糕切成两块。这样,要切成 N N 块蛋糕,windy 必须切 N1 N - 1 次。为了使得每块蛋糕看起来漂亮,我们要求 N N 块蛋糕的长边与短边的比值的最大值最小。你能帮助 windy 求出这个比值么?

    于  BZOJ, DFS, SCOI, 搜索 继续阅读

  4. 「SCOI2012」喵星球上的点名 - AC 自动机

    假设课堂上有 N N 个喵星人,每个喵星人的名字由姓和名构成。喵星球上的老师会选择 M M 个串来点名,每次读出一个串的时候,如果这个串是一个喵星人的姓或名的子串,那么这个喵星人就必须答到。

    统计每次点名的时候有多少喵星人答到,以及 M M 次点名结束后每个喵星人答到多少次。

    于  AC 自动机, BZOJ, SCOI, 字符串 继续阅读

  5. 「SCOI2007」蜥蜴 - 网络流

    在一个 r r c c 列的网格地图中有一些高度不同的石柱,一些石柱上站着一些蜥蜴,你的任务是让尽量多的蜥蜴逃到边界外。

    每行每列中相邻石柱的距离为 1 1 ,蜥蜴的跳跃距离是 d d ,即蜥蜴可以跳到平面曼哈顿距离不超过 d d 的任何一个石柱上。

    石柱都不稳定,每次当蜥蜴跳跃时,所离开的石柱高度减 1 1 (如果仍然落在地图内部,则到达的石柱高度不变),如果该石柱原来高度为 1 1 ,则蜥蜴离开后消失。以后其他蜥蜴不能落脚。

    任何时刻不能有两只蜥蜴在同一个石柱上。

    于  BZOJ, Dinic, SCOI, 网络流 继续阅读

  6. 「SCOI2009」粉刷匠 - 背包 DP

    windy 有 N N 条木板需要被粉刷。每条木板被分为 M M 个格子。 每个格子要被刷成红色或蓝色。 windy 每次粉刷,只能选择一条木板上一段连续的格子,然后涂上一种颜色。每个格子最多只能被粉刷一次。如果 windy 只能粉刷 T T 次,他最多能正确粉刷多少格子?

    一个格子如果未被粉刷或者被粉刷错颜色,就算错误粉刷。

    于  BZOJ, DP, SCOI, 背包 DP 继续阅读

  7. 「SCOI2003」字符串折叠 - 区间 DP

    折叠的定义如下:

    1. 一个字符串可以看成它自身的折叠。
    2. X(S) X(S) X(X>1) X(X > 1) S S 连接在一起的串的折叠。
    3. 如果 A A 的折叠,B B 的折叠,则 AB AB 的折叠。

    给一个字符串,求它的最短折叠。

    于  BZOJ, DP, SCOI, 区间 DP 继续阅读

  8. 「SCOI2009」windy 数 - 数位 DP

    windy 定义了一种 windy 数。不含前导零且相邻两个数字之差至少为 2 2 的正整数被称为 windy 数。

    windy 想知道,在 A A B B 之间,包括 A A B B ,总共有多少个 windy 数?

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

  9. 「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, 乱搞, 安徽集训 继续阅读

  10. 「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 继续阅读