[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团还管这么多？不是直接烧吗？显然一个强...
[计数]Codeforces GYM101194H【Great Cells】题解
题目概述构造一个 $n\times m$ 的矩阵，矩阵元素的值是 $[1,K]$ 中的整数。如果一个元素的值是同行同列中最大的，那么就是一个JZ数。令 $A_g$ 表示构造出的矩阵有 $g$ 个...
[扩展欧几里得]BZOJ1407(Noi2002)【Savage】题解
题目概述有 $n$ 个JZ在一个长度为 $m$ 的环上，第 $i$ 个JZ刚开始在 $c_i$ ，每天会顺时针走 $p_i$ 的路程到那里虐人，共虐 $l_i$ 天。如果一个人在同一天被多个JZ...
[二分图匹配]BZOJ1191(HNOI2006)【超级英雄Hero】题解
题目概述有 $n$ 个ZZK $m$ 个JZ，每个JZ可以虐两个指定的ZZK中的一个，一个ZZK被虐之后就心态爆炸不能再被虐，问从第一个JZ开始按顺序连续不断的虐ZZK，最多有多少个JZ能虐ZZ...
[莫比乌斯函数]BZOJ2005(Noi2010)【能量采集】题解
题目概述一个整点 $(x,y)$ 的代价 $w(x,y)$ 是与 $(0,0)$ 连线上的整点的个数的两倍减三，求 $\sum_{i=1}^{n}\sum_{j=1}^{m}w(i,j)$ 。解...
[DFS序换根+线段树]BZOJ5379【Tree】题解
题目概述有一棵 $n$ 个点的点权树，刚开始根是 $1$ ，现在有 $q$ 次操作：把根换成 $x$ 。把 $LCA(x,y)$ 子树中节点的权值均加上 $w$ 。询问 $x$ 子树的权值和。解...
