Chro's Blog

だから 迷わない 頑張ろう

Those things that hurt, instruct.


  1. 「BZOJ 4200」「UOJ 132」「NOI2015」小园丁与老司机

    小园丁 Mr. S 负责看管一片田野,田野可以看作一个二维平面。田野上有 n 棵许愿树,编号 1,2,3,…,n,每棵树可以看作平面上的一个点,其中第 i 棵树 (1≤i≤n) 位于坐标 (xi,yi)。任意两棵树的坐标均不相同。 老司机 Mr. P 从原点 (0,0) 驾车出发,进行若干轮行动。每一轮,Mr. P 首先选择任意一个满足以下条件的方向: 为左、右、上、左上 45° 、右上 45°…

    BZOJ, UOJ, 上下界最小流, 动态规划, 网络流 继续阅读

  2. 「BZOJ 4654」「UOJ 223」「NOI2016」国王饮水记

    Description跳蚤国有 n 个城市,伟大的跳蚤国王居住在跳蚤国首都中,即 1 号城市中。跳蚤国最大的问题就是饮水问题,由于首都中居住的跳蚤实在太多,跳蚤国王又体恤地将分配给他的水也给跳蚤国居民饮用,这导致跳蚤国王也经常喝不上水。于是,跳蚤国在每个城市都修建了一个圆柱形水箱,这些水箱完全相同且足够高。一个雨天后,第 i 个城市收集到了高度为 hi 的水。由于地理和天气因素的影响,任何两个不同…

    BZOJ, UOJ, 决策单调性, 动态规划 继续阅读

  3. 「BZOJ 4585」「UOJ 205」「APIO2016」Fireworks

    烟花表演是最引人注目的节日活动之一。在表演中,所有的烟花必须同时爆炸。为了确保安全,烟花被安置在远离开关的位置上,通过一些导火索与开关相连。导火索的连接方式形成一棵树,烟花是树叶,如图所示。火花从开关出发,沿导火索移动。每当火花抵达一个分叉点时,它会扩散到与之相连的所有导火索,继续燃烧。导火索燃烧的速度是一个固定常数。图中展示了六枚烟花 {E1,E2,…,E6} 的连线布局,以及每根导火索的长度。…

    BZOJ, UOJ, 可合并堆, 树型 DP 继续阅读

  4. 「BZOJ 4650」「UOJ 219」「NOI2016」优秀的拆分

    如果一个字符串可以被拆分为 AABB 的形式,其中 A 和 B 是任意非空字符串,则我们称该字符串的这种拆分是优秀的。 例如,对于字符串 aabaabaa,如果令 $A = \mathrm{aab}$,$B = \mathrm{a}$,我们就找到了这个字符串拆分成 AABB 的一种方式。 一个字符串可能没有优秀的拆分,也可能存在不止一种优秀的拆分。比如我们令 $A=\mathrm{a}$,$B=\…

    BZOJ, UOJ, 乱搞, 字符串哈希 继续阅读

  5. 「BZOJ 4197」「UOJ 129」「NOI2015」寿司晚宴

    Description为了庆祝 NOI 的成功开幕,主办方为大家准备了一场寿司晚宴。小 G 和小 W 作为参加 NOI 的选手,也被邀请参加了寿司晚宴。 在晚宴上,主办方为大家提供了 n−1 种不同的寿司,编号 1,2,3,…,n−1,其中第 i 种寿司的美味度为 i+1 (即寿司的美味度为从 2 到 n)。 现在小 G 和小 W 希望每人选一些寿司种类来品尝,他们规定一种品尝方案为不和谐的当且仅…

    BZOJ, UOJ, 状压 DP 继续阅读

  6. 「BZOJ 3669」「UOJ 3」「NOI2014」魔法森林

    Description为了得到书法大家的真传,小E同学下定决心去拜访住在魔法森林中的隐士。魔法森林可以被看成一个包含个N节点M条边的无向图,节点标号为1..N,边标号为1..M。初始时小E同学在号节点1,隐士则住在号节点N。小E需要通过这一片魔法森林,才能够拜访到隐士。 魔法森林中居住了一些妖怪。每当有人经过一条边的时候,这条边上的妖怪就会对其发起攻击。幸运的是,在号节点住着两种守护精灵:A型守护…

    BZOJ, Link-Cut Tree, UOJ 继续阅读

  7. 「UOJ 265」「NOIP2016」愤怒的小鸟

    Kiana 最近沉迷于一款神奇的游戏无法自拔。 简单来说,这款游戏是在一个平面上进行的。 有一架弹弓位于 (0,0) 处,每次 Kiana 可以用它向第一象限发射一只红色的小鸟,小鸟们的飞行轨迹均为形如 y=ax2+bx 的曲线,其中 a,b 是 Kiana 指定的参数,且必须满足 a<0,a,b 都是实数。 当小鸟落回地面(即 x 轴)时,它就会瞬间消失。 在游戏的某个关卡里,平面的第一象…

    UOJ, 状压 DP 继续阅读

  8. 「UOJ 264」「NOIP2016」蚯蚓

    本题中,我们将用符号 ⌊c⌋ 表示对 c 向下取整,例如:⌊3.0⌋=⌊3.1⌋=⌊3.9⌋=3。 蛐蛐国最近蚯蚓成灾了!隔壁跳蚤国的跳蚤也拿蚯蚓们没办法,蛐蛐国王只好去请神刀手来帮他们消灭蚯蚓。 蛐蛐国里现在共有 n 只蚯蚓(n 为正整数)。每只蚯蚓拥有长度,我们设第 i 只蚯蚓的长度为 ai (i=1,2,…,n),并保证所有的长度都是非负整数(即:可能存在长度为 0 的蚯蚓)。 每一秒,神刀…

    UOJ 继续阅读

  9. 「UOJ 263」「NOIP2016」组合数问题

    组合数 C(n, m) 表示的是从 n 个物品中选出 m 个物品的方案数。举个例子,从 (1,2,3) 三个物品中选择两个物品可以有 (1,2),(1,3),(2,3) 这三种选择方法。根据组合数的定义,我们可以给出计算组合数 C(n, m) 的一般公式: C(n, m) = n! / (m! * (n − m)!) 其中 n!=1×2×⋯×n;特别地,定义 0!=1。 小葱想知道如果给定 n,m…

    UOJ, 组合数 继续阅读

  10. 「UOJ 262」「NOIP2016」换教室

    对于刚上大学的牛牛来说,他面临的第一个问题是如何根据实际情况申请合适的课程。 在可以选择的课程中,有 2n 节课程安排在 n 个时间段上。在第 i(1≤i≤n)个时间段上,两节内容相同的课程同时在不同的地点进行,其中,牛牛预先被安排在教室 ci 上课,而另一节课程在教室 di 进行。 在不提交任何申请的情况下,学生们需要按时间段的顺序依次完成所有的 n 节安排好的课程。如果学生想更换第 i 节课程…

    UOJ, 动态规划, 最短路 继续阅读

  11. 「UOJ 261」「NOIP2016」天天爱跑步

    小C同学认为跑步非常有趣,于是决定制作一款叫做《天天爱跑步》的游戏。《天天爱跑步》是一个养成类游戏,需要玩家每天按时上线,完成打卡任务。 这个游戏的地图可以看作一棵包含 n 个结点和 n−1 条边的树,每条边连接两个结点,且任意两个结点存在一条路径互相可达。树上结点编号为从 1 到 n 的连续正整数。 现在有 m 个玩家,第 i 个玩家的起点为 Si,终点为 Ti。每天打卡任务开始时,所有玩家在第…

    LCA, UOJ 继续阅读

  12. 「UOJ 260」「NOIP2016」玩具谜题

    小南有一套可爱的玩具小人,它们各有不同的职业。 有一天,这些玩具小人把小南的眼镜藏了起来。小南发现玩具小人们围成了一个圈,它们有的面朝圈内,有的面朝圈外。如下图: 这时 singer 告诉小南一个谜题:“眼镜藏在我左数第 3 个玩具小人的右数第 1 个玩具小人的左数第 2 个玩具小人那里。” 小南发现,这个谜题中玩具小人的朝向非常关键,因为朝内和朝外的玩具小人的左右方向是相反的: 面朝圈内的玩具…

    UOJ 继续阅读

  13. 「UOJ 117」欧拉回路

    有一天一位灵魂画师画了一张图,现在要你找出欧拉回路,即在图中找一个环使得每条边都在环上出现恰好一次。 一共两个子任务: 这张图是无向图。(50分) 这张图是有向图。(50分) 输入格式第一行一个整数 t,表示子任务编号。 t∈{1,2},如果 t=1 则表示处理无向图的情况,如果 t=2 则表示处理有向图的情况。 第二行两个整数 n,m,表示图的结点数和边数。 接下来 m 行中,第 i 行两个整数…

    UOJ, 欧拉回路 继续阅读

  14. 「UOJ 78」二分图最大匹配

    从前一个和谐的班级,有 nl 个是男生,有 nr 个是女生。编号分别为 1,…,nl 和 1,…,nr。有若干个这样的条件:第 v 个男生和第 u 个女生愿意结为配偶。请问这个班级里最多产生多少对配偶? 输入格式第一行三个正整数,nl,nr,m。 接下来 m 行,每行两个整数 v,u 表示第 v 个男生和第 u 个女生愿意结为配偶。保证 1≤v≤nl,1≤u≤nr,保证同一个条件不会出现两次。 输…

    UOJ, 二分图最大匹配 继续阅读

  15. 「UOJ 17」「NOIP2014」飞扬的小鸟

    Flappy Bird 是一款风靡一时的休闲手机游戏。玩家需要不断控制点击手机屏幕的频率来调节小鸟的飞行高度,让小鸟顺利通过画面右方的管道缝隙。如果小鸟一不小心撞到了水管或者掉在地上的话,便宣告失败。 为了简化问题,我们对游戏规则进行了简化和改编: 游戏界面是一个长为 n,高为 m 的二维平面,其中有 k 个管道(忽略管道的宽度)。 小鸟始终在游戏界面内移动。小鸟从游戏界面最左边任意整数高度位置…

    UOJ, 背包 DP 继续阅读