menu ZigZagK的博客
account_circle

正在努力加载中QAQ

[bitset+树链剖分+线段树+霍尔定理]BZOJ5404【party】题解
题目概述有 $n$ 个点的有根树,每个节点只能往上走,且每个节点有一个特产。现在有 $q$ 个询问,每次询问 $c$ 个点,求这些点走到他们的公共祖先,在满足:1.每个人带的特产数量相等。2.没...
[霍尔定理+复杂度分析+贪心+线段树]Codeforces533A【Berland Miners】题解
题目概述有 $n$ 个点带点权的树和 $m$ 个物品,一个物品能放在树上一个节点的条件是树上这个节点到根路径上点权最小值大于等于这个物品的权值。现在能够把一个点权改大,求至少改多少能使得所有物品...
[二分图+矩阵树定理]LOJ6044(雅礼集训 2017 Day8)【共】题解
题目概述有 $n$ 个点的树,$1$ 为根,每个节点的深度定义为到根的点数。求深度为奇数的点恰好为 $K$ 的树的个数。解题报告emm……我们把树按照深度奇偶分开,就变成了一个二分图,两边点数为...
apps LOJ
local_offer 查看标签
comment 0 条评论
阅读全文
[霍尔定理+主席树+复杂度分析+DP]HHHOJ197【古明地】题解
解题报告题解里有个很厉害的 $O((n+s)log_2n)​$ 做法,但是我不会……我只会这种比较好想的做法。首先这明显是一个二分图完全匹配问题,我们可以把每项工作 $K_i$ 看成 $K_i$...
[二分图增广路+Tarjan]BZOJ2140【稳定婚姻】题解
题目概述有 $n$ 对CP,和 $m$ 对前男女友关系,一对CP(因抢着打隔膜导致电脑爆炸所以)解散之后可能会旧情复燃,导致很多CP都解散。问第 $i$ 对CP解散之后还能否使得所有人都找到新C...
apps BZOJ
local_offer 查看标签
comment 0 条评论
阅读全文
[离线+霍尔定理+线段树]BZOJ2138【stone】题解
题目概述有 $n$ 堆石子,每堆 $a_i$ 个,现在要取 $m$ 次,第 $i$ 次在 $[L_i,R_i]$ 中取 $K_i$ 个(不够 $K_i$ 就取完)。问在前 $i-1$ 次取到的最...
apps BZOJ
local_offer 查看标签
comment 0 条评论
阅读全文
[LCT维护最大生成树+二分图判定]BZOJ4025【二分图】题解
题目概述有 $n$ 个点 $m$ 条边,每条边有个出现时间 $s$ 和消失时间 $t$ ,问每个时刻是不是二分图。解题报告法老给我们上课用的PPT表示:把边加到线段树里然后线段树二分用LCT判奇...
apps BZOJ
local_offer 查看标签
comment 0 条评论
阅读全文
[DFS树+差分+二分图判定]BZOJ4424(Cf19E)【Fairy】题解
题目概述CF19E数据加大版。解题报告不能分治+LCT啦。由于只删除一条边所以可以大力分类讨论。先用DFS树+差分求出树边被多少个奇环覆盖以及被多少个偶环覆盖,然后:树边:如果处于所有奇环之间,...
[分治+LCT+二分图判定]Codeforces19E【Fairy】题解
题目概述有 $n$ 个点 $m$ 条边,问有多少边删除了之后让原图是二分图。解题报告远古CF题。删除一条边可以考虑分治,然后用LCT判断有没有奇环就行了。这是斯波做法,时间复杂度 $O(nlog...
apps Codeforces
local_offer 查看标签
comment 0 条评论
阅读全文
[二分图匹配]BZOJ1191(HNOI2006)【超级英雄Hero】题解
题目概述有 $n$ 个ZZK $m$ 个JZ,每个JZ可以虐两个指定的ZZK中的一个,一个ZZK被虐之后就心态爆炸不能再被虐,问从第一个JZ开始按顺序连续不断的虐ZZK,最多有多少个JZ能虐ZZ...
apps BZOJ
local_offer 查看标签
comment 0 条评论
阅读全文
keyboard_arrow_up