Chro's Blog

だから 迷わない 頑張ろう

Those things that hurt, instruct.


  1. 「BZOJ 4044」「CERC2014」 Virus synthesis

    DescriptionViruses are usually bad for your health. How about fighting them with… other viruses? In this problem, you need to find out how to synthesize such good viruses. We have prepared for you a s…

    BZOJ, 动态规划, 回文自动机 继续阅读

  2. 「BZOJ 3782」上学路线

    Description小C所在的城市的道路构成了一个方形网格,它的西南角为(0,0),东北角为(N,M)。小C家住在西南角,学校在东北角。现在有T个路口进行施工,小C不能通过这些路口。小C喜欢走最短的路径到达目的地,因此他每天上学时都只会向东或北行走;而小C又喜欢走不同的路径,因此他问你按照他走最短路径的规则,他可以选择的不同的上学路线有多少条。由于答案可能很大,所以小C只需要让你求出路径数mod…

    BZOJ, 中国剩余定理, 动态规划, 组合数 继续阅读

  3. 「BZOJ 1815」「SHOI2006」color 有色图

    Description Input输入三个整数N,M,P 1< = N <= 53 1< = M < = 1000 N< P < = 10^ 9 Output即总数模P后的余数 Sample Input13 2 97 Sample Output14 Solution考虑一种点的置换及其对应的边置换。 把点置换拆成若干个循环节。循环节具体包含了哪些节点不重要,重要…

    BZOJ, Polya 定理 继续阅读

  4. 「BZOJ 4730」「UOJ 266」「清华集训2016」Alice和Bob又在玩游戏

    DescriptionAlice和Bob在玩游戏。有n个节点,m条边(0<=m<=n-1),构成若干棵有根树,每棵树的根节点是该连通块内编号最小的点。Alice和Bob轮流操作,每回合选择一个没有被删除的节点x,将x及其所有祖先全部删除,不能操作的人输。注:树的形态是在一开始就确定好的,删除节点不会影响剩余节点父亲和儿子的关系。比如:1-3-2 这样一条链,1号点是根节点,删除1号点之…

    BZOJ, 博弈论, 树型 DP 继续阅读

  5. 「BZOJ 3672」「UOJ 7」「NOI2014」购票

    Description今年夏天,NOI在SZ市迎来了她30周岁的生日。来自全国 n 个城市的OIer们都会从各地出发,到SZ市参加这次盛会。 全国的城市构成了一棵以SZ市为根的有根树,每个城市与它的父亲用道路连接。为了方便起见,我们将全国的 n 个城市用 1 到 n 的整数编号。其中SZ市的编号为 1。对于除SZ市之外的任意一个城市 v,我们给出了它在这棵树上的父亲城市 fv 以及到父亲城市道路…

    BZOJ, 动态规划, 斜率优化, 点分治 继续阅读

  6. 「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, 上下界最小流, 动态规划, 网络流 继续阅读

  7. 「BZOJ 4012」「HNOI2015」开店

    Description风见幽香有一个好朋友叫八云紫,她们经常一起看星星看月亮从诗词歌赋谈到人生哲学。最近她们灵机一动,打算在幻想乡开一家小店来做生意赚点钱。这样的想法当然非常好啦,但是她们也发现她们面临着一个问题,那就是店开在哪里,面向什么样的人群。很神奇的是,幻想乡的地图是一个树形结构,幻想乡一共有 n 个地方,编号为 1 到 n,被 n-1 条带权的边连接起来。每个地方都住着一个妖怪,其中第 …

    BZOJ, 主席树, 树链剖分 继续阅读

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

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

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

  9. 「BZOJ 2759」一个动态树好题

    Description有N个未知数x[1..n]和N个等式组成的同余方程组: x[i]=k[i]*x[p[i]]+b[i] mod 10007 其中,k[i],b[i],x[i]∈[0,10007)∩Z 你要应付Q个事务,每个是两种情况之一: 一.询问当前x[a]的解 A a 无解输出-1 x[a]有多解输出-2 否则输出x[a] 二.修改一个等式 C a k[a] p[a] b[a] Input…

    BZOJ, Link-Cut Tree, 基环树 继续阅读

  10. 「BZOJ 2306」「CTSC2011」幸福路径

    Description有向图 G有n个顶点 1, 2, …, n,点i 的权值为 w(i)。现在有一只蚂蚁,从给定的起点 v0出发,沿着图 G 的边爬行。开始时,它的体力为 1。每爬过一条边,它的体力都会下降为原来的 ρ 倍,其中ρ 是一个给定的小于1的正常数。而蚂蚁爬到某个顶点时的幸福度,是它当时的体力与该点权值的乘积。 我们把蚂蚁在爬行路径上幸福度的总和记为 H。很显然,对于不同的爬行路径…

    BZOJ, Floyd, 倍增 继续阅读

  11. 「BZOJ 1025」「SCOI2009」游戏

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

    BZOJ, 群论, 背包 DP 继续阅读

  12. 「BZOJ 3864」「HDU 4899」Hero meet devil

    DescriptionThere is an old country and the king fell in love with a devil. The devil always asks the king to do some crazy things. Although the king used to be wise and beloved by his people. Now he i…

    BZOJ, DP 套 DP, HDOJ, 序列 DP 继续阅读

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

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

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

  14. 「BZOJ 2734」「HNOI2012」集合选数

    Description《集合论与图论》这门课程有一道作业题,要求同学们求出{1, 2, 3, 4, 5}的所有满足以 下条件的子集:若 x 在该子集中,则 2x 和 3x 不能在该子集中。同学们不喜欢这种具有枚举性 质的题目,于是把它变成了以下问题:对于任意一个正整数 n≤100000,如何求出{1, 2,…, n} 的满足上述约束条件的子集的个数(只需输出对 1,000,000,001 取模的结…

    BZOJ, 状压 DP 继续阅读

  15. 「BZOJ 3997」「TJOI2015」组合数学

    Description给出一个网格图,其中某些格子有财宝,每次从左上角出发,只能向下或右走。问至少走多少次才能将财宝捡完。此对此问题变形,假设每个格子中有好多财宝,而每一次经过一个格子至多只能捡走一块财宝,至少走多少次才能把财宝全部捡完。 Input第一行为正整数T,代表数据组数。 每组数据第一行为正整数N,M代表网格图有N行M列,接下来N行每行M个非负整数,表示此格子中财宝数量,0代表没有 Ou…

    BZOJ, Dilworth 定理, 动态规划 继续阅读