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 2055」80人环游世界

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

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

  3. 「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, 上下界最大流, 网络流 继续阅读

  4. 「BZOJ 2502」清理雪道

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

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

  5. 「BZOJ 4205」卡牌配对

    Description现在有一种卡牌游戏,每张卡牌上有三个属性值:A,B,C。把卡牌分为X,Y两类,分别有n1,n2张。 两张卡牌能够配对,当且仅当,存在至多一项属性值使得两张卡牌该项属性值互质,且两张卡牌类别不同。 比如一张X类卡牌属性值分别是225,233,101,一张Y类卡牌属性值分别为115,466,99。那么这两张牌是可以配对的,因为只有101和99一组属性互质。 游戏的目的是最大化匹配…

    BZOJ, 二分图最大匹配, 网络流 继续阅读

  6. 「BZOJ 1143」「CTSC2008」祭祀river

    Description在遥远的东方,有一个神秘的民族,自称Y族。他们世代居住在水面上,奉龙王为神。每逢重大庆典, Y族都会在水面上举办盛大的祭祀活动。我们可以把Y族居住地水系看成一个由岔口和河道组成的网络。每条河道连接着两个岔口,并且水在河道内按照一个固定的方向流动。显然,水系中不会有环流(下图描述一个环流的例子)。 由于人数众多的原因,Y族的祭祀活动会在多个岔口上同时举行。出于对龙王的尊重,这…

    BZOJ, 最小路径覆盖, 网络流 继续阅读