menu ZigZagK的博客
account_circle

正在努力加载中QAQ

[bitset+树链剖分+线段树+霍尔定理]BZOJ5404【party】题解
题目概述有 $n$ 个点的有根树,每个节点只能往上走,且每个节点有一个特产。现在有 $q$ 个询问,每次询问 $c$ 个点,求这些点走到他们的公共祖先,在满足:1.每个人带的特产数量相等。2.没...
[霍尔定理+复杂度分析+贪心+线段树]Codeforces533A【Berland Miners】题解
题目概述有 $n$ 个点带点权的树和 $m$ 个物品,一个物品能放在树上一个节点的条件是树上这个节点到根路径上点权最小值大于等于这个物品的权值。现在能够把一个点权改大,求至少改多少能使得所有物品...
[霍尔定理+主席树+复杂度分析+DP]HHHOJ197【古明地】题解
解题报告题解里有个很厉害的 $O((n+s)log_2n)​$ 做法,但是我不会……我只会这种比较好想的做法。首先这明显是一个二分图完全匹配问题,我们可以把每项工作 $K_i$ 看成 $K_i$...
[线段树+矩阵快速幂]Codeforces446C【DZY Loves Fibonacci Numbers】题解
题目概述有两种操作:1.将 $a_i,i\in[L,R]$ 加上 $fib_{i-L+1}$ 。2.求 $\sum_{i=L}^{R}a_i$ 。解题报告水Blog.jpg。先把原序列改成 $0...
[扫描线+线段树]LOJ6276【果树】题解
题目概述一棵 $n$ 个节点的树,每个节点有颜色,求路径上没有相同颜色的路径个数,每种颜色出现次数不超过 $20$ 。解题报告填联赛前的坑,模拟考的时候我疯狂想容斥,我都想到用正解做链了却没想到...
apps LOJ
local_offer 查看标签
comment 0 条评论
阅读全文
[线段树+复杂度分析]LOJ6507(雅礼集训 2018 Day7)【A】题解
题目概述区间与,区间或,区间最小值。解题报告完了我连吉利线段树裸题都不会做。这种题一般都是考虑差分数组来分析复杂度,如果 $[L,R]$ 与(或)上 $x$ ,那么 $x$ 为 $0(1)$ 的...
[贪心+后缀自动机+线段树合并]Codeforces700E【Cool Slogans】题解
题目概述有一个串,现在要找出这个串的一个子串使得这个子串在原串出现了至少 $2$ 次,接着对这个子串继续操作直到无法操作为止。求最多操作多少次。解题报告Div.1好难啊……因为要求最大值,所以贪...
[Dsu on tree+主席树优化建图+最大流]BZOJ3681【Arietta】题解
题目概述一棵 $n$ 个节点带点权的树,有 $m$ 种取节点的方法,第 $i$ 种 $[L,R,D,T]$ 表示只能取点权在 $[L,R]$ ,$D$ 子树中的点且只能取 $T$ 次。一个点不能...
[Manacher+离线+线段树]2015计蒜之道初赛第三场【商品推荐走马灯】题解
题目概述给出一个序列,一个回文区间的权值是区间权值和,问 $[L,R]$ 中所有回文区间的权值和。解题报告刚开始想用回文自动机 $O(n\sqrt n)$ 暴搞,然后我自带大常数TLE了……只需...
apps 计蒜客
local_offer 查看标签
comment 0 条评论
阅读全文
[BFS序+线段树]HDU5957【Query on a graph】题解
题目概述给一棵基环树,有两种操作:1.将到 $x$ 的距离 $\le K$ 的点权值均加上 $d$ 。2.询问到 $x$ 距离 $\le K$ 的点的权值和。解题报告emm……DFS序做多了都忘...
apps HDU
local_offer 查看标签
comment 0 条评论
阅读全文
keyboard_arrow_up