Chro's Blog


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


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

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

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

  2. 「BZOJ 1758」「WC2010」重建计划

    Description Input第一行包含一个正整数N,表示X国的城市个数. 第二行包含两个正整数L和U,表示政策要求的第一期重建方案中修建道路数的上下限 接下来的N-1行描述重建小组的原有方案,每行三个正整数Ai,Bi,Vi分别表示道路(Ai,Bi),其价值为Vi 其中城市由1..N进行标号 Output输出最大平均估值,保留三位小数 Sample Input1234542 31 2 11 3…

    BZOJ, 点分治 继续阅读

  3. 「CodeChef BTREE」Union on Tree

    There is a country whose road system is a tree, the nodes in the tree represent cities and the edge is the road between them, and each edge is of unit length. For safety, the government should put gua…

    CodeChef, 主席树, 点分治, 虚树 继续阅读

  4. 「HDU 4812」D Tree

    Problem DescriptionThere is a skyscraping tree standing on the playground of Nanjing University of Science and Technology. On each branch of the tree is an integer (The tree can be treated as a connec…

    HDOJ, 点分治 继续阅读

  5. 「BZOJ 2599」「IOI2011」Race

    Description给一棵树,每条边有权.求一条简单路径,权值和等于K,且边的数量最小.N <= 200000, K <= 1000000 Input第一行 两个整数 n, k 第二..n行 每行三个整数 表示一条无向边的两端和权值 (注意点的编号从0开始) Output一个整数 表示最小边数量 如果不存在这样的路径 输出-1 Sample Input4 30 1 11 2 21 3…

    BZOJ, 点分治 继续阅读

  6. 「BZOJ 2152」聪聪可可

    Description聪聪和可可是兄弟俩,他们俩经常为了一些琐事打起来,例如家中只剩下最后一根冰棍而两人都想吃、两个人都想玩儿电脑(可是他们家只有一台电脑)……遇到这种问题,一般情况下石头剪刀布就好了,可是他们已经玩儿腻了这种低智商的游戏。他们的爸爸快被他们的争吵烦死了,所以他发明了一个新游戏:由爸爸在纸上画n个“点”,并用n-1条“边”把这n个“点”恰好连通(其实这就是一棵树)。并且每条“边”上…

    BZOJ, 点分治 继续阅读

  7. 「POJ 1741」Tree

    DescriptionGive a tree with n vertices,each edge has a length(positive integer less than 1001). Define dist(u,v)=The min distance between node u and v. Give an integer k,for every pair (u,v) of vertic…

    POJ, 点分治 继续阅读