[压位+空间优化]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]...
[ST表]Codeforces1011F【Mars rover】题解
题目概述给出一个逻辑运算树，每个节点有一个逻辑运算或输入框（ $0$ 或 $1$ ）以及 $0/1/2$ 个儿子（根据符号定）。问每次只把所有输入框中的一个改成相反的（ $0\to 1,1\to...
[DP+线段树维护矩阵转移]Codeforces573D【Bear and Cavalry】题解
题目概述给出 $\{a_n\}$ 和 $\{b_n\}$ 以及刚开始 $P_i=i$ 的排列 $\{P_n\}$ ，有 $m$ 个询问，每次询问先交换 $P_x,P_y$ ，然后询问 $max\...
[莫比乌斯函数+调和级数]洛谷U32290【LJJ爱数数】题解
题目概述求 ${1\over a}+{1\over b}={1\over c}(a,b,c\in N^{*},a,b,c\le n)$ 解的个数。解题报告被学弟安利了这题（学弟秒掉了来嘲讽我）。...
[圆方树+树链剖分+线段树]Codeforces487E【Tourists】题解
题目概述给出 $n$ 个带权点和 $m$ 条无向边的图，给出 $q$ 个操作：1.修改某个节点的点权。2.询问 $x\to y$ 路径上所有简单路径的最小点权。解题报告简单路径就是一个点不能重复...
[莫队]HDU6333(2018多校练习赛第四场)【Harvest of Apples】题解
题目概述求 $\sum_{i=0}^{m}{n\choose m}$ ，多组询问 $(n,m)$ 。解题报告莫队大法好，由 $n\choose m$ 可以 $O(1)$ 得到 $n\choose...
[Tarjan求割点]BZOJ2730(HNOI2012)【矿场搭建】题解
题目概述煤矿工地可以看成是由隧道连接挖煤点组成的无向图。为安全起见，希望在工地发生事故时所有挖煤点的工人都能有一条出路逃到救援出口处。于是矿主决定在某些挖煤点设立救援出口，使得无论哪一个挖煤点坍...
