HDU2049 - 不容易系列之(4)——考新郎
不容易系列之(4)——考新郎 错排公式的应用。因为n个新郎中有m个“错排”了，所以先用C(n,m)求出从n个新郎中挑m个出来的方案数，再乘以错排数即可。 关于错排公式，可看这里：
Read morePOJ2249 - Binomial Showdown
Binomial Showdown 使用C(n,k)与C(n,k-1)的递推关系来求组合数。
Read more
HDU1018 - Big Number
Big Number 直接套用stirling数的公式即可。关于strling数，可参考下图
Read morePOJ1833 - 排列
排列 题意是输出给定排列的后第k个排列。这里用的是里的next_permutation()，比较方便。
Read moreHDU1969 - Pie
Pie 二分答案的经典题。所谓二分答案，即在整个可能的答案空间内进行二分操作，每次都检验一下mid，并根据检验结果调整lef和rig的值。
Read more
POJ - 3734 Block
Block 这是冬训的一道关于矩阵快速幂的题目，但我硬是想不出递推式，于是只好硬推公式(同时部分参考题解)
Read morePOJ2063 - Investment
Investment 其实就是做若干次的完全背包，每做一次都更新一下钱的总数。需要注意的是，因为钱的总数可能会很大，所以需要进行缩小，以免MLE。缩小方法是，因为每一种证券的价钱都是1000的倍数，故我们可以将它们的价钱都缩小为原来的1/1000(而利息不变)。
Read moreHDU1248 - 寒冰王座
寒冰王座
Read moreHDU2191 - 悼念512汶川大地震遇难同胞——珍惜现在，感恩生活
悼念512汶川大地震遇难同胞——珍惜现在，感恩生活 直接套用多重背包模板即可
Read more洛谷P1417 烹调方案
P1417 烹调方案 依然是01背包。这道题跟之前HDU的那道merchant很像，都是要先算一个不等式，再根据这个不等式进行排序，然后再进行01背包。具体而言，是要解下面这个不等式： a1 - (t0 + c1) x b1 + a2 - (t0 + c1 + c2) x b2 > a2 - (t0 + c2) x b2 +a1 - (t0 + c1 + c2) x b1 ==> b2 c1 < b1 c2 具体代码如下: #include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #define mst(a,b) memset(a,b,..
Read more