[贪心+ST表]BZOJ4444(Scoi2015)【国旗计划】题解

题目概述在一个长为 $m$ 的环上有 $n$ 个线段 $(s_i,t_i)$ ,问第 $i$ 个线段必选时至少需要多少线段能够覆盖这个环。解题报告和BZO...     阅读全文
ZigZagK 2018年8月17日 22:39
0 评论 | 5 访问

[贪心+ST表]BZOJ5397(湖南省队集训2018 Day3)【circular】题解

题目概述在一个长为 $m$ 的环上有 $n$ 个线段 $(s_i,t_i)$ ,在线段不交的情况下最多选择多少个线段?解题报告思路还停留在以前的斯波解法上...     阅读全文
ZigZagK 2018年8月17日 21:19
0 评论 | 8 访问

[斜率优化+二分]BZOJ5380【Function】题解

题目概述$$ f(x,y)=\begin{cases}A_y&x=1\\f(x-1,y)+A_y&y=1\land x\not=1\\mi...     阅读全文
ZigZagK 2018年8月14日 01:04
0 评论 | 12 访问

[Kruskal重构树]BZOJ3732【Network】题解

题目概述给出一张无向图,多次询问两个点之间最长边的最小值为多少。解题报告因为最小生成树神奇的性质,我们只需要建出最小生成树然后求最小生成树路经上的最长边就...     阅读全文
ZigZagK 2018年8月11日 19:35
0 评论 | 16 访问

[DFS树+线性基]BZOJ3569【DZY Loves Chinese II】题解

题目概述给出 $n$ 个点 $m$ 条无向边,有 $Q$ 个询问每次删除 $k_i$ 条边(之后还原),问图是否连通。解题报告先特判掉没删边就不连通,然后...     阅读全文
ZigZagK 2018年8月7日 21:03
0 评论 | 17 访问

[Tarjan求割点]BZOJ2730(HNOI2012)【矿场搭建】题解

题目概述煤矿工地可以看成是由隧道连接挖煤点组成的无向图。为安全起见,希望在工地发生事故时所有挖煤点的工人都能有一条出路逃到救援出口处。于是矿主决定在某些挖...     阅读全文
ZigZagK 2018年8月1日 22:51
0 评论 | 15 访问

[二分+后缀树+ST表]BZOJ5405【platform】题解

题目概述给出一个长度为 $n$ 的字符串和一个长度为 $n$ 的序列 $\{a_n\}$,问有多少个子串 $s_{[L,R]}$ 满足 $Rank(s_{...     阅读全文
ZigZagK 2018年7月31日 20:56
0 评论 | 29 访问

[哈希]BZOJ2795(Poi2012)【A Horrible Poem】题解

题目概述给出一个长度为 $n$ 的字符串和 $q$ 个询问,每个询问形如 $(l_i,r_i)$ 表示求 $s_{[l_i,r_i]}$ 的最短循环节的长...     阅读全文
ZigZagK 2018年7月25日 20:52
0 评论 | 21 访问

[DP]BZOJ2424(HAOI2010)【订货】题解

题目概述在第 $i$ 个月月初需要提供 $w_i$ 的货物,购买货物的单位价格为 $p_i$ 。货物可以存在上限为 $S$ 的仓库,但每月月底需要支付的单...     阅读全文
ZigZagK 2018年7月22日 14:12
0 评论 | 19 访问

[分数规划+树形DP]BZOJ4753(Jsoi2016)【最佳团体】题解

题目概述有 \(n+1\) 个人,选第 \(i\) 个人需要花费 \(s_i\) ,得到 \(p_i\) 的贡献,第一个人必选,没有花费和贡献。\(2\s...     阅读全文
ZigZagK 2018年7月17日 11:05
0 评论 | 13 访问