[莫比乌斯函数+调和级数]HDU6390【GuGuFishtion】题解
题目概述咕咕咕。求 $f(a,b)={\varphi(ab)\over\varphi(a)\varphi(b)},\sum_{a=1}^{n}\sum_{b=1}^{m}f(a,b)$ 。解题报...
[除法分块+矩阵快速幂]HDU6395【Sequence】题解
题目概述$f_1=A,f_2=B,f_n=Cf_{n-2}+Df_{n-1}+\lfloor{P\over n}\rfloor$ ，求 $f_n$ 。解题报告这可能是斯波题吧……除法分块然后每个...
[Kruskal重构树+ST表]LOJ2718(NOI2018)【归程】题解
题目概述给出 $n$ 个点 $m$ 条无向边的连通图，每条边有距离和高度，如果高度 $\le$ 水的高度这条边就会被淹没，令 $dis_i$ 表示到达 $1$ 号点的最短路，问从 $x$ 点出发...
[Kruskal重构树]BZOJ3732【Network】题解
题目概述给出一张无向图，多次询问两个点之间最长边的最小值为多少。解题报告因为最小生成树神奇的性质，我们只需要建出最小生成树然后求最小生成树路经上的最长边就是答案。不过我是来写Kruskal重构树...
[凸包同构]Codeforces1017E【The Supersonic Rocket】题解
题目概述判断两个凸包是否同构，即是否能平移+旋转使得两个凸包重合。解题报告原题意是说两个点之间都会建新点，建完之后新点之间也会建新点，那么其实很明显所有点构成了一个凸包围成的凸多边形……打比赛的...
[二分+后缀树+ST表+DFS序+主席树]LOJ2059(TJOI / HEOI2016)【字符串】题解
题目概述给出一个字符串 $S$ ，求 $max\{LCP(S_{[i,j]},S_{[c,d]})|a\le i\le j\le b\}$ 。解题报告先二分答案 $len$ ，然后只需要验证 $...
[压位+空间优化]Codeforces1017F【The Neutral Zone】题解
题目概述给出 $f(x)=Ax^3+Bx^2+Cx+D$ ，令 $x=p_1^{a_1}p_2^{a_2}\cdots p_k^{a_k},g(x)=a_1f(p_1)+a_2f(p_2)+\c...
[辗转相除+莫比乌斯函数+组合+调和级数]HDU6363(2018多校训练赛第六场)【bookshelf】题解
题目概述有 $n$ 个物品，分配到 $m$ 个箱子里（可以为空），问 $(2^{fib_{a_1} }-1,2^{fib_{a_2} }-1,\cdots,2^{fib_{a_m} })$ 的期...
[DFS树+线性基]BZOJ3569【DZY Loves Chinese II】题解
题目概述给出 $n$ 个点 $m$ 条无向边，有 $Q$ 个询问每次删除 $k_i$ 条边（之后还原），问图是否连通。解题报告先特判掉没删边就不连通，然后我们建出一棵DFS树，那么图不连通说明一...
[DP]HDU6356(2018多校练习赛第五场)【Glad You Came】题解
题目概述给出长度为 $n$ 的数字串，求最长非降子序列的长度，允许翻转一个区间 $[l,r]$ 。解题报告因为数字串，所以我们可以利用数值定义状态来快速转移，而翻转考虑三段DP：$f[i][j]...
