[二分]Codeforces1059D【Nature Reserve】题解

题目概述求一个半径最小的圆使得和 $x$ 轴相切,并且包含了所有给定的点。解题报告很明显可以二分 $r$ ,那么圆心就是 $(x,r)$ ,通过每个点就可...     阅读全文
ZigZagK 2018年10月8日 21:30
0 评论 | 17 访问

[Manacher+离线+线段树]2015计蒜之道初赛第三场【商品推荐走马灯】题解

题目概述给出一个序列,一个回文区间的权值是区间权值和,问 $[L,R]$ 中所有回文区间的权值和。解题报告刚开始想用回文自动机 $O(n\sqrt n)$...     阅读全文
ZigZagK 2018年10月8日 13:30
0 评论 | 15 访问

[BFS序+线段树]HDU5957【Query on a graph】题解

题目概述给一棵基环树,有两种操作:1.将到 $x$ 的距离 $\le K$ 的点权值均加上 $d$ 。2.询问到 $x$ 距离 $\le K$ 的点的权值...     阅读全文
ZigZagK 2018年10月5日 20:54
0 评论 | 15 访问

[Manacher+DP]BZOJ3790【神奇项链】题解

题目概述有一个字符串,用若干个回文串覆盖该串,回文串可以重叠,问需要的最少的回文串数 $-1$ 。解题报告很容易想到DP $f_i=f_j+1$ 其中以 ...     阅读全文
ZigZagK 2018年10月5日 18:28
0 评论 | 20 访问

[莫队]BZOJ4542(Hnoi2016)【大数】题解

题目概述有一个字符串,现在问这个字符串的一个子串中有多少子串是给出的素数 $p$ 的倍数( $0$ 也算)。解题报告$10^5$ ?莫队?先把满足条件的子...     阅读全文
ZigZagK 2018年10月5日 14:37
0 评论 | 20 访问

[期望DP]BZOJ4832(Lydsy1704月赛)【抵制克苏恩】题解

题目概述刚开始有 $A$ 个一点血的奴隶主,$B$ 个两点血的奴隶主,$C$ 个三点血的奴隶主。有一个克苏恩要攻击 $K$ 次,每次攻击随机攻击奴隶主或者...     阅读全文
ZigZagK 2018年10月5日 14:27
0 评论 | 20 访问

[wqs二分+决策单调性]POJ1160【Post Office】题解

题目概述有 $n$ 个村庄,现在要建 $m$ 个邮局,一种方案的代价是每个村庄到最近的邮局的距离之和。解题报告我再来水一遍这道题……之前已经用了wqs二分...     阅读全文
ZigZagK 2018年10月4日 23:03
0 评论 | 20 访问

[树形DP]入门BZOJ3004(Noi2016十连测第一场)【访问计划】题解

题目概述有一棵带边权的树,现在要从根节点出发,至少经过所有边一次,可以传送 $K$ 次,代价为 $C$ 。问走回根节点经过的最小边权和。解题报告先考虑把传...     阅读全文
ZigZagK 2018年10月4日 22:44
0 评论 | 10 访问

[贪心+阈值优化+精度]入门BZOJ3003(Noi2016十连测第一场)【奥义商店】题解

题目概述有 $n$ 个有权值的物品,现在给出若干个询问:$m$ 个颜色,每种颜色有 $c_i$ 个且和为 $n-1$ ,现在要在 $K$ 这个位置选择一个...     阅读全文
ZigZagK 2018年10月3日 23:23
0 评论 | 24 访问

[线段树+复杂度分析]Codeforces793F【Julia the snail】题解

题目概述有 $n$ 个点和 $m$ 个传送点 $(l,r)$ 表示可以从 $l$ 传送到 $r$ ,只能往下爬或者传送。问从 $x$ 出发在不超过 $y$...     阅读全文
ZigZagK 2018年10月3日 16:38
1 评论 | 23 访问