[DFS序上DP]一种带依赖的树上背包
题目概述BZOJ4182弱化版，原版是要求选出来的点是连通的（我不会），弱化版只需要满足儿子选了父亲必选。解题报告其实之前做过带依赖的一道题，但是并没有体积，所以依然可以用正常的树形DP做。但这...
[分数规划+树形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团还管这么多？不是直接烧吗？显然一个强...
[计数]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...
