ZigZagK的博客
[线段树二分+树状数组]2020 ICPC 澳门 J【Jewel Grab】题解
题目概述Jewel Grab解题报告因为 $k\le 10$ ,其实就是个暴力题。记录 $pre_x$ 表示 $x$ 前面第一个颜色相同的位置(没有就记成 $0$ ),如果不能跳过,那么一定是在...
[主席树二分+复杂度分析]牛客IOI周赛28-提高组 C【下克上の天邪鬼】题解
题目概述下克上の天邪鬼解题报告顺着 ${\lfloor{a_i\over 2}\rfloor}\le a_j<a_i$ 想,不难想到利用这个 $\lfloor{a_i\over 2}\rf...
[后缀自动机+线段树合并]Codeforces1037H【Security】题解
题目概述CF1037H解题报告算法不难得出:对于 $x$ 的每个前缀 $x[1,i]$ ,往后添加一个比 $x_{i+1}$ 大的字符 $ch$ ,$i$ 越大 $ch$ 越小得到的答案就越小。...
[后缀自动机+线段树合并]HydroH1079【‘Minami Kotori’ Pantw 和他的召唤物二元葡萄】题解
题目概述HydroH1079解题报告建出SAM,找到 $[A,B]$ 对应节点 $p$ ,然后在 $p$ 的 $Right$ 集合上考虑。$[C,D]$ 中出现 $[A,B]$ 的子串比较难算,...
[离线+线段树+堆]洛谷4747(CERC2017)【Intrinsic Interval】题解
题目概述Luogu4747解题报告找性质题过于困难……首先很明显,如果两个合法区间有重叠部分,那重叠部分一定也是合法的。更进一步,根据这个性质可以得知答案一定是唯一的,否则两个答案区间的重叠部分...
[离线+ODT+扫描线+线段树]2022 CCPC 广州 B【Ayano and sequences】题解
题目概述Ayano and sequences解题报告其实并不是很难,但感觉考场上性价比不高 🤔 ,也可能只是我们队做的太慢了 😭 。这个问题如果在线做会发现涉及到时间和区间两个维度,并不是很好...
[后缀自动机+线段树合并+后缀数组]LOJ2720【「NOI2018」你的名字】题解
题目概述LOJ2720解题报告毒瘤字符串题……这题的关键在于,给出串 $T$ ,在 $S$ 的 $[L,R]$ 子串中查询每个后缀的最长匹配前缀。倒着考虑 $T$ 的每个后缀 $i$ ,求出在 ...
[离线+线段树套单调栈+线段树二分]2019 ICPC 香港 H【Hold the Line】题解
题目概述Hold the Line解题报告直接线段树套set是过不了的,我们需要一个小常数的做法。考虑离线,这样第 $i$ 次事件插入 $x$ 位置时,就可以认为是 $i$ 时刻 $x$ 才出现...
[后缀自动机+线段树合并]Codeforces GYM102411L【Lengths and Periods】题解
题目概述给一个字符串 $S$ ,选一个子串 $T$ ,使 ${T\over T-Border(T)}$ 最大。解题报告每个串的Border并不好考虑,但是可以考虑枚举Border,然后去找子串。...
[分数规划+长链剖分+线段树]洛谷4292【[WC2010]重建计划】题解
题目概述洛谷4292解题报告题解里很多点分治,但其实用长链剖分十分的直白。首先先用01分数规划,二分答案 $mid$ ,然后问题转化为边权为 $w-mid$ 的树上选出一条和 $\ge0$ 且长...