ZigZagK的博客
[离线+并查集按秩合并+平衡树启发式合并]Codeforces1417F【Graph and Queries】题解
题目概述CF1417F解题报告超级套路题……任意无向图删边是很麻烦的,所以肯定考虑离线转换成加边然后回退。加边就可以利用并查集来进行合并,考虑用set维护一个块的最大值,并查集合并的时候set启...
[离线+线段树]Codeforces1405E【Fixed Point Removal】题解
题目概述CF1405E解题报告显然有贪心:当有多个可以删除的元素同时存在时,先删除后面的,因为删后面的不影响前面。既然如此,我们从左往右考虑一个位置能否被删除。对于一个位置 $i$ ,如果前面已...
[离线+扫描线+LCT]BZOJ4573(Zjoi2016)【大森林】题解
题目概述有 $n$ 棵树和 $m$ 个操作,操作有:1.在 $[L,R]$ 树当前根的后面加一个点。2.把 $[L,R]$ 树的根改为 $x$ 。3.询问第 $x$ 树中 $A$ 到 $B$ 的...
[离线+后缀数组+STL乱搞]LOJ6041(雅礼集训 2017 Day7)【事情的相似度】题解
题目概述有长度为 $n$ 的 $01$ 串 $s$ 和 $m$ 个询问,每次询问 $[L,R]$ 表示 $s$ 的 $[L,R]$ 这些前缀之间的最大公共后缀。解题报告SAM+LCT什么的好大啊...
[莫比乌斯函数+线性筛+离线+除法分块+调和级数]BZOJ3529(Sdoi2014)【数表】题解
题目概述有一张 $n\times m$ 的数表,其第 $i$ 行第 $j$ 列的数值为能同时整除 $i$ 和 $j$ 的所有自然数之和。给定 $a$ , 计算数表中不大于 $a$ 的数之和。解题...
[Manacher+离线+线段树]2015计蒜之道初赛第三场【商品推荐走马灯】题解
题目概述给出一个序列,一个回文区间的权值是区间权值和,问 $[L,R]$ 中所有回文区间的权值和。解题报告刚开始想用回文自动机 $O(n\sqrt n)$ 暴搞,然后我自带大常数TLE了……只需...
[离线+霍尔定理+线段树]BZOJ2138【stone】题解
题目概述有 $n$ 堆石子,每堆 $a_i$ 个,现在要取 $m$ 次,第 $i$ 次在 $[L_i,R_i]$ 中取 $K_i$ 个(不够 $K_i$ 就取完)。问在前 $i-1$ 次取到的最...
[离线+复杂度分析]Codeforces1028H【Make Square】题解
题目概述有一个序列 $\{a_n\}$ ,如果区间 $[L,R]$ 里存在 $i<j$ 使得 $a_ia_j$ 是完全平方数就称这个区间是好的。一次操作可以把一个数变成 $a_ip$ 或 ...
[离线+AC自动机+复杂度分析]Codeforces963D【Frequency of String】题解
题目概述有一个文本串,现在有 $m$ 个模板串(互不相同),问文本串中长度最小的子串使得模板串出现了 $k_i$ 次。解题报告$m$ 个模板串互不相同奥妙重重,令 $M=\sum Length(...
[离线+斜率优化+二分]BZOJ5380【Function】题解
题目概述$$ f(x,y)=\begin{cases}A_y&x=1\\f(x-1,y)+A_y&y=1\land x\not=1\\min\{f(x-1,y-1),f(x-1)...