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 3672」「UOJ 7」「NOI2014」购票

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

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

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

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

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

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

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

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

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

  7. 「BZOJ 1002」「FJOI2007」轮状病毒

    Description轮状病毒有很多变种,所有轮状病毒的变种都是从一个轮状基产生的。一个N轮状基由圆环上N个不同的基原子和圆心处一个核原子构成的,2个原子之间的边表示这2个原子之间的信息通道。如下图所示 N轮状病毒的产生规律是在一个N轮状基中删去若干条边,使得各原子之间有唯一的信息通道,例如共有16个不同的3轮状病毒,如下图所示 现给定n(N<=100),编程计算有多少个不同的n轮状病毒…

    BZOJ, 动态规划, 矩阵树定理 继续阅读

  8. 「BZOJ 1566」「NOI2009」管道取珠

    Description Input第一行包含两个整数n, m,分别表示上下两个管道中球的数目。 第二行为一个AB字符串,长度为n,表示上管道中从左到右球的类型。其中A表示浅色球,B表示深色球。 第三行为一个AB字符串,长度为m,表示下管道中的情形。 Output仅包含一行,即为 Sigma(Ai^2) i从1到k 除以1024523的余数。 Sample Input1232 1ABB Sample…

    BZOJ, 动态规划 继续阅读

  9. 「BZOJ 1487」「HNOI2009」无归岛

    DescriptionNeverland是个神奇的地方,它由一些岛屿环形排列组成,每个岛上都生活着之中与众不同的物种。但是这些物种都有一个共同的生活习性:对于同一个岛上的任意两个生物,他们有且仅有一个公共朋友,即对同一岛上的任意两个生物a和b有且仅有一个生物c既是a的朋友也是b的朋友,当然某些岛上也可能会只有一个生物孤单地生活着。这一习性有一个明显的好处,当两个生物发生矛盾的时候,他们可以请那个唯…

    BZOJ, 仙人掌, 动态规划 继续阅读

  10. 「BZOJ 1023」「SHOI2008」cactus仙人掌图

    Description如果某个无向连通图的任意一条边至多只出现在一条简单回路(simple cycle)里,我们就称这张图为仙人掌图(cactus)。所谓简单回路就是指在图上不重复经过任何一个顶点的回路。 举例来说,上面的第一个例子是一张仙人图,而第二个不是——注意到它有三条简单回路:(4,3,2,1,6,5,4)、(7,8,9,10,2,3,7)以及(4,3,7,8,9,10,2,1,6,5,…

    BZOJ, 仙人掌, 动态规划 继续阅读

  11. 「BZOJ 3029」守卫者的挑战

    Description打开了黑魔法师Vani的大门,队员们在迷宫般的路上漫无目的地搜寻着关押applepi的监狱的所在地。突然,眼前一道亮光闪过。“我,Nizem,是黑魔法圣殿的守卫者。如果你能通过我的挑战,那么你可以带走黑魔法圣殿的地图……”瞬间,队员们被传送到了一个擂台上,最初身边有一个容量为K的包包。 擂台赛一共有N项挑战,各项挑战依次进行。第i项挑战有一个属性ai,如果ai>=0,表…

    BZOJ, 动态规划, 数学期望 继续阅读

  12. 「Codeforces 453A」Little Pony and Expected Maximum

    Twilight Sparkle was playing Ludo with her friends Rainbow Dash, Apple Jack and Flutter Shy. But she kept losing. Having returned to the castle, Twilight Sparkle became interested in the dice that wer…

    Codeforces, 动态规划, 数学期望 继续阅读

  13. 「Codeforces 398B」Painting The Wall

    User ainta decided to paint a wall. The wall consists of n2 tiles, that are arranged in an n × n table. Some tiles are painted, and the others are not. As he wants to paint it beautifully, he will fol…

    Codeforces, 动态规划, 数学期望 继续阅读

  14. 「BZOJ 1415」「NOI2005」聪聪和可可

    Description Input数据的第1行为两个整数N和E,以空格分隔,分别表示森林中的景点数和连接相邻景点的路的条数。 第2行包含两个整数C和M,以空格分隔,分别表示初始时聪聪和可可所在的景点的编号。 接下来E行,每行两个整数,第i+2行的两个整数Ai和Bi表示景点Ai和景点Bi之间有一条路。 所有的路都是无向的,即:如果能从A走到B,就可以从B走到A。 输入保证任何两个景点之间不会有多于一…

    BFS, BZOJ, 动态规划, 数学期望 继续阅读

  15. 「BZOJ 3450」Tyvj1952 Easy

    Description某一天WJMZBMR在打osu~~~但是他太弱逼了,有些地方完全靠运气:( 我们来简化一下这个游戏的规则 有n次点击要做,成功了就是o,失败了就是x,分数是按comb计算的,连续a个comb就有a*a分,comb就是极大的连续o。 比如ooxxxxooooxxx,分数就是22+44=4+16=20。 Sevenkplus闲的慌就看他打了一盘,有些地方跟运气无关要么是o要么是x…

    BZOJ, 动态规划, 数学期望 继续阅读