文章

1. 普通多重背包 把每种物品拆成一个一个的单个的物品，跑 01 背包。 复杂度：$O(n×m)$（物品数量×背包容量）2. 多重背包的二进制优化 你把一种物品拆成一个一个的物品累不累啊？ 我们知道，用二进制可以表示任何数字，即 $2^0,2^1,2^2…$到 $2^k$可以表示 1 阅读更多…

Amount of Degrees 题意: 给你两个数 X,Y(X<=Y<2^31-1), 以及 k,b, 求所有的 i∈[X,Y] 的数目,i 在 b 进制下只由 b 个１和若干个０组成。注意有多组数据。 如 X=15,Y=20,k=2,b=2, 则会有： 17 = 24+20, 18 阅读更多…

1. 博客已经安装了 MathJax，可以直接书写数学公式 2. 行内公式 二次方程 $ax^2+bx+c=0$的两根为 $\frac {-b \pm \sqrt {b^2-4ac}}{2a}$ 二次方程 $ax^2+bx+c=0$的两根为 $\frac {-b \pm \sqrt {b^2-4ac 阅读更多…

洛谷 “新创无际夏日公开赛—-幻想乡的西瓜”T3 题意：将球体沿俯视图的两条半径切去一个扇形，求正视图中球的内部部分占总可视面积的百分比，如图为俯视图，正视图面向 0°的位置。两条半径的极角为 a,b∈[0,360] 的整数，从若 x∈[a,b] 则 x 对应的半径已被切去。如图: 此题 阅读更多…

HAOI2010 题意：给定一些软件，每个软件占 Wi 空间，价值 Vi，依赖第 Di 个软件。求在 M 空间的电脑最多可以装多少价值的软件。软件 i 可以安装当且仅当软件 Di 已安装，默认 Di=0 意思是没有依赖，可以随意安装。 思路，由于图中相当于有 n 个节点，n 条边，所以必定有自环。我 阅读更多…

1. 题目 传送门＝￣ω￣＝ 2. 题解 你可以把这题看成树型 dp。 但其实这应该算是个。。。区间 dp。 给出的序列是中序遍历。。。 中序遍历是按 “左-根-右” 方式进行遍历二叉树，因此二叉树左孩子遍历序列一定在根结点的左边，右孩子遍历序列一定在根结点的右边。。。 所以我们设 $f[i,j]$ 阅读更多…

1. 题目 传送门＝￣ω￣＝ 2. 题解 跑一遍素数筛，筛出每个数字的所有质因数，存在数组里。 然后 $f(i)=min(f(i-1),f(i/p))+1$，$p$是 $i$的质因数。 代码： #include <bits/stdc++.h> using namespace std; i 阅读更多…

树上分组背包 题意：给定一棵 n 个节点的树，树的某个节点 s 上有 k 个机器人。要分配这些机器人去遍历这颗树，求经过的边的最小权值和。 分析：对于某一棵子树，如果进去一个机器人，它要么出来，要么不出来。如果有一个机器人出来了，就不能有第二个机器人出来。因为让第一个人去走第二个人要走的路，比第二个 阅读更多…

扇形面积并 这道题比矩形面积并友好多了。 题意：给定 n 个同心扇形，放置在一个被半径 2m 等分的圆中（圆是假想的），求被扇形覆盖了 k 次以上的关于面积的代数式 $\frac{\pi}{2m}\times ans=S$, 其中 S 为面积，输出 ans; 输入：第一行是三个整数 n，m，k。n 阅读更多…

Polygon 题意：给定一个环，每个节点是一个数字，每条边是加号或者乘号。首先删除一条边，接下来重复下列方式进行游戏：1. 选取一条边，删除它。2. 把删除的边两端的数字按照符号合并为一个新的节点。直到没有边。 分析：简单的 Dp 问题，如果用 $f[i][j]$表示将环拆开后再复制一遍后，从 $ 阅读更多…