[线段树二分]HDU6301(2018多校第一场)【Distinct Values】题解
题目概述有一个长度为 $n$ 的序列，给出 $m$ 个限制，每个限制形如 $(l_i,r_i)$ 表示 $l_i$ 到 $r_i$ 的数互不相同，求字典序最小的满足条件的序列。解题报告把限制按照...
[DP]BZOJ2424(HAOI2010)【订货】题解
题目概述在第 $i$ 个月月初需要提供 $w_i$ 的货物，购买货物的单位价格为 $p_i$ 。货物可以存在上限为 $S$ 的仓库，但每月月底需要支付的单位价格为 $m$ ，仓库刚开始为空最后也...
[非互质CRT]LOJ2721(NOI2018)【屠龙勇士】题解
题目概述求方程组 $atk_ix\equiv a_i\ (mod\ m_i)$ 最小的解。示例程序如果把系数去掉就是裸的非互质CRT，根据同余方程的同除性，我们可以同除 $r=(atk_i,m_...
[分数规划+树形DP]BZOJ4753(Jsoi2016)【最佳团体】题解
题目概述有 $n+1$ 个人，选第 $i$ 个人需要花费 $s_i$ ，得到 $p_i$ 的贡献，第一个人必选，没有花费和贡献。$2\sim n+1$ 都有一个推荐人（推荐人编号小于自己的编号）...
[数位DP,矩阵快速幂]BZOJ3329【Xorequ】题解
题目概述求 $[1,n]$ 中满足 $x\ xor\ 3x=2x$ 的 $x$ 的个数以及 $[1,2^n]$ 中 $x$ 的个数。解题报告我竟然分析成了 $x=3x\ xor\ 2x$ ，然后...
[DP]BZOJ1190(HNOI2007)【梦幻岛宝珠】题解
题目概述有 $n$ 个物品，每个物品的体积满足 $a\cdot 2^b$ ，背包体积为 $W$ ，求最大价值。解题报告直接上背包！因为每个物品体积满足 $a\cdot 2^b$ ，所以我们可以定...
[LIS]洛谷3365【改造二叉树】题解
题目概述给出一棵 $n$ 个节点的二叉树，现在可以修改任意个节点的权值（只能改成整数），问至少多少次能把这棵二叉树改成BST。解题报告先中序遍历得到序列，然后就是用最少的次数把这个序列改成上升的...
[状压DP]BZOJ2734(HNOI2012)【集合选数】题解
题目概述如果选了 $x$ 就不能选 $2x$ 和 $3x$ ，求 $1..n$ 满足条件的子集个数。解题报告这种神题完全做不来，一波转化日神仙： x 3x 9x ...
2x 6x 18x...
[数位DP]Codeforces55D【Beautiful numbers】题解
题目概述问 $[L,R]$ 多少个整数是每个位上的数的倍数（$0$ 不算）。解题报告这道题想法不是特别难，但是要考虑优化。首先可以发现只需要记录 $mod\ 5,mod\ 7,mod\ 8,mo...
[Tarjan+拓扑]HDU6165【FFF at Valentine】题解
题目概述问一张 $n$ 个点 $m$ 条有向边的图是否满足两两点 $x,y$ 之间均有 $x$ 与 $y$ 连通或 $y$ 与 $x$ 连通。解题报告FFF团还管这么多？不是直接烧吗？显然一个强...
