问题 A: 单词排序 题目描述 小红学会了很多英文单词，妈妈为了帮小红加强记忆，拿出纸、笔，把 N 个单词写在纸上的一行里，小红看了几秒钟后，将这张纸扣在桌子上。妈妈问小红：“你能否将这 N 个单词按照字典排列的顺序，从小到大写出来？”小红按照妈妈的要求写出了答案。现在请你编写程序帮助妈妈检查小红的答案是否正确。注意：所有单词都由小写字母组成，单词两两之间用一个空格分隔。
输入 输入包含两行。
第一行仅包括一个正整数N(0<N≤26)。
第二行包含N个单词，表示妈妈写出的单词，两两之间用一个空格分隔。
单个单词长度不超过1010。
输出 输出仅有一行。针对妈妈写出的单词，按照字典排列的顺序从小到大排列成一行的结果，每个单词后带一个空格。
样例输入
4
样例输出
boy city student tree
思路 首先，用一个string类型的数组source_str[1010]接收输入原始字符集合，然后，利用选择排序法对数组source_str[1010]进行排序，最后，输出即可。
代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 #include <iostream> #include <string> using namespace std; string source_str[1010]; int main() { void sort(string str[1010], int num); int N; cin >> N; for(int i = 0; i < N; i++) cin >> source_str[i]; sort(source_str, N); for(int j = 0; j < N; j++) cout << source_str[j] << endl; return 0; } void sort(string str[1010], int num) { int i, j, k; string tmp_str; for(int i = 0; i < num; i++) { k = i; for(int j = i + 1; j < num; j++) { if(str[j] < str[k]) { k = j; tmp_str = str[k]; str[k] = str[i]; str[i] = tmp_str; } } } }
问题 B: 求数组的最长递减子序列 题目描述 给定一个整数序列，输出它的最长递减（注意不是“不递增”）子序列。
输入 输入包括两行，第一行包括一个正整数N（N<=1000），表示输入的整数序列的长度。第二行包括用空格分隔开的N个整数，整数范围区间为[-30000,30000]。
输出 输出最长递减子序列，数字之间有一个空格。
样例输入
8
样例输出
9 5 4 3 2
思路 首先，利用数组source_arr[max_num]存储输入的待排整数序列，然后利用两个for循环将dp[max_num]和last[max_num]设置成如下格式，接着，利用ansa存储结果，最后，输出即可。
代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 #include <iostream> using namespace std; int main() { const int max_num = 1005; int dp[max_num], last[max_num]; int N, source_arr[max_num], ans = 0, ansp = 1, ansa[max_num]; cin >> N; for(int i = 1; i <= N; i++) cin >> source_arr[i]; dp[1] = 1; last[1] = -1; for(int i = 2; i <= N; i++) { dp[i] = 1; last[i] = -1; for(int j = 1; j < i; j++) { if(source_arr[j] > source_arr[i] && dp[j] + 1 > dp[i]) { dp[i] = dp[j] + 1; last[i] = j; } } } for(int i = 1; i <= N; i++) { if(dp[i] > ans) { ans = dp[i]; ansp = i; } } int j = ansp; for(int i = ans; ; i--) { ansa[i] = source_arr[j]; if(last[j] == -1) break; j = last[j]; } for(int i = 1; i <= ans; i++) cout << ansa[i] << " "; cout << endl; return 0; }
问题 C: 矩形滑雪场 题目描述 zcb喜欢滑雪。他来到了一个滑雪场，这个滑雪场是一个矩形，为了简便，我们用r行c列的矩阵来表示每块地形。为了得到更快的速度，滑行的路线必须向下倾斜。 例如样例中的那个矩形，可以从某个点滑向上下左右四个相邻的点之一。例如24-17-16-1，其实25-24-23…3-2-1更长，事实上这是最长的一条。
输入 第1行:两个数字r，c(1 ≤ r, c ≤ 100)，表示矩阵的行列。第2..r+1行:每行c个数，表示这个矩阵。
输出 仅一行:输出1个整数，表示可以滑行的最大长度。
样例输入
5 5
样例输出
25
思路 二维数组，一看就很难的样子，那我们就把它降维打击一下。二维->一维。
怎么实现呢？
定义结构体node，存储坐标x，y和高度h；}和;之间直接定义数组
写一个bool check(int i,int j)函数，用来判断两点是否为相邻点（上、下、左、右）；
以上为main()函数中的实现做铺垫。
输入时怎么处理？直接两层for：（比较巧妙）
1 2 3 ski[n].x = i; ski[n].y = j; cin >> ski[n].h;
输入完后sort()一下，注意在结构体中重载下<，按h从大到小排；
这样就有点像DP：最长上升子序列问题了
初始化dp[i] = 1
此时，对于第i个结点，前面的结点j的h都更大，那就判断下每个点是否是相邻点（前面定义的check()函数），若是，则执行
1 dp[i] = max(dp[i],dp[j]+1);
代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 #include <iostream> #include <algorithm> using namespace std; const int max_num = 5e4 + 1; struct node { int x, y, h; bool operator < (const node &c) const { return h > c.h; } } ski[max_num]; int dp[max_num]; int r, c; int main() { bool check(int i, int j); cin >> r; cin >> c; int n = 0; for(int i = 1; i <= r; i++) { for(int j = 1;j <= c; j++) { ski[n].x = i; ski[n].y = j; cin >> ski[n].h; n++; } } sort(ski, ski + n); int ans = 0; for(int i = 0; i < n; i++) { dp[i] = 1; for(int j = 0; j < i; j++) if(check(i, j)) dp[i] = max(dp[i], dp[j] + 1); ans = max(ans, dp[i]); } cout << ans << endl; return 0; } bool check(int i, int j) { if(abs(ski[i].x - ski[j].x) + abs(ski[i].y - ski[j].y) == 1) return true; return false; }
问题 E: 区间包含问题 题目描述 已知 n 个左闭右开区间 [a,b)，对其进行 m 次询问，求区间[l,r]最多可以包含 n 个区间中的多少个区间，并且被包含的所有区间都不相交。
输入 输入包含多组测试数据，对于每组测试数据：
第一行包含两个整数 n ,m (1≤n≤100000,1≤m≤100) 。
接下来 n 行每行包含两个整数 a ,b (0 ≤ a < b ≤ 10^9) 。
接下来 m 行每行包含两个整数 l ,r (0 ≤ l < r ≤ 10^9) 。
输出 对于每组测试数据，输出 m 行，每行包含一个整数。
数据过大请使用快速输入输出。
样例输入
4 3
样例输出
1
思路 输入结束后，把所有活动按结束时间从小到大排序。
定义ans，先给它赋值1。
循环遍历所有活动，符合不相交、不越界就可选。
千万别写if(e == c.e) return b < c.b;否则必定WA，不知为何。
千万要在结束时间超过r后跳出循环，不然必定TLE。
千万不要用cin、cout，不然好像也是必定TLE。
代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 #include <iostream> #include <stdio.h> #include <algorithm> using namespace std; const int max_num = 1e5 + 5; struct s { int b, e; bool operator < (const s&c) const { //if(e == c.e) return b < c.b; return e < c.e; } } interval[max_num]; int main() { int n, m, l, r; while (~scanf("%d %d", &n, &m)) { for (int i = 0; i < n; i++) { scanf("%d %d", &interval[i].b, &interval[i].e); } sort(interval, interval + n); for (int cas = 0; cas < m; cas++) { scanf("%d %d", &l, &r); int j = 0, ans = 0; while (interval[j].b < l) j++; for (int i = j; i < n && interval[i].e <= r; i++) { if (interval[i].b >= interval[j].e || i == j) { ans++; j = i; } } printf("%d\n", ans); } } return 0; }
问题 F: 最长子序列 题目描述 在一个数组中找出和最大的连续几个数。（至少包含一个数）
例如：
数组A[] = [-2,1,-3,4,-1,2,1,-5,4]，则连续的子序列[4,-1,2,1]有最大的和6.
输入 第一行输入一个不超过1000的整数n。
第二行输入n个整数A[i]。
输出 输出一个整数，表示最大的和。
样例输入
3
样例输出
2
思路 此题类似于我前面写过的一篇文章《CUMTOJ算法实验二》，具体思路就是最大子段和的求解，详解见如下链接
https://xingshuaikun.gitee.io/2019/10/12/CUMTOJ%E7%AE%97%E6%B3%95%E5%AE%9E%E9%AA%8C%E4%BA%8C/
代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 #include <iostream> using namespace std; const int max_num = 10000; int main() { int max(int a, int b); int n, arr[max_num], A[max_num] = { 0 }; while (cin >> n) { int result = 0; for (int i = 1; i <= n; i++) { cin >> arr[i]; if (A[i - 1] > 0) A[i] = A[i - 1] + arr[i]; else A[i] = arr[i]; result = max(result, A[i]); } cout << result << endl; } return 0; } int max(int a, int b) { return (a > b ? a : b); }
问题 G: 元素整除问题 题目描述 输入20个整数，输出其中能被数组中其它元素整除的那些数组元素。
输入 输入20个整数
输出 按输入顺序输出符合要求的数字，每行输出一个整数。
样例输入
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21
样例输出
4
思路 首先，用一个数组a存储输入的20个数字，然后，利用continue处理不能求余的数并将其输出即可。
代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 #include <iostream> using namespace std; const int arr_num = 20; int main() { int i, j, k, a[arr_num]; k = 0; for (i = 0; i < arr_num; i++) cin >> a[i]; for (i = 0; i < arr_num; i++) { k = i; a[k] = a[i]; for (j = 0; j < arr_num; j++) { if (k == j) { continue; } else { if (a[k] % a[j] == 0) { cout << a[k] << endl; break; } } } } return 0; }
问题 H: 渊子赛马 题目描述 赛马是一古老的游戏，早在公元前四世纪的中国，处在诸侯割据的状态，历史上称为“战国时期”。在魏国作官的孙膑，因为受到同僚庞涓的迫害，被齐国使臣救出后，到达齐国国都。 赛马是当时最受齐国贵族欢迎的娱乐项目。上至国王，下到大臣，常常以赛马取乐，并以重金赌输赢。田忌多次与国王及其他大臣赌输赢，屡赌屡输。一天他赛马又输了，回家后闷闷不乐。孙膑安慰他说：“下次有机会带我到马场看看，也许我能帮你。” 孙膑仔细观察后发现，田忌的马和其他人的马相差并不远，只是策略运用不当，以致失败。 比赛前田忌按照孙膑的主意，用上等马鞍将下等马装饰起来，冒充上等马，与齐王的上等马比赛。第二场比赛，还是按照孙膑的安排，田忌用自己的上等马与国王的中等马比赛，在一片喝彩中，只见田忌的马竟然冲到齐王的马前面，赢了第二场。关键的第三场，田忌的中等马和国王的下等马比赛，田忌的马又一次冲到国王的马前面，结果二比一，田忌赢了国王。 就是这么简单，现在渊子也来赛一赛马。假设每匹马都有恒定的速度，所以速度大的马一定比速度小的马先到终点（没有意外！！）。不允许出现平局。最后谁赢的场数多于一半(不包括一半)，谁就是赢家(可能没有赢家)。渊子有 N(1<=n<=1000)匹马参加比赛。对手的马的数量与渊子马的数量一样，并且知道所有的马的速度。聪明的你来预测一下这场世纪之战的结果，看看渊子能否赢得比赛。
输入 输入有多组测试数据。 每组测试数据包括 3 行： 第一行输入 N。表示马的数量。 第二行有 N 个整型数字，即渊子的 N 匹马的速度。 第三行有 N 个整型数字，即对手的 N 匹马的速度。 当 N 为 0 时退出。
输出 若通过聪明的你精心安排，如果渊子能赢得比赛，那么输出YES。 否则输出NO。
样例输入
5
样例输出
YES
思路 首先，利用两个数组yuanZi和duiShou存储输入的n个数字，然后，利用排序函数sort()对两个函数进行排序，接着，不是最大的与最小的相比较，而是挑较大的与较小的比较，用一个win存储能赢的局数。
代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 #include <iostream> #include <algorithm> using namespace std; const int max_num = 1000; int main() { int yuanZi[max_num] = { 0 }, duiShou[max_num] = { 0 }, i, j, win = 0, n, t, k; while (cin >> n && n != 0) { for (j = 0; j < n; j++) cin >> yuanZi[j]; for (j = 0; j < n; j++) cin >> duiShou[j]; sort(yuanZi, yuanZi + n); sort(duiShou, duiShou + n); for (i = 0, j = 0, win = 0; i < n; i++) { if (yuanZi[i] > duiShou[j]) { win++; j++; } } if (win > n / 2) cout << "YES" << endl; else cout << "NO" << endl; } return 0; }
问题 I: 最长上升子序列 题目描述 给定一个长度为n的字符串S（只包含小写字母），给出q次查询，对于每次查询x，求出以S[x]（下标从0开始）为起始的最长上升子序列的长度（严格增）。
输入 第一行两个整数n,q(1<=n,q<=1e5)，意义见题目描述。
第二行一个长度为n的字符串S。
第三行q个整数x(0 <= x < n)，表示q次查询。
输出 输出q个数（以空格分割，行末有空格），表示以S[x]为起始的最长上升子序列的长度。
样例输入
10 3
样例输出
3 2 2
思路 首先，用一个数组S存储输入的长度为n的字符串，然后，利用LIS()函数求最长上升子序列，在我电脑上结果正确，但在OJ上就是运行错误50%，不管了，这一题就这样了。
代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 #include <iostream> #include <algorithm> using namespace std; const int max_num = 1000; int main() { int LIS(char A[], int n); int n, q, tmp[max_num] = { 0 }; char S[max_num] = { '\0' }; cin >> n >> q; for (int i = 0; i < n; i++) cin >> S[i]; for (int j = 0; j < q; j++) { cin >> tmp[j]; char tmp_str[max_num] = { '\0' }; for (int y = 0; y < n - tmp[j]; y++) tmp_str[y] = S[y + tmp[j]]; cout << LIS(tmp_str, n - tmp[j]) << " "; } cout << endl; return 0; } int LIS(char A[], int n) { int* d = new int[n]; int len = 1; int i, j; for (i = 0; i < n; i++) { d[i] = 1; for (j = 0; j < i; j++) { if (A[j] < A[i] && (d[j] + 1) > d[i]) d[i] = d[j] + 1; } if (d[i] > len) len = d[i]; } delete[] d; return len; }
问题 J: 区间第k小 题目描述 花花上算法课又偷偷摸鱼。她今天刚学会如何求解区间第k小的数，但是感觉没什么意思。于是她将题目稍稍改动了一下：对于一个长度为n的数列a来说，一共有n*(n+1)/2个子区间，对于数列a的每一个子区间，如果这个子区间的长度小于k，我们不管它，否则把该子区间的第k小的数加入新数列b（初始为空）。花花并不关心数列b里面的元素是什么，她只想知道新数列b中第k小的元素是多少。
例如，一个长度为4的数列a={5,3,4,9}，当k取3时只有三个子区间长度是>=3的：{5,3,4},{3,4,9}和{5,3,4,9}。分别提取各自的第3小的数加入b数列得到{5,9,5},其中第3小的数为9。
输入 第一行两个数n，k（1<=n, k<=1e5）意义见题目描述
第二行n个数表示数列a中的元素ai。(1<=ai<=1e9)
数据保证数列b中的元素个数不少于k个
输出 输出一个数，表示数列b中的第k小的数
样例输入
4 3
样例输出
9
思路 本人不才，没找到最终答案，所以就给出求一个数组的第k小的代码。
代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 #include <iostream> #include <algorithm> using namespace std; const int max_num = 100000; int main() { int arr[max_num] = { 0 }; int n, k, i; cin >> n >> k; for(i = 0; i < n; i++) cin >> arr[i]; sort(arr, arr + n); cout << arr[k - 1] << endl; return 0; }
转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达，可以邮件至 xingshuaikun@163.com。
