[离线+后缀数组+STL乱搞]LOJ6041(雅礼集训 2017 Day7)【事情的相似度】题解
题目概述有长度为 $n$ 的 $01$ 串 $s$ 和 $m$ 个询问，每次询问 $[L,R]$ 表示 $s$ 的 $[L,R]$ 这些前缀之间的最大公共后缀。解题报告SAM+LCT什么的好大啊...
[霍尔定理+主席树+复杂度分析+DP]HHHOJ197【古明地】题解
解题报告题解里有个很厉害的 $O((n+s)log_2n)$ 做法，但是我不会……我只会这种比较好想的做法。首先这明显是一个二分图完全匹配问题，我们可以把每项工作 $K_i$ 看成 $K_i$...
[单调栈+DP]Codeforces1131G【Most Dangerous Shark】题解
题目概述有 $n$ 个骨牌，每个骨牌有高度和推倒代价，骨牌可以往左往右推倒，如果两个骨牌的距离小于推倒骨牌高度那么就会向同一个方向倒下，求最小代价使得所有骨牌都倒下。解题报告不难想到 $O(n^...
[线段树+矩阵快速幂]Codeforces446C【DZY Loves Fibonacci Numbers】题解
题目概述有两种操作：1.将 $a_i,i\in[L,R]$ 加上 $fib_{i-L+1}$ 。2.求 $\sum_{i=L}^{R}a_i$ 。解题报告水Blog.jpg。先把原序列改成 $0...
[思维]HHHOJ189【Garrafeira】题解
解题报告陈老师的题解和没讲一样……考虑每一个二进制位的贡献，发现只要存在 $a_i$ 有 $j$ 这个二进制位，这个二进制位就有 $2^{n-1}2^{j}$ 的贡献，因为可以通过 $a_i$ ...
[贪心]Codeforces1131E【String Multiplication】题解
题目概述定义字符串 $A$ 和 $B$ 的乘法 $A\times B$ 的结果为将 $B$ 插入 $A$ 的每个空隙中（包含两端），给出 $n$ 个串，求按顺序乘起来之后最长连续相同字符的长度。...
[二维偏序+三维偏序]HHHOJ183【Drinks】题解
解题报告很明显至多选 $3$ 个就能构成一种方案，所以我们只需要考虑选 $1,2,3$ 个的情况就行了。考虑不合法的情况，即物品之间有包含的情况，如：1 1 1 | 3 2 2
2 2 2 | ...
[除法分块+杜教筛]HHHOJ173【B】题解
解题报告重新看一遍发现这题十分斯波……我们要求的是：$$
\sum_{\{a_k\}}e[(a_1,a_2,\cdots,a_k)]\\
\sum_{\{a_k\}}\sum_{d|(a_1,a...
[点分治]HHHOJ174【C】题解
解题报告摆明了要你点分治……每次统计 $x$ 子树的时候记录两个值：到 $x$ 路径最大值和到 $x$ 路径点权和。按照最大值排序之后，枚举 $i$ ，只要看前面有多少 $dis_j\equiv...
[STL乱搞+压位]BZOJ5087【Polycomp】题解
题目概述给出 $f(x),g(x),h(x)$ ，求 $f(g(x))\ mod\ h(x)$ ，系数在 $mod\ 2$ 意义下。解题报告直接就有一个 $O(n^2log_2n)$ 的多项式取...
