• poj训练记录2

    poj训练记录2

    3613.CowRelays求经过n条边的最短路,floyd+倍增QAQ[crayon-58d3681e9e7a9861447340/]2728.DesertKing最优比率生成树分数规划[crayon-58d3681e9e7b5803276384/]1639.PicnicPlanning带度数限制的最小生成树http://wenku.baidu.com/link?url=UKcnK1pZvaVwypQOrIFRTOPzM4edIlBmqvnZjZipGf2o_6u-aB1F2tFsMGdUQbA1O-96menmbgyxNoSoWKWBeJnr-RJKuG2yM4b6Jf7IvR3[crayon-58d3681e9e7...

  • CERC 2014 填坑计划(9/12)

    CERC 2014 填坑计划(9/12)

    又是一个深不见底的大坑9/12A.Parades树形dp,dp[x]=∑dp[son]可能还有从一个子树出发,到达另一个子树的路径在每个结点记录在这棵树最优解的情况下去掉覆盖的路径树根能到达的点,这个每次暴力合并每个结点用状压dp配对子树得出最优解[crayon-58d3681e9faee254021706/]C.Sum我傻逼了。。。枚举答案后二分(其实可以直接算)不合法的情况似乎是2的幂[crayon-58d3681e9fafe503543710/]D.Wheels模拟[crayon-58d3681e9fb0223305...

  • 【cf507X】Codeforces Round #287 (Div. 2)

    【cf507X】Codeforces Round #287 (Div. 2)

    A.AmrandMusic排序贪心[crayon-58d3681ea02b5276693271/]B.AmrandPins算出距离除以直径[crayon-58d3681ea02bd432138297/]C.GuessYourWayOut!按位考虑[crayon-58d3681ea02c1084753665/]D.TheMathsLecture从后往前dpf(i,j,k)表示后i位,当前模为j,是否有后缀被K整除[crayon-58d3681ea02c5352646936/]E.BreakingGood广搜,选可用边最多的路径[crayon-58d3681ea02cb032365374/] ...

  • 【cf525X】Codeforces Round #297 (Div. 2)

    【cf525X】Codeforces Round #297 (Div. 2)

    A.VitaliyandPie模拟[crayon-58d3681ea0e1c154653103/]B.PashaandString前缀和记录一下每个点的翻转次数[crayon-58d3681ea0e25831281678/]C.IlyaandSticks排序后从大到小贪心[crayon-58d3681ea0e2a130714636/]D.ArthurandWalls如果某四个格子只有一个*,则把它变成.[crayon-58d3681ea0e2d629731364/]E.AnyaandCubes折半搜索一下[crayon-58d3681ea0e32411239667/] ...

    02015年5月16日745模拟,贪心,深度搜索
  • NEERC 2014 填坑计划(7/12)

    NEERC 2014 填坑计划(7/12)

    7/12已弃A简单贪心[crayon-58d3681ecf475930605946/]B按B/A排序后贪心[crayon-58d3681ecf481664337333/]E写的题解被吞了。。。奇怪的随机化直接看代码好了[crayon-58d3681ecf487642062259/]F主要是读题上的困难,得出每个文件的二进制串,用bitset判包含[crayon-58d3681ecf48d123797687/]I将出现次序作为权,发现合法状态是一个递增序列拼上递减序列然后就是dp啦[crayon-58d3681ecf491222494885/]J搜索可过,因为不合法状态...

  • poj训练记录

    poj训练记录

    1966.CableTVNetwork枚举源汇求最小割[crayon-58d3681ecff20709228374/]2386.LakeCounting搜索[crayon-58d3681ecff2e137177007/]3863.BusinessCenter枚举每个电梯,二分求最小值[crayon-58d3681ecff34402673275/]2504.Boundingbox求外心然后旋转n次得到多边形坐标精度弃坑。。[crayon-58d3681ecff37772665312/]3155.HardLife最大密度子图+方案分数规划[crayon-58d3681ecff3f062406781/]4028.GCDGuessingGame贪心策...

  • 【bzoj4029】[HEOI2015]定价

    【bzoj4029】[HEOI2015]定价

    Description 在市场上有很多商品的定价类似于999元、4999元、8999元这样。它们和1000元、5000元和9000元并没有什么本质区别,但是在心理学上会让人感觉便宜很多,因此也是商家常用的价格策略。不过在你看来,这种价格十分荒谬。于是你如此计算一个价格p(p为正整数)的荒谬程度:1、首先将p看做一个由数字组成的字符串(不带前导0);2、然后,如果p的最后一个字符是0,就去掉它。重复这一过程,直到p的最后一个字符不是0;3、记...

    22015年4月28日1,469贪心
  • 【bzoj4027】[HEOI2015]兔子与樱花

    【bzoj4027】[HEOI2015]兔子与樱花

    Description很久很久之前,森林里住着一群兔子。有一天,兔子们突然决定要去看樱花。兔子们所在森林里的樱花树很特殊。樱花树由n个树枝分叉点组成,编号从0到n-1,这n个分叉点由n-1个树枝连接,我们可以把它看成一个有根树结构,其中0号节点是根节点。这个树的每个节点上都会有一些樱花,其中第i个节点有c_i朵樱花。樱花树的每一个节点都有最大的载重m,对于每一个节点i,它的儿子节点的个数和i节点上樱花个数之和不能超过m,即so...

    02015年4月27日2,268贪心,树形动规
  • 【cf538X】Codeforces Round #300

    【cf538X】Codeforces Round #300

    A.CuttingBanner枚举切掉中间部分匹配[crayon-58d3681ed180e000041874/]B.QuasiBinary用最少的只包含01的数凑出n每次贪心在非0位上取1[crayon-58d3681ed1817974106562/]C.Tourist'sNotes根据每俩个的时间及高度差可计算答案[crayon-58d3681ed181c506618420/]D.WeirdChess暴力暴力暴力[crayon-58d3681ed1821649550960/]E.DemiurgesPlayAgain考虑进入某个根,最终会取得子树第几小的叶子[crayon-58d3681ed1827041299...

    02015年4月27日1,501模拟,贪心,主席树,调和级数
  • 【bzoj3624】[Apio2008]免费道路

    【bzoj3624】[Apio2008]免费道路

    DescriptionInputOutputSampleInput572130451320531430121421 SampleOutput320430531121题解优先加1做生成树,得出必须添加的0的边反过来,将0的边加至K条,再放1的边[crayon-58d3681ed1d44467507881/] ...

    02015年4月24日1,712贪心,并查集
  • 【bzoj2811】[Apio2012]Guard

    【bzoj2811】[Apio2012]Guard

    DescriptionInputOutputSampleInput534121341440451SampleOutput35HINT在这个样例中,有两种可能的安排方式:1,3,5 或者 2,3,5。即 3 和 5后面必然躲着一个忍者。考虑第一个灌木丛,存在一种安排方案使得它的后面躲着忍者,但也存在一种安排方案使得它后面没有躲忍者,因此不应该输出 1。同理,不应该输出 2。题解首先先将0的区间去除,可以用线段树TT如果去除0剩下的坐标编号等于忍者数,则所有剩下的坐标...

    132015年4月24日2,035贪心,二分法,线段树
  • UOJ Round #2

    UOJ Round #2

    http://vfleaking.blog.uoj.ac/blog/38【UR#2】猪猪侠再战括号序列猪猪侠大神太厉害了[crayon-58d3681ed2f13753882069/]下面俩题怎么这么恶心TT【UR#2】跳蚤公路负环能影响一个点v当其与1,v都连通,这个用floyd就好不等式取整要手写虽然分析了那个式子写起来还是蛋疼每个环每个系数k,枚举j,取整范围求并就能得出所能影响的点的x取值范围,x<=l或x>=r一个点的x被许多这样的取整范围限定TT将区间排序一下扫一遍得去...

    52015年4月15日1,308spfa,贪心,floyd,点分治
  • 【cf534X】Codeforces Round #298 (Div. 2)

    【cf534X】Codeforces Round #298 (Div. 2)

    【cf534A】Examyy个奇怪的构造TT[crayon-58d3681ed3951715604946/]【cf534B】CoveredPathd很小,最大速度就很小,dp即可[crayon-58d3681ed395a816072522/]【cf534C】Polycarpus'Dice对于每个骰子,得出其它骰子的和sum则它的最小值为A-sum,最大值为A-n+1[crayon-58d3681ed395f859476136/]【cf534D】Handshakes尽量大的能处理则处理[crayon-58d3681ed3966747052372/]【cf534E】BerlandLocalPositioningSystem非...