Menci

眉眼如初,岁月如故

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


  1. 「NOIP2016」愤怒的小鸟 - 状态压缩 + BFS

    Kiana 最近沉迷于一款神奇的游戏无法自拔。

    简单来说,这款游戏是在一个平面上进行的。

    有一架弹弓位于 (0,0) (0, 0) 处,每次 Kiana 可以用它向第一象限发射一只红色的小鸟,小鸟们的飞行轨迹均为形如 y=ax2+bx y = ax ^ 2 + bx 的曲线,其中 a a b b 是 Kiana 指定的参数,且必须满足 a<0 a < 0

    当小鸟落回地面(即 x x 轴)时,它就会瞬间消失。

    在游戏的某个关卡里,平面的第一象限中有 n n 只绿色的小猪,其中第 i i 只小猪所在的坐标为 (xi,yi) (x_i, y_i)

    如果某只小鸟的飞行轨迹经过了(xi,yi) (x_i, y_i) ,那么第 i i 只小猪就会被消灭掉,同时小鸟将会沿着原先的轨迹继续飞行;

    如果一只小鸟的飞行轨迹没有经过(xi,yi) (x_i, y_i) ,那么这只小鸟飞行的全过程就不会对第 i i 只小猪产生任何影响。

    例如,若两只小猪分别位于 (1,3) (1, 3) (3,3) (3, 3) ,Kiana 可以选择发射一只飞行轨迹为 y=x2+4x y = -x ^ 2 + 4x 的小鸟,这样两只小猪就会被这只小鸟一起消灭。

    而这个游戏的目的,就是通过发射小鸟消灭所有的小猪。

    这款神奇游戏的每个关卡对 Kiana 来说都很难,所以 Kiana 还输入了一些神秘的指令,使得自己能更轻松地完成这个游戏。这些指令将在「输入格式」中详述。

    假设这款游戏一共有 T T 个关卡,现在 Kiana 想知道,对于每一个关卡,至少需要发射多少只小鸟才能消灭所有的小猪。由于她不会算,所以希望由你告诉她。

    于  BFS, NOIP, 搜索, 状态压缩 继续阅读

  2. 「NOIP2016」蚯蚓 - 队列

    本题中,我们将用符号 c \lfloor c \rfloor 表示对 c c 向下取整,例如:3.0=3.1=3.9=3 \lfloor 3.0 \rfloor = \lfloor 3.1 \rfloor = \lfloor 3.9 \rfloor = 3

    蛐蛐国最近蚯蚓成灾了!隔壁跳蚤国的跳蚤也拿蚯蚓们没办法,蛐蛐国王只好去请神刀手来帮他们消灭蚯蚓。

    蛐蛐国里现在共有 n n 只蚯蚓(n n 为正整数)。每只蚯蚓拥有长度,我们设第 i i 只蚯蚓的长度为 ai a_i i=1,2,,n i = 1, 2, \ldots , n ),并保证所有的长度都是非负整数(即:可能存在长度为 0 0 的蚯蚓)。

    每一秒,神刀手会在所有的蚯蚓中,准确地找到最长的那一只(如有多个则任选一个)将其切成两半。神刀手切开蚯蚓的位置由常数 p p (是满足 0<p<1 0 < p < 1 的有理数)决定,设这只蚯蚓长度为 x x ,神刀手会将其切成两只长度分别为 px \lfloor px \rfloor xpx x - \lfloor px \rfloor 的蚯蚓。特殊地,如果这两个数的其中一个等于 0 0 ,则这个长度为 0 0 的蚯蚓也会被保留。此外,除了刚刚产生的两只新蚯蚓,其余蚯蚓的长度都会增加 q q (是一个非负整常数)。

    蛐蛐国王知道这样不是长久之计,因为蚯蚓不仅会越来越多,还会越来越长。蛐蛐国王决定求助于一位有着洪荒之力的神秘人物,但是救兵还需要 m m 秒才能到来 ……(m m 为非负整数)

    蛐蛐国王希望知道这 m m 秒内的战况。具体来说,他希望知道:

    • m m 秒内,每一秒被切断的蚯蚓被切断前的长度(有 m m 个数);
    • m m 秒后,所有蚯蚓的长度(有 n+m n + m 个数)。

    蛐蛐国王当然知道怎么做啦!但是他想考考你 ……

    于  NOIP, 队列 继续阅读

  3. 「NOIP2016」组合数问题 - 递推 + 前缀和

    组合数表示的是从 n n 个物品中选出 m m 个物品的方案数。举个例子,从 (1,2,3) (1, 2, 3) 三个物品中选择两个物品可以有 (1,2) (1, 2) (1,3) (1, 3) (2,3) (2, 3) 这三种选择方法。

    根据组合数的定义,我们可以给出计算组合数的一般公式:

    Cnm=n!m!(nm)! C_n ^ m = \frac{n!}{m!(n - m)!}

    其中 n!=1×2××n n! = 1 \times 2 \times \cdots \times n

    小葱想知道如果给定 n n m m k k ,对于所有的 0in 0 \leq i \leq n 0jmin(i,m) 0 \leq j \leq \min(i, m) 有多少对 (i,j) (i, j) 满足是 k k 的倍数。

    于  NOIP, 前缀和, 数学, 组合数 继续阅读

  4. 「NOIP2016」换教室 - Floyd + DP + 概率与期望

    对于刚上大学的牛牛来说,他面临的第一个问题是如何根据实际情况申请合适的课程。

    在可以选择的课程中,有 2n 2n 节课程安排在 n n 个时间段上。在第 i i 1in 1 \leq i \leq n )个时间段上,两节内容相同的课程同时在不同的地点进行,其中,牛牛预先被安排在教室 ci c_i 上课,而另一节课程在教室 di d_i 进行。

    在不提交任何申请的情况下,学生们需要按时间段的顺序依次完成所有的 n n 节安排好的课程。如果学生想更换第i节课程的教室,则需要提出申请。若申请通过,学生就可以在第 i i 个时间段去教室 di d_i 上课,否则仍然在教室 ci c_i 上课。

    由于更换教室的需求太多,申请不一定能获得通过。通过计算,牛牛发现申请更换第 i i 节课程的教室时,申请被通过的概率是一个已知的实数 ki k_i ,并且对于不同课程的申请,被通过的概率是互相独立的。

    学校规定,所有的申请只能在学期开始前一次性提交,并且每个人只能选择至多 m m 节课程进行申请。这意味着牛牛必须一次性决定是否申请更换每节课的教室,而不能根据某些课程的申请结果来决定其他课程是否申请;牛牛可以申请白己最希望更换教室的 m m 门课程,也可以不用完这 m m 个申请的机会,甚至可以一门课程都不申请。

    因为不同的课程可能会被安排在不同的教室进行,所以牛牛需要利用课问时间从一间教室赶到另一间教室。

    牛牛所在的大学有 v v 个教室,有 e e 条道路。每条道路连接两间教室,并且是可以双向通行的。由于道路的长度和拥堵程度不同,通过不同的道路耗费的体力可能会有所不同。当第 i i 1in1 1 \leq i \leq n - 1 )节课结束后,牛牛就会从这节课的教室出发,选择一条耗费体力最少的路径前往下一节课的教室。

    现在牛牛想知道,申请哪几门课程可以使他因在教室问移动耗费的体力值的总和的期望值最小,请你帮他求出这个最小值。

    于  DP, Floyd, NOIP, 概率与期望 继续阅读

  5. 「NOIP2016」天天爱跑步 - 树链剖分 + 前缀和

    小 C 同学认为跑步非常有趣,于是决定制作一款叫做《天天爱跑步》的游戏。《天天爱跑步》是一个养成类游戏,需要玩家每天按时上线,完成打卡任务。

    这个游戏的地图可以看作一棵包含 n n 个结点和 n1 n - 1 条边的树,每条边连接两个结点,且任意两个结点存在一条路径互相可达。树上结点编号为从 1 1 n n 的连续正整数。

    现在有 m m 个玩家,第 i i 个玩家的起点为 Si S_i ,终点为 Ti T_i 。每天打卡任务开始时,所有玩家在第 0 0 秒同时从自己的起点出发,以每秒跑一条边的速度,不间断地沿着最短路径向着自己的终点跑去,跑到终点后该玩家就算完成了打卡任务。(由于地图是一棵树,所以每个人的路径是唯一的)

    小 C 想知道游戏的活跃度,所以在每个结点上都放置了一个观察员。在结点 j j 的观察员会选择在第 Wj W_j 秒观察玩家,一个玩家能被这个观察员观察到当且仅当该玩家在第 Wj W_j 秒也理到达了结点 j j 。小 C 想知道每个观察员会观察到多少人?

    注意:我们认为一个玩家到达自己的终点后该玩家就会结束游戏,他不能等待一段时间后再被观察员观察到。即对于把结点 j j 作为终点的玩家:若他在第 Wj W_j 秒前到达终点,则在结点 j j 的观察员不能观察到该玩家;若他正好在第 Wj W_j 秒到达终点,则在结点 j j 的观察员可以观察到这个玩家。

    于  NOIP, 前缀和, 树链剖分 继续阅读

  6. 「NOIP2016」玩具谜题 - 模拟

    小南有一套可爱的玩具小人,它们各有不同的职业。

    有一天,这些玩具小人把小南的眼镜藏了起来。小南发现玩具小人们围成了一个圈,它们有的面朝圈内,有的面朝圈外。

    这时 singer 告诉小南一个谜题:「眼镜藏在我左数第 3 3 个玩具小人的右数第 1 1 个玩具小人的左数第 2 2 个玩具小人那里。」

    小南发现,这个谜题中玩具小人的朝向非常关键, 因为朝内和朝外的玩具小人的左右方向是相反的:面朝圈内的玩具小人,它的左边是顺时针方向,右边是逆时针方向;而面向圈外的玩具小人,它的左边是逆时针方向,右边是顺时针方向。

    小南一边艰难地辨认着玩具小人,一边数着:

    singer 朝内,左数第 3 3 个是 archer
    archer 朝外,右数第 1 1 个是 thinker
    thinker 朝外,左数第 2 2 个是 writer

    所以眼镜藏在 writer 这里!

    虽然成功找回了眼镜,但小南并没有放心。如果下次有更多的玩具小人藏他的眼镜,或是谜题的长度更长,他可能就无法找到眼镜了。所以小南希望你写程序帮他解决类似的谜题。这样的谜题具体可以描述为:

    n n 个玩具小人围成一圈,已知它们的职业和朝向。现在第 1 1 个玩具小人告诉小南一个包含 m m 条指令的谜题。其中第 i i 条指令形如「左数/右数第 si s_i 个玩具小人」。你需要输出依次数完这些指令后,到达的玩具小人的职业。

    于  NOIP, 模拟 继续阅读

  7. 「NOIP2012」疫情控制 - 二分 + 倍增 + 贪心

    H 国有 n n 个城市,这 n n 个城市用 n1 n - 1 条双向道路相互连通构成一棵树,1 1 号城市是首都,也是树中的根节点。

    H 国的首都爆发了一种危害性极高的传染病。当局为了控制疫情,不让疫情扩散到边境城市(叶子节点所表示的城市),决定动用军队在一些城市建立检查点,使得从首都到边境城市的每一条路径上都至少有一个检查点,边境城市也可以建立检查点。但特别要注意的是,首都是不能建立检查点的。

    现在,在 H 国的一些城市中已经驻扎有军队,且一个城市可以驻扎多个军队。一支军队可以在有道路连接的城市间移动,并在除首都以外的任意一个城市建立检查点,且只能在一个城市建立检查点。一支军队经过一条道路从一个城市移动到另一个城市所需要的时间等于道路的长度(单位:小时)。

    请问最少需要多少个小时才能控制疫情。注意,不同的军队可以同时移动。

    于  CodeVS, NOIP, 二分, 倍增, 贪心 继续阅读

  8. 「NOIP2010」引水入城 - BFS + DP

    在一个遥远的国度,一侧是风景秀美的湖泊,另一侧则是漫无边际的沙漠。该国的行政区划十分特殊,刚好构成一个 N N M M 列的矩形,如上图所示,其中每个格子都代表一座城市,每座城市都有一个海拔高度。

    为了使居民们都尽可能饮用到清澈的湖水,现在要在某些城市建造水利设施。水利设施有两种,分别为蓄水厂和输水站。蓄水厂的功能是利用水泵将湖泊中的水抽取到所在城市的蓄水池中。因此,只有与湖泊毗邻的第 1 1 行的城市可以建造蓄水厂。而输水站的功能则是通过输水管线利用高度落差,将湖水从高处向低处输送。故一座城市能建造输水站的前提,是存在比它海拔更高且拥有公共边的相邻城市,已经建有水利设施。

    由于第 N N 行的城市靠近沙漠,是该国的干旱区,所以要求其中的每座城市都建有水利设施。那么,这个要求能否满足呢?如果能,请计算最少建造几个蓄水厂;如果不能,求干旱区中不可能建有水利设施的城市数目。

    于  BFS, CodeVS, DP, NOIP, 线性 DP 继续阅读

  9. 「NOIP2012」开车旅行 - 倍增

    小 A 和小 B 决定利用假期外出旅行,他们将想去的城市从 1 1 N N 编号,且编号较小的城市在编号较大的城市的西边,已知各个城市的海拔高度互不相同,记城市 i i 的海拔高度为 Hi H_i ,城市 i i 和城市 j j 之间的距离 d(i,j) d(i, j) 恰好是这两个城市海拔高度之差的绝对值,即

    旅行过程中,小 A 和小 B 轮流开车,第一天小 A 开车,之后每天轮换一次。他们计划选择一个城市 S S 作为起点,一直向东行驶,并且最多行驶 X X 公里就结束旅行。小 A 和小 B 的驾驶风格不同,小 B 总是沿着前进方向选择一个最近的城市作为目的地,而小 A 总是沿着前进方向选择第二近的城市作为目的地(注意:本题中如果当前城市到两个城市的距离相同,则认为离海拔低的那个城市更近)。如果其中任何一人无法按照自己的原则选择目的城市,或者到达目的地会使行驶的总距离超出 X X 公里,他们就会结束旅行。

    在启程之前,小 A 想知道两个问题:

    1. 对于一个给定的 X=X0 X = X_0 ,从哪一个城市出发,小 A 开车行驶的路程总数与小 B 行驶的路程总数的比值最小(如果小 B 的行驶路程为 0 0 ,此时的比值可视为无穷大,且两个无穷大视为相等)。如果从多个城市出发,小 A 开车行驶的路程总数与小 B 行驶的路程总数的比值都最小,则输出海拔最高的那个城市。
    2. 对任意给定的 X=Xi X = X_i 和出发城市 Si S_i ,小 A 开车行驶的路程总数以及小 B 行驶的路程总数。

    于  CodeVS, NOIP, 倍增 继续阅读

  10. 「NOIP2013」华容道 - BFS + SPFA

    1. 在一个 n×m n \times m 棋盘上有 n×m n\times m 个格子,其中有且只有一个格子是空白的,其余 n×m1 n \times m - 1 个格子上每个格子上有一个棋子,每个棋子的大小都是 1×1 1 \times 1 的;
    2. 有些棋子是固定的,有些棋子则是可以移动的;
    3. 任何与空白的格子相邻(有公共的边)的格子上的棋子都可以移动到空白格子上。游戏的目的是把某个指定位置可以活动的棋子移动到目标位置。

    给定一个棋盘,游戏可以玩 q q 次,当然,每次棋盘上固定的格子是不会变的,但是棋盘上空白的格子的初始位置、指定的可移动的棋子的初始位置和目标位置却可能不同。第 i i 次玩的时候,空白的格子在第 EXi EX_i 行第 EYi EY_i 列,指定的可移动棋子的初始位置为第 SXi SX_i 行第 SYi SY_i 列,目标位置为第 TXi TX_i 行第 TYi TY_i 列。

    假设小 B 每秒钟能进行一次移动棋子的操作,而其他操作的时间都可以忽略不计。请你告诉小 B 每一次游戏所需要的最少时间,或者告诉他不可能完成游戏。

    于  BFS, CodeVS, NOIP, SPFA, 搜索, 最短路 继续阅读