[线段树+复杂度分析]LOJ6507(雅礼集训 2018 Day7)【A】题解
题目概述区间与，区间或，区间最小值。解题报告完了我连吉利线段树裸题都不会做。这种题一般都是考虑差分数组来分析复杂度，如果 $[L,R]$ 与(或)上 $x$ ，那么 $x$ 为 $0(1)$ 的...
[启发式分裂]BZOJ4059(Cerc2012)【Non-boring sequences】题解
题目概述判断一个序列是否满足所有子序列都有一个数只出现了一次。解题报告可以用矩形覆盖+扫描线的方法，不过可以像NWERC2017F一样启发式分裂。一个数左边第一个相同的数和右边第一个相同的数这一...
[线性筛+启发式分裂]NWERC2017F【Factor-Free Tree】题解
题目概述如果一棵二叉树儿子和祖先权值均互质则是一棵FFT（手动滑稽），现在给出一棵树权值的中序遍历，问是否有一种方案使得该树为FFT。解题报告首先有结论：如果 $[L,R]$ 可以变成FFT，那...
[阈值优化+可持久化Trie+哈希]CodeChef(BINSTR)【Binary Strings】题解
题目概述有一个二进制数序列 $\{A_n\}$ ，现在有 $Q$ 个询问，每次询问 $(L,R,X)$ 表示询问 $[L,R]$ 中与二进制数 $X$ 异或值最大的元素的下标。解题报告友情提示：...
[欧拉序+树的直径+复杂度分析]CodeChef(MXPATH)【Maximum Tree Path】题解
题目概述有一棵既有点权又有边权的树，求 $max\{dist(u,v)\cdot min(u,v)\cdot gcd(u,v)\}$ ，其中 $dist(u,v)$ 表示距离，$min(u,v)...
[思维]HDU4473【Exam】题解
题目概述令 $f(x)=\sum_{a=1}^{+\infty}\sum_{b=1}^{+\infty}[ab|x]$ ，求 $\sum_{i=1}^{n}f(i)$ 。解题报告emm……其实就...
[莫队+阈值优化+哈夫曼树]Codeforces700D【Huffman Coding on Segment】题解
题目概述给出 $n$ 个数和 $m$ 个询问，每次询问给 $[L,R]$ 中的数进行哈夫曼编码得到的长度总和。解题报告挺强的题，给 $[L,R]$ 中的数进行哈夫曼编码，数据结构肯定搞不了，所以...
[Dsu on tree+主席树优化建图+最大流]BZOJ3681【Arietta】题解
题目概述一棵 $n$ 个节点带点权的树，有 $m$ 种取节点的方法，第 $i$ 种 $[L,R,D,T]$ 表示只能取点权在 $[L,R]$ ，$D$ 子树中的点且只能取 $T$ 次。一个点不能...
[调和级数+DP]Codeforces1047E【Region Separation】题解
题目概述有一棵树，现在要把树分成若干个级别，每个级别是若干个权值加和相等的连通块。第一个级别是所有节点，之后的级别需要满足第 $i$ 个级别中的连通块均在 $i-1$ 中连通且 $i$ 的块数必...
[贪心+阈值优化+精度]入门BZOJ3003(Noi2016十连测第一场)【奥义商店】题解
题目概述有 $n$ 个有权值的物品，现在给出若干个询问：$m$ 个颜色，每种颜色有 $c_i$ 个且和为 $n-1$ ，现在要在 $K$ 这个位置选择一个颜色，然后从 $K$ 向两边以 $D$ ...
