前述
组合数学：
1) C(n,m)=C(n,n-m)经常拿来预处理提高程序的执行效率。
还有很多需要总结的，还没想好，先放着。
POJ2249
题目描述：求组合数C(n,2)。
解题思路：如果直接相乘肯定会在中途溢出，所以用贪心的策略，每乘一个数，用尽量多的除数去把它除掉，如果再用64保存结果应该更加保险一点。
源代码:1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26#include <stdio.h>
int main()
{
int n,k;
while (scanf("%d%d",&n,&k)==2)
{
if (n==0&&k==0)
break;
if (n-k<k)
k=n-k;
int i,m=k;
__int64 mul=1;
for (i=k;i>0;i--)
{
mul = mul*(n-m+i);
while (mul%k==0&&k>1)
{
mul /= k;
k--;
}
}
printf("%I64d\n",mul);
}
return 0;
}
POJ1833
题目描述：大家知道，给出正整数n，则1到n这n个数可以构成n！种排列，把这些排列按照从小到大的顺序（字典顺序）列出，如n=3时，列出1 2 3，1 3 2，2 1 3，2 3 1，3 1 2，3 2 1六个排列。
任务描述：
给出某个排列，求出这个排列的下k个排列，如果遇到最后一个排列，则下1排列为第1个排列，即排列1 2 3…n。
比如：n = 3，k=2 给出排列2 3 1，则它的下1个排列为3 1 2，下2个排列为3 2 1，因此答案为3 2 1。
解决思路：1. 使用next_permutation函数 2.模拟这个查找过程，先找右边第一个逆序的数，将其右边略大于它的数放在其位置，将右边剩下的数和它按从小到大排序即完成一次next_permutation。
源代码：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23#include <stdio.h>
#include <algorithm>
using namespace std;
int main()
{
int m,n,k,i,a[1024+5];
scanf("%d",&m);
while (m--)
{
scanf("%d%d",&n,&k);
for (i=0;i<n;i++)
scanf("%d",&a[i]);
while (k--)
next_permutation(a,a+n);
printf("%d",a[0]);
for (i=1;i<n;i++)
printf(" %d",a[i]);
printf("\n");
}
return 0;
}
POJ1844
题目描述：给你一个数S让你用1～N，用这些自然数通过加减得到S，要求N最小。
比如12=－1+2+3+4+5+6-7
解题思路：S＝(1+N)N/2 - 偶数，这很容易想到。那么偶数等于(1+N)N/2-S, 现在要证明为什么(1+N)N/2-S是偶数就能得到S，首先(1+N)N/2-S < (1+N)N的也就是偶数 < (1+N)N，我们知道偶数是通过翻转1～N中的若干数得到，只要他不超过(1+N)N就可以翻转得到，因此此N是可以通过加减得到S的，另外N从小到大依次找，第一个能使(1+N)N/2-S为偶数的既是N最小。
源代码：1
2
3
4
5
6
7
8
9
10
11
12#include <stdio.h>
int main()
{
int n,i;
scanf("%d",&n);
int sum=0;
for (i=1;sum<n||(sum-n)%2==1;i++)
sum += i;
printf("%d\n",i-1);
return 0;
}