一、集合的划分（信息学奥赛一本通-T1315）：
关于集合自己并不是理解的很透彻：
关于a[i]的处理有两种：1.a[i]是k个子集中的一个，于是便把a[1]，a[2]......a[i - 1]划分为了k - 1个子集，这种情况共有s(n - 1, k - 1)个
2.a[i]不是k个子集中的一个，那么它肯定与其他元素构成一个子集，这种情况共有k * s(n - 1, k)个
根据乘法、加法原理，得到递归式：s(n, k) = s(n - 1, k - 1) + k * s(n - 1, k)，然后注意一些边界条件，注意s很大，要开long long
1 #include2 #include 3 4 inline long long s(int n, int k){ 5 if(k == 1 || k == n) return 1;//边界 6 if(k == 0 || n < k) return 0;//边界 7 return s(n - 1, k - 1) + k * s(n - 1, k);//递归式 8 } 9 10 int main(){11 int n, k;12 scanf("%d%d", &n, &k);13 printf("%lld", s(n, k));14 return 0;15 }
二、数的计数（信息学奥赛一本通-T1316）：
这道题暴力的递归会超时，所以用记忆化递归（类似记忆化搜索）来做...
1 #include2 #include 3 4 using namespace std; 5 6 int h[1005]; 7 8 inline void dfs(int x){ 9 if(h[x] != -1) return;//如果不等于-1，说明已经处理过了10 h[x] = 1;//它本身一种情况11 for(int i = 1; i <= x / 2; i++){12 dfs(i);//按题目要求13 h[x] += h[i];//i的情况肯定是x中的情况，因为i比x小14 }15 }16 17 int main(){18 int n;19 memset(h, -1, sizeof(h));//初始化20 scanf("%d", &n);21 dfs(n);22 printf("%d", h[n]);23 return 0;24 }
三、逆波兰表达式（信息学奥赛一本通-T1198）：
这道题虽然说没有优先级，但是感觉隐隐约约还是有的：离数字越近的运算优先级越高...然后这个题中有一个函数：atof，用来把一个string类型的数变换成float类型...
#include#include #include using namespace std;char s[1000005];inline double dfs(){ scanf("%s", s); if(s[0] == '+') return dfs() + dfs(); else if(s[0] == '-') return dfs() - dfs(); else if(s[0] == '*') return dfs() * dfs(); else if(s[0] == '/') return dfs() / dfs(); else return atof(s);//函数 }int main(){ printf("%f", dfs()); return 0;}
四、全排列（信息学奥赛一本通-T1199）：
这道题用到了回溯的一个思想：
我们如果长度达到了len，那么就输出。如果还没有，那么就一位一位枚举，如果它并没有在当前的序列中出现过，那么就把它加进来，然后找下一个。注意回溯...
1 #include2 #include 3 #include 4 5 using namespace std; 6 7 char s[10], now[10]; 8 int vis[10], len; 9 10 inline void dfs(int l){11 if(l == len){12 for(int i = 0; i < l; i++)13 printf("%c", now[i]);14 printf("\n");15 }16 else{17 for(int i = 0; i < len; i++){18 if(!vis[i]){19 now[l] = s[i];20 vis[i] = 1;21 dfs(l + 1);22 vis[i] = 0;//回溯 23 }24 }25 }26 }27 28 int main(){29 scanf("%s", s);30 len = strlen(s);31 dfs(0);32 return 0;33 }
五、分解因数（信息学奥赛一本通-T1200）：
我们用a数组存储现在已经得到的这个元素的因数，然后看看除它以外还有多少因数，最后如果等于，则tot++，但是不明白为什么a[0]初始化为2...
1 #include2 #include 3 4 using namespace std; 5 6 int m, a[40004], tot; 7 8 inline void dfs(int x, int cur){ 9 int ans = 1;10 for(int i = 1; i <= cur - 1; i++)11 ans *= a[i];12 if(ans == m) {tot++; return;}//正好 13 if(ans > m) return;14 for(int i = a[cur - 1]; i <= x; i++){15 if(x % i == 0){ 16 x /= i;17 a[cur] = i;18 dfs(x, cur + 1);19 x *= i;//回溯 20 }21 }22 }23 24 int main(){25 int n;26 scanf("%d", &n);27 for(int i = 1; i <= n; i++){28 scanf("%d", &m);29 tot = 0;30 a[0] = 2;31 dfs(m, 1);32 printf("%d\n", tot);33 }34 return 0;35 }
六、斐波那契数列（信息学奥赛一本通-T1201）：
这道题可以直接用递推做，实在太水...
1 #include2 #include 3 4 using namespace std; 5 6 int f[25], a; 7 8 inline void work(){ 9 f[1] = 1;10 f[2] = 1;11 for(int i = 3; i <= 20; i++){12 f[i] = f[i - 1] + f[i - 2];13 }14 return;15 }16 17 int main(){18 int n;19 scanf("%d", &n);20 work();21 for(int i = 1; i <= n; i++){22 scanf("%d", &a);23 printf("%d\n", f[a]);24 }25 return 0;26 }
七、Pell数列（信息学奥赛一本通-T1202）：
这道题跟T6太像了，注意不断的模就可以了...
1 #include2 #include 3 4 using namespace std; 5 6 int a[1000005]; 7 8 inline void work(){ 9 for(int i = 3; i <= 1000005; i++)10 a[i] = 2 * a[i - 1] % 32767 + a[i - 2] % 32767;11 return;12 }13 14 int main(){15 int n;16 scanf("%d", &n);17 a[1] = 1;18 a[2] = 2;19 work();20 for(int i = 1; i <= n; i++){21 int x;22 scanf("%d", &x);23 printf("%d\n", a[x] % 32767);24 }25 return 0;26 }
八、扩号匹配问题（信息学奥赛一本通-T1203）：
这道题并没有看出有什么递归，只是用了两个栈进行模拟...竟然水过了！！
1 #include2 #include 3 #include 4 #include 5 6 using namespace std; 7 8 stack st1; 9 stack st2;10 11 char s[105];12 int vis[105], l;13 14 int main(){15 while(scanf("%s", s) == 1){16 memset(vis, 0, sizeof(vis));17 l = strlen(s);18 for(int i = 0; i < l; i++){19 if(s[i] != '(' && s[i] != '[' && s[i] != ']' && s[i] != ')') continue;20 if(s[i] == '(' || s[i] == '['){21 if(s[i] == '(') st1.push(i);22 else st2.push(i);23 }24 else if(s[i] == ')' || s[i] == ']'){25 if(s[i] == ')' && !st1.empty()) {st1.pop(); continue;}26 if(st1.empty()) vis[i] = 2;27 if(s[i] == ']' && !st2.empty()) {st2.pop(); continue;}28 if(st2.empty()) vis[i] = 2;29 }30 else{31 if(s[i] == '(' || s[i] == '[') vis[i] = 1;32 else vis[i] = 2;33 }34 }35 while(!st1.empty()){36 vis[st1.top()] = 1;37 st1.pop();38 }39 while(!st2.empty()){40 vis[st2.top()] = 1;41 st2.pop();42 }43 printf("%s\n", s);44 for(int i = 0; i < l; i++){45 if(vis[i] == 1) printf("$");46 else if(vis[i] == 2) printf("?");47 else printf(" ");48 }49 printf("\n");50 }51 return 0;52 }53
九、爬楼梯（信息学奥赛一本通-T1204）：
这道题只要手模一下即可得出规律：
f[1] = 1，f[2] = 2，f[x] = f[x - 1] + f[x - 2] (x > 2)
然后可以先全部预处理一下，也可以每一个都进行递归..
1 #include2 #include 3 4 using namespace std; 5 6 7 inline int dfs(int x){ 8 if(x == 1) return 1; 9 else if(x == 2) return 2;10 else return dfs(x - 1) + dfs(x - 2);11 }12 13 int main(){14 int n;15 while(scanf("%d", &n) == 1){16 printf("%d\n", dfs(n));17 }18 return 0;19 }
十、汉诺塔问题（信息学奥赛一本通-T1205）：
这道题比较晕，对汉诺塔的原理不是很清楚：
为了解决这个问题，不妨假设已经知道怎样移动N-1个圆环了。现在，为了把起点盘上的圆环移动到目标盘，需要做如下操作：
1、把N-1个圆环从起点盘移动到（当前）没有任何圆环的过渡盘；
2、把最后一个圆环从起点盘移动到目标盘；
3、把N-1个圆环从过渡盘移动到目标盘（模仿1和2的操作方法来实现）。
1 #include2 #include 3 4 using namespace std; 5 6 inline void dfs(int n, char st, char gd, char end){ 7 if(n == 1){ 8 printf("%c->%d->%c\n", st, n, end); 9 return;10 }11 dfs(n - 1, st, end, gd);12 printf("%c->%d->%c\n", st, n, end);13 dfs(n - 1, gd, st, end);14 }15 16 int main(){17 int n;18 char a, b, c;19 cin >> n >> a >> b >> c;20 dfs(n, a, c, b);21 return 0;22 }
十一、放苹果（信息学奥赛一本通-T1206）：
f(m,n)表示m个苹果放到n个盘子中的方法数
当n>m时，必然有盘子是空的，因为最多也就用到m个盘子，因此f(m,n)=f(m,m); 当n<=m时，有两种情况： 有盘子为空时： f(m,n)=f(m,n-1)因为至少有一个为空，那去掉一个完全不影响已有的方法数（反正这个空盘子不会放苹果） 当盘子不空的时候，全部n个盘子都有装苹果，那所有的都可以拿掉一个苹果，也就是 f(m,n)=f(m-n,n) 方法数是一样的，只不过所有盘子都用上的时候每个盘子装的数量可能不一样 而n<=m的时候就是有空和没空两种情况的和：f(n,m)=f(m,n-1)+f(m-n,n) 两者递归时，n和m都会逐渐减小 ，出口为n==1||m==0的时候，都只有一种方法 1 #include2 #include 3 4 using namespace std; 5 6 inline int dfs(int m, int n){ 7 if(m == 0 || n == 1) return 1; 8 if(m < n) return dfs(m, m); 9 else return dfs(m, n - 1) + dfs(m - n, n);10 }11 12 int main(){13 int t, n, m;14 scanf("%d", &t);15 while(t--){16 scanf("%d%d", &m, &n);17 printf("%d\n", dfs(m, n));18 }19 return 0;20 }
十二、求最大公约数问题（信息学奥赛一本通-T1207）：
没什么好解释的，gcd的模板，也很好理解...
1 #include2 #include 3 4 using namespace std; 5 6 inline int gcd(int a, int b){ 7 return b == 0 ? a : gcd(b, a % b); 8 } 9 10 int main(){11 int a, b;12 scanf("%d%d", &a, &b);13 printf("%d", gcd(a, b));14 return 0;15 }
十三、2的幂次方表示（信息学奥赛一本通-T1208）：
把一个数想成二进制，那么像十进制一样，取最后一位则为%2，详见代码...
1 #include2 #include 3 4 using namespace std; 5 6 inline void dfs(int n, int cur){ 7 //n为被分解数，cur为二进制位数，n % 2为位数上的数值 8 if(n == 0) return; 9 dfs(n / 2, cur + 1);10 if(n % 2){11 if(n / 2) printf("+");//如果n不为0且n % 2不为0证明这不是第一个2的幂次方，输出+12 if(cur == 1) printf("2");13 else{14 printf("2(");15 if(cur == 0) printf("0");16 else dfs(cur, 0);17 printf(")");18 }19 }20 }21 22 int main(){23 int n;24 scanf("%d", &n);25 dfs(n, 0);26 return 0;27 }
十四、分数求和（信息学奥赛一本通-T1209）：
这道题思路很简单，暴力地相加，先不约分，将所有分母相乘作为分母，然后看每一个分数的分母比原来扩大了多少倍，分子跟着扩大多少倍。然后找它们的gcd，最后约分，注意分母为1即可...
1 #include2 #include 3 4 using namespace std; 5 6 bool fir; 7 8 int p[15], q[15]; 9 int ans1, ans2 = 1;10 char c;11 12 inline int gcd(int a, int b){13 return b == 0 ? a : gcd(b, a % b);14 }15 16 int main(){17 int n;18 scanf("%d", &n);19 for(int i = 1; i <= n; i++){20 scanf("%d%c%d", &p[i], &c, &q[i]);21 }22 for(int i = 1; i <= n; i++) ans2 *= q[i];23 for(int i = 1; i <= n; i++){24 ans1 += (ans2 / q[i]) * p[i];25 }26 int t = gcd(ans1, ans2);27 if(ans2 / t == 1) printf("%d", ans1);28 else printf("%d/%d", ans1 / t, ans2 / t);29 return 0;30 }
十五、因子分解（信息学奥赛一本通-T1210）：
这道题很简单，没有想象中那样复杂，并不需要欧拉筛，因为是从小到大找因数，所以找到的因数都是质数，反证法可以证明...
1 #include2 #include 3 4 using namespace std; 5 6 int n, cnt; 7 int tot[105]; 8 bool fir; 9 10 inline void dfs(int n, int l){11 if(n == 0 || l > n) return;12 while (n % l == 0){13 tot[l] ++;14 n /= l;15 }16 dfs(n, l + 1);17 }18 19 inline void work(){20 for(int i = 2; i <= n; i++){21 if(tot[i] == 0) continue;22 if(!fir){23 if(tot[i] == 1) printf("%d", i);24 else printf("%d^%d", i, tot[i]);25 fir = 1;26 }27 else{28 if(tot[i] == 1) printf("*%d", i);29 else printf("*%d^%d", i, tot[i]);30 }31 }32 }33 34 int main(){35 scanf("%d", &n);36 dfs(n, 2);37 work();38 return 0;39 }
十六、判断元素是否存在（信息学奥赛一本通-T1211）：
一开始自己的思路和正解正好相反，自己是将所有的集合中的可能进行一个初始化，可是发现并没有边界，所以这道题的思路是逆着来的，看x按照题中的规律往后退，看看能否推到k，注意第十行，不能没有...
1 #include2 #include 3 4 using namespace std; 5 6 int k; 7 8 inline int dfs(int x){ 9 if(x == k) return 1;10 if((x - 1) % 2 == 0 && (x - 1) % 3 == 0) return (dfs((x - 1) / 2) || dfs((x - 1) / 3));11 if((x - 1) % 2 == 0) return dfs((x - 1) / 2);12 if((x - 1) % 3 == 0) return dfs((x - 1) / 3);13 return 0;14 }15 16 int main(){17 int x;18 scanf("%d,%d", &k, &x);19 if(dfs(x)) printf("YES");20 else printf("NO");21 return 0;22 }