ZigZagK的博客
[复杂度分析]LOJ6043(雅礼集训 2017 Day7)【蛐蛐国的修墙方案】题解
题目概述给出一个 $n$ 的排列 $\{p_n\}$(满足 $i\not=p_i$ ),求一个括号序列满足:1.是合法的括号序列。2.对于所有左括号 $i$ ,向 $p_i$ 连双向边,最后得到...
[DP]LOJ6501(雅礼集训 2018 Day4)【Cube】题解
题目概述定义 $0$ 维基础图形为点,$1$ 维基础图形为边,$2$ 维基础图形是正方形,$3$ 维基础图形是正方体,以此类推。问 $n$ 维基础图形由多少个 $m$ 维基础图形组成。解题报告感...
[二分+随机+斯坦纳树+思维]LOJ2977(THUSCH 2017)【巧克力】题解
题目概述给出一个 $n\times m$ 的巧克力,每个位置有形状和美味值,求一个个数最小的连通块满足形状数 $\ge K$ ,且在个数最小的前提下,美味值的中位数也要最小。解题报告人类智慧题Q...
[离线+后缀数组+STL乱搞]LOJ6041(雅礼集训 2017 Day7)【事情的相似度】题解
题目概述有长度为 $n$ 的 $01$ 串 $s$ 和 $m$ 个询问,每次询问 $[L,R]$ 表示 $s$ 的 $[L,R]$ 这些前缀之间的最大公共后缀。解题报告SAM+LCT什么的好大啊...
[Min-Max容斥+树上高斯消元]LOJ2542(PKUWC2018)【随机游走】题解
题目概述有一棵树,刚开始你在 $X​$ ,每次随机走到相邻的点。有 $q​$ 个询问,每次询问给出一些点,求把这些点至少经过一次的期望时间。解题报告不难想到Min-Max容斥,令 $min(S)...
[贪心]NOIP2018Day2【旅行】题解
解题报告树的情况直接贪心做,基环树枚举环上的边断开然后贪心做。乱优化代码害人不浅,少 $20$ 分送我爆炸。测评鸭上面有 $O(n)$ 加强版,大佬们可以去切啊QAQ。示例程序#include&...
[扫描线+线段树]LOJ6276【果树】题解
题目概述一棵 $n$ 个节点的树,每个节点有颜色,求路径上没有相同颜色的路径个数,每种颜色出现次数不超过 $20$ 。解题报告填联赛前的坑,模拟考的时候我疯狂想容斥,我都想到用正解做链了却没想到...
[LCT+泰勒展开]LOJ2289(THUWC 2017)【在美妙的数学王国中畅游】题解
题目概述有 $n$ 个点,每个点是一个函数:$sin(ax+b),e^{ax+b},ax+b$ 。有 $4$ 种操作:1.连接 $x,y$ 。2.断开 $x,y$ 。3.修改 $x$ 点函数。4...
[线段树+复杂度分析]LOJ6507(雅礼集训 2018 Day7)【A】题解
题目概述区间与,区间或,区间最小值。解题报告完了我连吉利线段树裸题都不会做。这种题一般都是考虑差分数组来分析复杂度,如果 $[L,R]$ 与(或)上 $x$ ,那么 $x$ 为 $0(1)$ 的...
[树形DP]LOJ2485(CEOI2017)【Chase】题解
题目概述有 $n$ 个点的树,每个点上有 $p_i$ 只咕咕咕。从任意点出发开始走,有 $k$ 次放面包的机会,放下面包后相邻点的咕咕咕就会凑到该点,问先走一遍之后再走一遍遇到的咕咕咕个数之差最...