CUMTOJ算法作业二
问题 A: 单词排序
题目描述
小红学会了很多英文单词，妈妈为了帮小红加强记忆，拿出纸、笔，把 N 个单词写在纸上的一行里，小红看了几秒钟后，将这张纸扣在桌子上。妈妈问小红：“你能否将这 N 个单词按照字典排列的顺序，从小到大写出来？”小红按照妈妈的要求写出了答案。现在请你编写程序帮助妈妈检查小红的答案是否正确。注意：所有单词都由小写字母组成，单词两两之间用一个空格分隔。
输入
输入包含两行。
第一行仅包括一个正整数N(0<N≤26)。
第二行包含N个单词，表示妈妈写出的单词，两两之间用一个空格分隔。
单个单词长度不超过1010。
输出
输出仅有一行。针对妈妈写出的单词，按照字典排列的顺序从小到大排列成一行的结果，每个单词后带一个空格。
样例输入
4
city boy tree student
样例输出
boy city student tree
思路
首先，用一个string类型的数组source_str[1010]接收输入原始字符集合，然后，利用选择排序法对数组source_str[1010]进行排序，最后，输出即可。
代码
#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 4 3 2 5 4 3 2
样例输出
9 5 4 3 2
思路
首先，利用数组source_arr[max_num]存储输入的待排整数序列，然后利用两个for循环将dp[max_num]和last[max_num]设置成如下格式，接着，利用ansa存储结果，最后，输出即可。
代码
#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
1 2 3 4 5
16 17 18 19 6
15 24 25 20 7
14 23 22 21 8
13 12 11 10 9
样例输出
25
思路
二维数组，一看就很难的样子，那我们就把它降维打击一下。二维->一维。
怎么实现呢？
-
定义结构体
node
，存储坐标
x
，
y
和高度
h
；
一般在定义后在
}
和
;
之间直接定义数组 -
写一个
bool check(int i,int j)
函数，用来判断两点是否为相邻点（上、下、左、右）；
以上为main()函数中的实现做铺垫。
- 输入时怎么处理？直接两层for：（比较巧妙）
ski[n].x = i;
ski[n].y = j;
cin >> ski[n].h;
- 输入完后sort()一下，注意在结构体中重载下<，按h从大到小排；
- 这样就有点像DP：最长上升子序列问题了
-
初始化
dp[i] = 1
-
此时，对于第
i
个结点，前面的结点
j
的
h
都更大，那就判断下每个点是否是相邻点（前面定义的
check()
函数），若是，则执行
dp[i] = max(dp[i],dp[j]+1);
- 最后的ans是dp[i]数组的最大值
代码
#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;
}
问题 D: Homework
题目描述
临近开学了，大家都忙着收拾行李准 备返校，但 I_Love_C 却不为此担心! 因为他的心思全在暑假作业上：目前为止还未开动。
暑假作业是很多张试卷，我们这些从试卷里爬出来的人都知道，卷子上的题目有选择题、填空题、简答题、证明题等。而做选择题的好处就在于工作量很少，但又因为选择题题目都普遍很长。如果有 5 张试卷，其中 4 张是选择题，最后一张是填空题，很明显做最后一张所花的时间要比前 4 张长很多。但如果你只做了选择题，虽然工作量很少，但表面上看起来也已经做了4/5的作业了。
I_Love_C决定就用这样的方法来蒙混过关，他统计出了做完每一张试卷所需的时间以及它做完后能得到的价值（按上面的原理，选择题越多价值当然就越高咯）。
现在就请你帮他安排一下，用他仅剩的一点时间来做最有价值的作业。
输入
测试数据包括多组。每组测试数据以两个整数 M,N(1<M<20,1<N<10000) 开头，分别表示试卷的数目和 I_Love_C 剩下的时间。接下来有 M 行，每行包括两个整数 T,V(1<T<N,1<V<10000)分别表示做完这张试卷所需的时间以及做完后能得到的价值，输入以 0 0 结束。
输出
对应每组测试数据输出 I_Love_C 能获得的最大价值。保留小数点 2 位
提示：float 的精度可能不够，你应该使用 double 类型。
样例输入
4 20
4 10
5 22
10 3
1 2
0 0
样例输出
37.00
思路
代码
问题 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 3
2 4
1 4
1 2
1 2
1 3
1 4
样例输出
1
1
2
思路
输入结束后，把所有活动按结束时间从小到大排序。
定义
ans
，先给它赋值1。
循环遍历所有活动，符合不相交、不越界就可选。
-
千万别写if(e == c.e) return b < c.b;否则必定WA，不知为何。
-
千万要在结束时间超过r后跳出循环，不然必定TLE。
-
千万不要用cin、cout，不然好像也是必定TLE。
代码
#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
1 1 -2
样例输出
2
思路
此题类似于我前面写过的一篇文章《CUMTOJ算法实验二》，具体思路就是最大字段和的求解，详解见如下链接
https://blog.csdn.net/qq_41509200/article/details/101204716
代码
#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
6
8
9
10
12
14
15
16
18
20
21
思路
首先，用一个数组a存储输入的20个数字，然后，利用continue处理不能求余的数并将其输出即可。
代码
#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
2 3 3 4 5
1 2 3 4 5
4
2 2 1 2
2 2 3 1
0
样例输出
YES
NO
思路
首先，利用两个数组yuanZi和duiShou存储输入的n个数字，然后，利用排序函数sort()对两个函数进行排序，接着，不是最大的与最小的相比较，而是挑较大的与较小的比较，用一个win存储能赢的局数。
代码
#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
abbaaccbbd
2 5 8
样例输出
3 2 2
思路
首先，用一个数组S存储输入的长度为n的字符串，然后，利用LIS()函数求最长上升子序列，在我电脑上结果正确，但在OJ上就是运行错误50%，不管了，这一题就这样了。
代码
#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
5 3 4 9
样例输出
9
思路
本人不才，没找到最终答案，所以就给出求一个数组的第k小的代码。
代码
#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;
}