Chro's Blog


同じ世界に、立っていたんだ。


  1. 「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, 基环树 继续阅读

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

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

    BZOJ, Floyd, 倍增 继续阅读

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

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

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

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

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

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

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

    BZOJ, 状压 DP 继续阅读

  7. 退役前夜(未完待续)

    总感觉今年「我可能签了假的一本」,就连现在在常州听江苏省队集训,我也还是天天考试天天被虐…… 7 月 2 日今天是 JSOI 省队集训的最后一天。我好菜啊。江苏的同学们都好强啊。 明天我就要离开常州了,不知道接下来又会发生什么。 所谓「我可能签了假的一本」,还是希望不要如此吧。 我学 OI 毕竟已经三年半了,还是希望在这即将与 OI 分别的时刻,不留遗憾。希望在 21 日那天,我在浙江完成第四个 …

    Diary, 置顶文章 继续阅读

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

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

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

  9. 「BZOJ 1119」「POI2009」SLO

    Description对于一个1-N的排列(ai),每次你可以交换两个数ax与ay(x<>y),代价为W(ax)+W(ay) 若干次交换的代价为每次交换的代价之和。请问将(ai)变为(bi)所需的最小代价是多少。 Input第一行N。第二行N个数表示wi。第三行N个数表示ai。第四行N个数表示bi。 2<=n<=1000000 100<=wi<=6500 1&l…

    BZOJ, 置换群 继续阅读

  10. 「BZOJ 1697」「POJ 3270」Cow Sorting

    DescriptionFarmer John’s N (1 ≤ N ≤ 10,000) cows are lined up to be milked in the evening. Each cow has a unique “grumpiness” level in the range 1…100,000. Since grumpy cows are more likely to damage …

    BZOJ, POJ, 置换群 继续阅读

  11. 「BZOJ 2876」「NOI2012」骑行川藏

    Description蛋蛋非常热衷于挑战自我,今年暑假他准备沿川藏线骑着自行车从成都前往拉萨。川藏线的沿途有着非常美丽的风景,但在这一路上也有着很多的艰难险阻,路况变化多端,而蛋蛋的体力十分有限,因此在每天的骑行前设定好目的地、同时合理分配好自己的体力是一件非常重要的事情。 由于蛋蛋装备了一辆非常好的自行车,因此在骑行过程中可以认为他仅在克服风阻做功(不受自行车本身摩擦力以及自行车与地面的摩擦力影…

    BZOJ, 二分法, 拉格朗日乘数法 继续阅读

  12. 「BZOJ 4698」「SDOI2008」Sandy的卡片

    DescriptionSandy和Sue的热衷于收集干脆面中的卡片。然而,Sue收集卡片是因为卡片上漂亮的人物形象,而Sandy则是为了积攒卡片兑换超炫的人物模型。每一张卡片都由一些数字进行标记,第i张卡片的序列长度为Mi,要想兑换人物模型,首先必须要集够N张卡片,对于这N张卡片,如果他们都有一个相同的子串长度为k,则可以兑换一个等级为k的人物模型。相同的定义为:两个子串长度相同且一个串的全部元素…

    BZOJ, 后缀数组, 差分 继续阅读

  13. 「BZOJ 2055」80人环游世界

    Description想必大家都看过成龙大哥的《80天环游世界》,里面的紧张刺激的打斗场面一定给你留下了深刻的印象。现在就有这么一个80人的团伙,也想来一次环游世界。 他们打算兵分多路,游遍每一个国家。 因为他们主要分布在东方,所以他们只朝西方进军。设从东方到西方的每一个国家的编号依次为1…N。假若第i个人的游历路线为P1、P2……Pk(0≤k≤N),则P1<P2<……<Pk。 …

    BZOJ, 上下界费用流, 网络流 继续阅读

  14. 「BZOJ 3698」XWW的难题

    DescriptionXWW是个影响力很大的人,他有很多的追随者。这些追随者都想要加入XWW教成为XWW的教徒。但是这并不容易,需要通过XWW的考核。 XWW给你出了这么一个难题:XWW给你一个N*N的正实数矩阵A,满足XWW性。 称一个N*N的矩阵满足XWW性当且仅当:(1)A[N][N]=0;(2)矩阵中每行的最后一个元素等于该行前N-1个数的和;(3)矩阵中每列的最后一个元素等于该列前N-1…

    BZOJ, 上下界最大流, 网络流 继续阅读

  15. 「BZOJ 2502」清理雪道

    Description滑雪场坐落在FJ省西北部的若干座山上。 从空中鸟瞰,滑雪场可以看作一个有向无环图,每条弧代表一个斜坡(即雪道),弧的方向代表斜坡下降的方向。 你的团队负责每周定时清理雪道。你们拥有一架直升飞机,每次飞行可以从总部带一个人降落到滑雪场的某个地点,然后再飞回总部。从降落的地点出发,这个人可以顺着斜坡向下滑行,并清理他所经过的雪道。 由于每次飞行的耗费是固定的,为了最小化耗费,你想…

    BZOJ, 上下界最小流, 网络流 继续阅读