[树形DP]LOJ2485(CEOI2017)【Chase】题解

题目概述有 $n$ 个点的树,每个点上有 $p_i$ 只咕咕咕。从任意点出发开始走,有 $k$ 次放面包的机会,放下面包后相邻点的咕咕咕就会凑到该点,问先...     阅读全文
ZigZagK 2018年8月19日 22:40
0 评论 | 1 访问

[Kruskal重构树+ST表]LOJ2718(NOI2018)【归程】题解

题目概述给出 $n$ 个点 $m$ 条无向边的连通图,每条边有距离和高度,如果高度 $\le$ 水的高度这条边就会被淹没,令 $dis_i$ 表示到达 $...     阅读全文
ZigZagK 2018年8月12日 12:48
0 评论 | 11 访问

[二分+后缀树+ST表+DFS序+主席树]LOJ2059(TJOI / HEOI2016)【字符串】题解

题目概述给出一个字符串 $S$ ,求 $max\{LCP(S_{[i,j]},S_{[c,d]})|a\le i\le j\le b\}$ 。解题报告先二...     阅读全文
ZigZagK 2018年8月10日 20:22
0 评论 | 16 访问

[非互质CRT]LOJ2721(NOI2018)【屠龙勇士】题解

题目概述求方程组 $atk_ix\equiv a_i\ (mod\ m_i)$ 最小的解。示例程序如果把系数去掉就是裸的非互质CRT,根据同余方程的同除性...     阅读全文
ZigZagK 2018年7月22日 11:21
0 评论 | 20 访问

[霍尔定理+线段树]LOJ6062(2017 山东一轮集训 Day2)【Pair】题解

题目概述两个数 \(x,y​\) 可以匹配定义为 \(x+y\ge H​\) 。现在给出 \(\{a_n\}​\) 和 \(\{b_m\}​\) ,问 \...     阅读全文
ZigZagK 2018年6月1日 14:11
0 评论 | 24 访问

[随机+Trie]LOJ2313(HAOI2017)【供给侧改革】题解

题目概述给出一个 \(n\) 位随机 \(01\) 串,定义 \(data(L,R)=max\{LCP(Suf_i,Suf_j)|i\not=j,L\le...     阅读全文
ZigZagK 2018年5月30日 20:49
0 评论 | 4 访问

[SG函数]LOJ2126(HAOI2015)【数组游戏】题解

题目概述有一个长度为 \(n\) 的数组,甲乙两人在上面进行这样一个游戏:首先,数组上有一些格子是白的,有一些是黑的。然后两人轮流进行操作。每次操作选择一...     阅读全文
ZigZagK 2018年5月22日 16:15
0 评论 | 20 访问

[矩阵快速幂]LOJ2128(HAOI2015)【数字串拆分】题解

题目概述你有一个长度为 \(n\) 的数字串。定义 \(f(S)\) 为将 \(S\) 拆分成若干个 \(1\sim m\) 的数的和的方案数,你可以将这...     阅读全文
ZigZagK 2018年5月20日 23:18
0 评论 | 3 访问

[区间DP]LOJ2063(HAOI2016)【字符合并】题解

题目概述有一个长度为 \(n​\) 的 \(01​\) 串,你可以每次将相邻的 \(k​\) 个字符合并,得到一个新的字符并获得一定分数。得到的新字符和分...     阅读全文
ZigZagK 2018年5月20日 13:19
0 评论 | 15 访问

[状压DP+组合]LOJ2540(PKUWC 2018)【随机算法】题解

题目概述我们知道,求任意图的最大独立集是一类NP完全问题,目前还没有准确的多项式算法,但是有许多多项式复杂度的近似算法。例如,小C常用的一种算法是: 对于...     阅读全文
ZigZagK 2018年5月18日 21:28
0 评论 | 33 访问