一、集合的划分（信息学奥赛一本通-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 #include<cstdio> 2 #include<iostream> 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 #include<cstdio> 2 #include<cstring> 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<cstdio> #include<iostream> #include<algorithm> 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 #include<cstdio> 2 #include<iostream> 3 #include<cstring> 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 #include<cstdio> 2 #include<iostream> 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 #include<cstdio> 2 #include<iostream> 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 #include<cstdio> 2 #include<iostream> 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 #include<cstdio> 2 #include<iostream> 3 #include<cstring> 4 #include<stack> 5 6 using namespace std; 7 8 stack<int> st1; 9 stack<int> 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 #include<cstdio> 2 #include<iostream> 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 }
十、
原文：https://www.cnblogs.com/New-ljx/p/11299369.html
