近期程序设计竞赛和公司面试的总结

1 树型DP的问题:


2 C++中讲string 快速转化到Int的问题:
stringstream是用于C++风格的字符串的输入输出的。
stringstream的构造函数原形如下： stringstream::stringstream(string str); #include

string s;
int a;
istringstream ss(s);
ss>>a;



3 C++中常用的字符串初始化函数
void *memset(void *s, int c, size_t n); Sets n bytes of a block of memory to byte c. memset sets the first n bytes of the array s to the character c.
用这个东东可以快速将字符串初始化.


4数学问题(发现好久没看数学了,连一些基本的东东都忘了)
递归方程组解的渐进阶的求法——差分方程法
这里只考虑形如：
T(n)=c1T(n-1)+c2T(n-2)+…+ ckT(n-k)+f(n)，n≥k (6.18)
的递归方程。其中ci (i=l，2，…，k)为实常数，且ck≠0。它可改写为一个线性常系数k阶非齐次的差分方程：
T(n)-c1T(n-1)- c2T(n-2)-…-ckT(n-k)=f(n)，n≥k (6.19)
(6.19)与线性常系数k阶非齐次常微分方程的结构十分相似，因而解法类同。限于篇幅，这里直接给出(6.19)的解法，略去其正确性的证明。
第一步，求(6.19)所对应的齐次方程：
T(n)-c1T(n-1)- c2T(n-2)-…-ckT(n-k)=0 (6.20)
的基本解系：写出(6.20)的特征方程：
C(t)=tk-c1tk-1-c2tk-2 -…-ck=0 (6.21)
若t=r是(6.21)的m重实根，则得(6.20)的m个基础解rn，nrn，n2rn，…，nm-1rn；若ρeiθ和ρe-iθ是(6.21)的一对l重的共扼复根，则得(6.20)的2l个基础解ρncosnθ，ρnsinnθ，nρncosnθ，nρnsinnθ，…，nl-1ρncosnθ，nl-1ρncosnθ。如此，求出(6.21)的所有的根，就可以得到(6.20)的k个的基础解。而且，这k个基础解构成了(6.20)的基础解系。即(6.20)的任意一个解都可以表示成这k个基础解的线性组合。
第二步，求(6.19)的一个特解。理论上，(6.19)的特解可以用Lagrange常数变易法得到。但其中要用到(6.20)的通解的显式表达，即(6.20)的基础解系的线性组合，十分麻烦。因此在实际中，常常采用试探法，也就是根据f(n)的特点推测特解的形式，留下若干可调的常数，将推测解代人(6.19)后确定。由于(6.19)的特殊性，可以利用迭加原理，将f(n)线性分解为若干个单项之和并求出各单项相应的特解，然后迭加便得到f(n)相应的特解。这使得试探法更为有效。为了方便，这里对三种特殊形式的f(n)，给出(6.19)的相应特解并列在表6-1中，可供直接套用。其中pi，i=1,2,…,s是待定常数