一, 集合的划分(信息学奥赛一本通 - 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
- #include<cstdio>
- #include<iostream>
- inline long long s(int n, int k){
- if(k == 1 || k == n) return 1;// 边界
- if(k == 0 || n <k) return 0;// 边界
- return s(n - 1, k - 1) + k * s(n - 1, k);// 递归式
- }
- int main(){
- int n, k;
- scanf("%d%d", &n, &k);
- printf("%lld", s(n, k));
- return 0;
- }
- 1315
二, 数的计数(信息学奥赛一本通 - T1316):
这道题暴力的递归会超时, 所以用记忆化递归 (类似记忆化搜索) 来做...
- #include<cstdio>
- #include<cstring>
- using namespace std;
- int h[1005];
- inline void dfs(int x){
- if(h[x] != -1) return;// 如果不等于 - 1, 说明已经处理过了
- h[x] = 1;// 它本身一种情况
- for(int i = 1; i <= x / 2; i++){
- dfs(i);// 按题目要求
- h[x] += h[i];//i 的情况肯定是 x 中的情况, 因为 i 比 x 小
- }
- }
- int main(){
- int n;
- memset(h, -1, sizeof(h));// 初始化
- scanf("%d", &n);
- dfs(n);
- printf("%d", h[n]);
- return 0;
- }
- 1316
三, 逆波兰表达式(信息学奥赛一本通 - 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;
- }
- 1198
四, 全排列(信息学奥赛一本通 - T1199):
这道题用到了回溯的一个思想:
我们如果长度达到了 len, 那么就输出. 如果还没有, 那么就一位一位枚举, 如果它并没有在当前的序列中出现过, 那么就把它加进来, 然后找下一个. 注意回溯...
- #include<cstdio>
- #include<iostream>
- #include<cstring>
- using namespace std;
- char s[10], now[10];
- int vis[10], len;
- inline void dfs(int l){
- if(l == len){
- for(int i = 0; i <l; i++)
- printf("%c", now[i]);
- printf("\n");
- }
- else{
- for(int i = 0; i < len; i++){
- if(!vis[i]){
- now[l] = s[i];
- vis[i] = 1;
- dfs(l + 1);
- vis[i] = 0;// 回溯
- }
- }
- }
- }
- int main(){
- scanf("%s", s);
- len = strlen(s);
- dfs(0);
- return 0;
- }
- 1199
五, 分解因数(信息学奥赛一本通 - T1200):
我们用 a 数组存储现在已经得到的这个元素的因数, 然后看看除它以外还有多少因数, 最后如果等于, 则 tot++, 但是不明白为什么 a[0]初始化为 2...
- #include<cstdio>
- #include<iostream>
- using namespace std;
- int m, a[40004], tot;
- inline void dfs(int x, int cur){
- int ans = 1;
- for(int i = 1; i <= cur - 1; i++)
- ans *= a[i];
- if(ans == m) {tot++; return;}// 正好
- if(ans> m) return;
- for(int i = a[cur - 1]; i <= x; i++){
- if(x % i == 0){
- x /= i;
- a[cur] = i;
- dfs(x, cur + 1);
- x *= i;// 回溯
- }
- }
- }
- int main(){
- int n;
- scanf("%d", &n);
- for(int i = 1; i <= n; i++){
- scanf("%d", &m);
- tot = 0;
- a[0] = 2;
- dfs(m, 1);
- printf("%d\n", tot);
- }
- return 0;
- }
- 1200
六, 斐波那契数列(信息学奥赛一本通 - T1201):
这道题可以直接用递推做, 实在太水...
- #include<cstdio>
- #include<iostream>
- using namespace std;
- int f[25], a;
- inline void work(){
- f[1] = 1;
- f[2] = 1;
- for(int i = 3; i <= 20; i++){
- f[i] = f[i - 1] + f[i - 2];
- }
- return;
- }
- int main(){
- int n;
- scanf("%d", &n);
- work();
- for(int i = 1; i <= n; i++){
- scanf("%d", &a);
- printf("%d\n", f[a]);
- }
- return 0;
- }
- 1201
七, Pell 数列(信息学奥赛一本通 - T1202):
这道题跟 T6 太像了, 注意不断的模就可以了...
- #include<cstdio>
- #include<iostream>
- using namespace std;
- int a[1000005];
- inline void work(){
- for(int i = 3; i <= 1000005; i++)
- a[i] = 2 * a[i - 1] % 32767 + a[i - 2] % 32767;
- return;
- }
- int main(){
- int n;
- scanf("%d", &n);
- a[1] = 1;
- a[2] = 2;
- work();
- for(int i = 1; i <= n; i++){
- int x;
- scanf("%d", &x);
- printf("%d\n", a[x] % 32767);
- }
- return 0;
- }
- 1202
八, 扩号匹配问题(信息学奥赛一本通 - T1203):
- #include<cstdio>
- #include<iostream>
- #include<cstring>
- #include<stack>
- using namespace std;
- stack<int> st1;
- stack<int> st2;
- char s[105];
- int vis[105], l;
- int main(){
- while(scanf("%s", s) == 1){
- memset(vis, 0, sizeof(vis));
- l = strlen(s);
- for(int i = 0; i <l; i++){
- if(s[i] != '(' && s[i] != '[' && s[i] != ']' && s[i] != ')') continue;
- if(s[i] == '(' || s[i] == '['){
- if(s[i] == '(') st1.push(i);
- else st2.push(i);
- }
- else if(s[i] == ')' || s[i] == ']'){
- if(s[i] == ')' && !st1.empty()) {st1.pop(); continue;}
- if(st1.empty()) vis[i] = 2;
- if(s[i] == ']' && !st2.empty()) {st2.pop(); continue;}
- if(st2.empty()) vis[i] = 2;
- }
- else{
- if(s[i] == '(' || s[i] == '[') vis[i] = 1;
- else vis[i] = 2;
- }
- }
- while(!st1.empty()){
- vis[st1.top()] = 1;
- st1.pop();
- }
- while(!st2.empty()){
- vis[st2.top()] = 1;
- st2.pop();
- }
- printf("%s\n", s);
- for(int i = 0; i < l; i++){
- if(vis[i] == 1) printf("$");
- else if(vis[i] == 2) printf("?");
- else printf(" ");
- }
- printf("\n");
- }
- return 0;
- }
- 1203
- #include<cstdio>
- #include<iostream>
- using namespace std;
- inline int dfs(int x){
- if(x == 1) return 1;
- else if(x == 2) return 2;
- else return dfs(x - 1) + dfs(x - 2);
- }
- int main(){
- int n;
- while(scanf("%d", &n) == 1){
- printf("%d\n", dfs(n));
- }
- return 0;
- }
- 1204
来源: http://www.bubuko.com/infodetail-3147461.html