等级标准
掌握算法以及算法性能、算法效率的概念；掌握基本算法中枚举的概念；掌握基本算法中递归的概念；掌握自调用函数的应用，实现基本算法中的递归方法；掌握基本算法中由递归变递推的方法；能够使用上述方法编写指定功能的正确完整的程序。1.课程冲突
考试题目
小 A 修了 n 门课程, 第 i 门课程是从第 ai 天一直上到第 bi 天。
定义两门课程的冲突程度为 : 有几天是这两门课程都要上的。
例如 a1=1,b1=3,a2=2,b2=4 时, 这两门课的冲突程度为 2。
现在你需要求的是这 n 门课中冲突程度最大的两门课的冲突程度。
时间限制：1000
内存限制：65536
输入
第一行一个正整数 n 表示课程数量。 接下来 n 行,每行两个正整数 ai,bi。 2 ≤ n≤ 1000, 1 ≤ ai ≤ bi ≤ 1000。
输出
输出一个整数表示最大的冲突程度
样例输入
3
1 3
2 4
5 5
样例输出
2
参考答案
#include <bits/stdc++.h>using namespace std;//#define PPYDEBUGstruct lesson{int no; //课程编号int a; //课程开始a天int b; //课程结束b天};int max_chongtu(lesson x, lesson y){int r = min(x.b, y.b) - max(x.a, y.a) + 1;if(r < 0){r = 0;}#ifdef PPYDEBUGprintf("%d = x[%d,%d] - y[%d,%d]\n", r, x.a, x.b, y.a, y.b);#endifreturn r;}int main() {#ifdef LOCALfreopen("09_3_1.in", "r", stdin);#endifint n;scanf("%d", &n);lesson le[1010];for(int i = 0; i < n; i++){le[i].no = i + 1;scanf("%d%d", &le[i].a, &le[i].b);}int r = 0;for(int i = 0; i < n; i++){for(int j = i + 1; j < n; j++){r = max(r, max_chongtu(le[i], le[j]));}}printf("%d", r);return 0;}
2.42点
考试题目
42是：
·组合数学上的第5个卡特兰数
·字符’'的ASCII码
·钼的原子序数
·6与9的乘积结果的13进制表示
·生命、宇宙以及任何事情的终极答案
·以及……表达式(1+5)/2(6-4)7的值
因此，小机器人Marvin发明了这个叫42点的小游戏。在这个游戏中，玩家会获得n个数。玩家需要使用’+‘、’-‘、’‘、’/‘、’(‘、’)'以及这n个数构成一个合法的中缀表达式，并使得该表达式的值为42。n个数之间的顺序可以改变。表达式运算过程中只能出现整数。
由于过于抑郁，Marvin无力完成这个游戏，于是来找你帮忙。你的任务是对于给定的n个数，判断他们是否能根据上述游戏规则算出42。
时间限制：1000
内存限制：65536
输入
第一行为一个数n，1<=n<=6。 第二行为n个数，每个数均为[1,13]范围内的整数。
输出
输出一行，若可以算出42则输出“YES”，否则输出“NO”（注意大小写）。
样例输入
6
1 5 2 6 4 7
样例输出
YES
参考答案
#include <bits/stdc++.h>using namespace std;#define PPYDEBUGbool dfs(int a[], int n){if(n == 1){return a[0] == 42;}for(int i = 0; i < n; i++){for(int j = i + 1; j < n; j++){//b[]数组为a[]数组去掉a[i]和a[j]后形成的新数组int b[10];int m = 0;for(int k = 0; k < n; k++){if(k == i || k == j) continue;b[m] = a[k];m++;}//最后一位等于去掉的a[i]和a[j]之间的加减乘除结果//此时m = n - 2#ifdef PPYDEBUGprintf("n[%d], m[%d]\n", n, m);#endifb[m] = a[i]+a[j]; if(dfs(b, m + 1)) return 1;b[m] = a[i]-a[j]; if(dfs(b, m + 1)) return 1;b[m] = a[j]-a[i]; if(dfs(b, m + 1)) return 1;b[m] = a[i]*a[j]; if(dfs(b, m + 1)) return 1;if(a[i] != 0) b[m] = a[j]/a[i]; if(dfs(b, m + 1)) return 1;if(a[j] != 0) b[m] = a[i]/a[j]; if(dfs(b, m + 1)) return 1;}}return 0;}int main(){#ifdef LOCALfreopen("1107_0503.in", "r", stdin);#endifint n;int a[10];cin >> n;for(int i = 0; i < n; i++) cin >> a[i];if(dfs(a, n)) cout << "YES" << endl;else cout << "NO" << endl;return 0;}
3.最长下坡
考试题目
小明天天沿着未名湖环湖路跑，有时候也觉得蛮累。
累的时候跑下坡就很开心。小明想知道最长的一段下坡有多长。
环湖路是个圆形，周长n米。每隔一米测一下路面高度，两个测高点之间的高度是单调变化或不变的。
问最长的一段下坡有多少米长。小明只能顺时针跑。下坡必须高度单调减少。
时间限制：1000
内存限制：65536
输入
第一行是整数n，表示环湖路一共n米长(2<=n<=100)。 第二行是n个整数，每个整数范围[0,10000]，按顺时针顺序给出了n个测高点的高度
输出
最长下坡路段的长度
样例输入
样例输入1:
5
2 1 5 6 3
样例输入2：
5
2 1 5 4 3
样例输入3:
4
1 1 1 1
样例输出
样例输出1：
3
样例输出2
4
样例输出3
0
提示
这是个简单枚举题，枚举起点即可
参考答案
#include <bits/stdc++.h>using namespace std;int main() {#ifdef LOCALfreopen("09_3_3.in", "r", stdin);#endifint n;scanf("%d", &n);int a[200];for(int i = 0; i < n; i++){scanf("%d", &a[i]);}//这题有个坑，就是<环湖>for(int i = 0; i < n; i++){a[n + i] = a[i];}int dp[200];dp[0] = 0;int dp_max = 0;for(int i = 1; i < 2 * n; i++){if(a[i] <= a[i - 1]){dp[i] = dp[i - 1] + 1;}else{dp[i] = 0;}dp_max = max(dp_max, dp[i]);}printf("%d", dp_max);return 0;}
4.吃糖果
考试题目
现有n(20 > n > 0)个糖果,每天可以吃1个,也可以每天吃2个,也可以每天吃3个，请计算共有多少种不同的吃法。
时间限制：1000
内存限制：65536
输入
输入的每一行包括一组测试数据，即为糖果数n。最后一行为0，表示测试结束。
输出
每一行输出对应一行输入的结果，即为吃法的数目。
样例输入
1
2
3
4
0
样例输出
1
2
4
7
参考答案
#include <bits/stdc++.h>using namespace std;int main() {#ifdef LOCALfreopen("09_3_4.in", "r", stdin);#endifint dp[30];dp[0] = 1;dp[1] = 2;dp[2] = 4;//111,12,21,3for(int i = 3; i < 20; i++){dp[i] = dp[i - 3] + dp[i - 2] + dp[i - 1];}int n;do{scanf("%d", &n);//printf("%d\n", n);if(n == 0){break;}printf("%d\n", dp[n - 1]);}while(true);return 0;}
5.放苹果
考试题目
把M个同样的苹果放在N个同样的盘子里，允许有的盘子空着不放，问共有多少种不同的分法？（用K表示）5，1，1和1，5，1 是同一种分法。
时间限制：1000
内存限制：65536
输入
第一行是测试数据的数目t（0 <= t <= 20）。以下每行均包含二个整数M和N，以空格分开。1<=M，N<=10。
输出
对输入的每组数据M和N，用一行输出相应的K。
样例输入
1
7 3
样例输出
8
解题思路
将这8组数分成2组
第一组，可以发现最后一个数总是为0，其实可以理解成这一组数与m = 7,n = 2也是相等的
7 0 0
6 1 0
5 2 0
4 3 0
第二组，如果将每一个数都减1,可以发现，这组数的个数与m = 4,n = 3相等
5 1 1
4 2 1
3 3 1
3 2 1
参考答案
#include <bits/stdc++.h>using namespace std;int dp(int m, int n){if(m == 0 or n == 1){//如果，碟子只有1个，无论苹果有多少个都只有一种放法return 1;}if(n > m){//如果，碟子的个数大于苹果的个数return dp(m, m);}else{return dp(m, n - 1) + dp(m - n, n);}}int main() {#ifdef LOCALfreopen("09_3_5.in", "r", stdin);#endifint t;scanf("%d", &t);int n, m;for(int i = 0; i < t; i++){scanf("%d%d", &m, &n);printf("%d", dp(m, n));}return 0;}
