HDU4015 - Mario and Mushrooms( The 36th ACM/ICPC Asia Regional Shanghai Site —— Warmup E题)
Mario and Mushrooms 一道数学题，和pzc推了差不多一小时的式子，结果还是错了OTZ，遂看题解 然后发现这题其实就是直接把Raney引理套一套就行了(Raney引理又是什么神仙？？？) Raney引理: 设整数序列A={Ai,i=1,2,…,N}，且部分和为Sk=A1+,…,+Ak，序列中的所有的数字之和为Sn=1；则在A的N个循环表示中，有且仅有一个序列B，满足B的任意部分和Si均大于零。 一篇文章: HDOJ4105和raney引理 所以当时为什么不直接打表 代码如下: #include <cstdio> #include <iostream> #include <cstring> #include <cmath> #include ..
Read more
HDU2067 - 小兔的棋盘
小兔的棋盘 这道题有两种方法，一是dp，二是用卡特兰数(事实上我觉得dp是很自然的想法) 先说dp。对于棋盘的第0行(从下往上、从左往右数),除了(0,0)外，所有的点都只能由左边走来；对于棋盘的第0列，除了(0,0)外，所有的点都只能由左边走来。而对于对角线上的点，因为不能跨越对角线，所以这些点都只能由下边走来。而以上三种情况都不符合的点，则可以由左边或下边的点走来。故有一下dp代码：
Read more
HDU2049 - 不容易系列之(4)——考新郎
不容易系列之(4)——考新郎 错排公式的应用。因为n个新郎中有m个“错排”了，所以先用C(n,m)求出从n个新郎中挑m个出来的方案数，再乘以错排数即可。 关于错排公式，可看这里：
Read morePOJ2249 - Binomial Showdown
Binomial Showdown 使用C(n,k)与C(n,k-1)的递推关系来求组合数。
Read morePOJ1833 - 排列
排列 题意是输出给定排列的后第k个排列。这里用的是里的next_permutation()，比较方便。
Read more
POJ - 3734 Block
Block 这是冬训的一道关于矩阵快速幂的题目，但我硬是想不出递推式，于是只好硬推公式(同时部分参考题解)
Read more