一.最长子序列问题，见http://blog.csdn.net/qq_37416823/article/details/77718585
二·放苹果问题 【问题描述】将整数n分成k份，且每份不能为空，任意两个方案不相同(不考虑顺序)。 例如：n=7，k=3，下面三种分法被认为是相同的。 1，1，5; 1，5，1; 5，1，1; 问有多少种不同的分法。 【分析】根据排列组合公式得，将整数n分成k份相当于Σn-i分成k-1份(1<=i<=N/K) 核心代码为：
int dfs(int sum,int step,int now) //sum为n，step为k，now是防止重复的 { int g=0; if(step==1) return g=1;//边界条件 for(int i=now;i<=sum/step;i++)//从now枚举，防止重复 g+=dfs(sum-i,step-1,i);//统计方案和 return g; }三.最大子段和问题 【题目描述】给出一段序列，选出其中连续且非空的一段使得这段和最大。 【分析】使用滚动数组来解决这道题目，我们注意到，a[i]=max(a[i-1],sum); 也就是a[i]的值与a[i-2],a[i-3],a[i-4]……已经没有关系了。 【核心代码】
sum=a[1]; for(int i=2;i<=n;++i) { scanf("%d",&a[i%2]); sum+=a[i%2]; a[i%2]=max(a[(i-1)%2],sum); if(sum<0) sum=0; }四.逆序对 【问题描述】对于给定的一段正整数序列，逆序对就是序列中ai>aj且i
inline void add(int i,int x){//树状数组添加数 while(i<=n){ tree[i]+=x; i+=i&-i; } } inline int quary(int i){//查询个数 int s=0; while(i){ s+=tree[i]; i-=i&-i; } return s; }排序和查询添加的核心代码
sort(p+1,p+1+n,cmp); for(int i=1;i<=n;i++) a[p[i]]=i;//p[i]变不了，重新编号 for(int i=1;i<=n;i++){ ans+=i-1-quary(a[i]); //当前树状数组中有**i-1**个（为什么？），quary(a[i])前缀和查出a[i]前的个数 add(a[i],1); //值为a[i]的数又增加了一个 }五.最大公约数和最小公倍数问题 最大公约数核心代码
int gcd(int a,int b){ if(b==0) return a; return gcd(b,a%b); }最小公倍数=两整数的乘积÷最大公约数
六.快速幂 核心代码：
long long qpow(long long n,long long x,long long mod) { if(x==0) return 1;//递归出口：0次方为1 long long res=qpow(n*n%mod,x/2,mod);//递归 if(x&1) res=res*n%mod;//若x为奇数那么把返回值乘上n return res; }