HDU2602 - Bone Collector
Bone Collector 一道01背包模板题，套模板即可
Read moreURAL - 1244 Gentlemen(01背包+记录路径)
URAL - 1244 Gentlemen 一道01背包的题目，只不过这一次不是用01背包来求最大值或最小值，而是将背包填满。这只需要将数组dp[]的dp[0]设为0，将其他设为 -∞即可（原因：这是为什么呢？可以这样理解：初始化的 F 数组事实上就是在没有任何物品可以放 入背包时的合法状态。如果要求背包恰好装满，那么此时只有容量为 0 的背包可以在什 么也不装且价值为 0 的情况下被“恰好装满”，其它容量的背包均没有合法的解，属于 未定义的状态，应该被赋值为 -∞ 了。如果背包并非必须被装满，那么任何容量的背包 都有一个合法解“什么都不装”，这个解的价值为 0，所以初始时状态的值也就全部为 0 了。） 难点在于记录路径，同时处理多个解的情况。一开始我也想不到要怎么处理多个解的情况(总不能做两次dp..
Read moreAizu - ALDS1_1_D-Maximum Profit（转化思想+DP）
Aizu - ALDS1_1_1_D (这貌似是个日本的oj？名字叫aizu有点奇怪呢hhhh)
Read moreHDU1171-Big Event in HDU（多重背包做法）
HDOJ1171 这道题之前是用01背包做的，现在用多重背包的做法解决。这其实更符合题意（个人认为）
Read more
HDU4054-Hexadecimal View
Hexadecimal View 此题没有考查任何一个算法知识点，只是一道用来练代码熟悉度的题目
Read more拓展欧几里得算法
普通的欧几里得算法 这大概是最为人熟知的数论算法了吧，作用是求出gcd(a,b)，代码如下:
Read more
卢卡斯定理与中国剩余定理
卢卡斯定理 卢卡斯定理主要是用来求组合数取模，即C(n,m)%p。其适用范围是:组合数很大，但p又不是很大且p是素数的情况(10^6+3也算是“不很大”) 。卢卡斯定理可以表达为:
Read more快速乘算法
原理与快速幂相似，利用二进制将两个数的乘法运算转化为加法运算。具体代码如下:
Read more
HDU5446-Unknown Treasure(卢卡斯定理，中国剩余定理)
题目链接:Unknown Treasure 这道题求得实际上是C(n,m)%M,M=p1·p2·p3···pk。又因为pi都是素数，故可用卢卡斯定理。但这里不可以直接用Lucas，因为Lucas的使用条件是“C(n,m)很大，但p不太大，同时p为素数”，而这里的M可能会很大。故我们可以先求C(n,m)%p1,C(n,m)%p2,C(n,m)%pk，然后再利用中国剩余定理得到最终答案。 代码如下: #include <iostream> #include <cstdio> #include <cstdlib> #include <cstring> using namespace std; typedef long long LL; //从n个苹果中挑出m个相互..
Read more
BZOJ4403-序列统计(组合数学，卢卡斯定理)
题目链接:序列统计 首先，L与R实际上是没太大意义的，因为我们需要的只是L和R之间含有多少个数，即R-L+1个数。其次，要注意一点，在一个序列中，数字是可以重复的。以样例中的2 4 5为例，符合要求的序列有{4},{5},{4,5},{4,4},{5,5}。事实上，问题可以转化为“有R-L+1个不同的盒子，若要将i(1<=i<=n)个相同的小球放进这些盒子里(某些盒子可以为空)，问对于所有的i，放法的总和是多少？”其中，不同的盒子代表着不同的数，在一个盒子中放入一个球，相当于选取一次该数字作为序列中的成员。再将问题抽象一下，即为“将i个小球划分成k堆(1<=k<=i)，问对于所有的i，划分方法的总和是多少？”对于这个问题，我们可以直接用C(m+n,n)求解(对于本题是C(seg..
Read more