ZigZagK的博客
[贪心+堆]Codeforces1428E【Carrots for Rabbits】题解
题目概述CF1428E解题报告这就是换了皮的贪心+堆套路题,但是我不会QAQ。设 $Count(x,k)$ 表示 $x$ 分成 $k$ 堆的最少时间,显然是分成 $k-x\bmod k$ 个 $...
[思维+贪心+最短路]Codeforces1407E【Egor in the Republic of Dagestan】题解
题目概述CF1407E解题报告这题好妙啊……如果正着做,那么一个城市的颜色决定了好多边,但是倒着做的话,一条边决定了一座城市的颜色,明显好考虑了很多。从 $n$ 出发做最短路,记录 $dis_{...
[霍尔定理+复杂度分析+贪心+线段树]Codeforces533A【Berland Miners】题解
题目概述有 $n$ 个点带点权的树和 $m$ 个物品,一个物品能放在树上一个节点的条件是树上这个节点到根路径上点权最小值大于等于这个物品的权值。现在能够把一个点权改大,求至少改多少能使得所有物品...
[wqs二分+贪心+DP]BZOJ5400【y】题解
题目概述有 $n-1$ 座城市,$n$ 个乡村,每个城市有一条公路和一条铁路连进来(乡村没有连进来的路),每个乡村有参数 $a_i,b_i,c_i$ ,如果乡村走到 $1$ 号城市的路径上有 $...
[贪心+树形DP]LOJ6042(雅礼集训 2017 Day7)【跳蚤王国的宰相】题解
题目概述给出一棵 $n$ 个节点的树,求每个点成为与其他点距离和最小点最少需要删除并加上的边数 $k$(新加边之后依然是一棵树)。解题报告我根本发现不了性质.jpg。可以证明,到其他点距离和最小...
[贪心]Codeforces1131E【String Multiplication】题解
题目概述定义字符串 $A$ 和 $B$ 的乘法 $A\times B$ 的结果为将 $B$ 插入 $A$ 的每个空隙中(包含两端),给出 $n$ 个串,求按顺序乘起来之后最长连续相同字符的长度。...
[贪心+后缀自动机+线段树合并]Codeforces700E【Cool Slogans】题解
题目概述有一个串,现在要找出这个串的一个子串使得这个子串在原串出现了至少 $2$ 次,接着对这个子串继续操作直到无法操作为止。求最多操作多少次。解题报告Div.1好难啊……因为要求最大值,所以贪...
[倍增+并查集+贪心]Codeforces1059E【Split the Tree】题解
题目概述把一棵有权值的树分成若干条儿子到祖先的路径,每条路径节点个数不能超过 $L$ ,节点权值和不能超过 $S$ ,问最少分成多少路径。解题报告一个不知道正确性的解法,大佬可以来证明或者证伪一...
[贪心+阈值优化+精度]入门BZOJ3003(Noi2016十连测第一场)【奥义商店】题解
题目概述有 $n$ 个有权值的物品,现在给出若干个询问:$m$ 个颜色,每种颜色有 $c_i$ 个且和为 $n-1$ ,现在要在 $K$ 这个位置选择一个颜色,然后从 $K$ 向两边以 $D$ ...
[贪心+虚树+状压DP]51Nod1673【树有几多愁】题解
题目概述有一棵树,现在要给这棵树重编号,叶子节点的权值为到根路径的最小值,现在求叶子节点权值的积的最大值,保证叶子节点的个数不超过 $20$ 。解题报告可以想到这样的贪心:一个点的新编号肯定是子...