[二分+随机+斯坦纳树+思维]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$ 次放面包的机会，放下面包后相邻点的咕咕咕就会凑到该点，问先走一遍之后再走一遍遇到的咕咕咕个数之差最...
[Kruskal重构树+ST表]LOJ2718(NOI2018)【归程】题解
题目概述给出 $n$ 个点 $m$ 条无向边的连通图，每条边有距离和高度，如果高度 $\le$ 水的高度这条边就会被淹没，令 $dis_i$ 表示到达 $1$ 号点的最短路，问从 $x$ 点出发...
[二分+后缀树+ST表+DFS序+主席树]LOJ2059(TJOI / HEOI2016)【字符串】题解
题目概述给出一个字符串 $S$ ，求 $max\{LCP(S_{[i,j]},S_{[c,d]})|a\le i\le j\le b\}$ 。解题报告先二分答案 $len$ ，然后只需要验证 $...
