算法作业二。
问题 A: 单词排序
题目描述
小红学会了很多英文单词，妈妈为了帮小红加强记忆，拿出纸、笔，把 N 个单词写在纸上的一行里，小红看了几秒钟后，将这张纸扣在桌子上。妈妈问小红：“你能否将这 N 个单词按照字典排列的顺序，从小到大写出来？”小红按照妈妈的要求写出了答案。现在请你编写程序帮助妈妈检查小红的答案是否正确。注意：所有单词都由小写字母组成，单词两两之间用一个空格分隔。
输入
输入包含两行。
第一行仅包括一个正整数N(0<N≤26)。
第二行包含N个单词，表示妈妈写出的单词，两两之间用一个空格分隔。
单个单词长度不超过1010。
输出
输出仅有一行。针对妈妈写出的单词，按照字典排列的顺序从小到大排列成一行的结果，每个单词后带一个空格。
样例输入
4
city boy tree student
样例输出
boy city student tree
提示
代码
#include<bits/stdc++.h>
using namespace std;
int main()
{
string s[30];
int n;
cin>>n;
for(int i=0;i<n;i++)
{
cin>>s[i];
}
sort(s,s+n);
for(int i=0;i<n;i++)
{
if(i==0)
cout<<s[i];
else
cout<<" "<<s[i];
}
cout<<endl;
return 0;
}
问题 B: 求数组的最长递减子序列
题目描述
给定一个整数序列，输出它的最长递减（注意不是“不递增”）子序列。
输入
输入包括两行，第一行包括一个正整数N（N<=1000），表示输入的整数序列的长度。第二行包括用空格分隔开的N个整数，整数范围区间为[-30000,30000]。
输出
输出最长递减子序列，数字之间有一个空格。
样例输入
8
9 4 3 2 5 4 3 2
样例输出
9 5 4 3 2
提示
代码
#include<bits/stdc++.h>
using namespace std;
int main()
{
int n;
int a[1010],b[1010],p[1010];
cin>>n;
for(int i=0;i<n;i++)
{
cin>>a[i];
}
memset(b,1,sizeof(b));
memset(p,-1,sizeof(p));
for(int i=1;i<n;i++)
{
for(int j=0;j<i;j++)
{
if(a[i]<a[j]&&(b[j]+1)>b[i])
{
b[i]=b[j]+1;
p[i]=j;
}
}
}
int maxn=0,num=0;
for(int i=0;i<n;i++)
{
if(b[i]>maxn)
{
maxn=b[i];
num=i;
}
}
stack <int>stk;
stk.push(a[num]);
while(p[num]!=-1)
{
stk.push(a[p[num]]);
num=p[num];
}
while(!stk.empty())
{
cout<<stk.top()<<" ";
stk.pop();
}
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
提示
代码
#include<bits/stdc++.h>
using namespace std;
int m,n;
int dp[40400];
struct node
{
int h,x,y;
}ai[40040];
bool compare(node a,node b)
{
return a.h<b.h;
}
bool check(node a,node b)
{
if(((a.x==b.x&&abs(a.y-b.y)==1)||(a.y==b.y&&abs(a.x-b.x)==1))&&b.h>a.h)
return true;
return false;
}
int main()
{
int num=0;
cin>>m>>n;
for(int i=1;i<=m;i++)
{
for(int j=1;j<=n;j++)
{
cin>>ai[num].h;
ai[num].x=i;
ai[num].y=j;
num++;
}
}
sort(ai,ai+m*n,compare);
int mmax=1;
for(int i=0;i<num;i++)
{
dp[i]=1;
for(int j=0;j<i;j++)
{
if(check(ai[j],ai[i]))
{
dp[i]=max(dp[i],dp[j]+1);
}
}
if(dp[i]>mmax) mmax=dp[i];
}
cout<<mmax<<endl;
return 0;
}
问题 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
提示
代码
#include<bits/stdc++.h>
using namespace std;
int main()
{
int m,n;
int a[20],b[20];
double ma[20];
while(cin>>m>>n&&m!=0&&n!=0)
{
double maxn=0;
for(int i=0;i<m;i++)
{
cin>>a[i];
cin>>b[i];
ma[i]=double(b[i])/a[i];
}
int f=0;
int s;
double vm;
while(1)
{
if(f==m)
break;
vm=0;
for(int i=0;i<m;i++)
{
if(ma[i]>vm)
{
vm=ma[i];
s=i;
}
}
if(n<a[s])
{
maxn=maxn+n*ma[s];
break;
}
else
{
maxn=maxn+b[s];
n=n-a[s];
ma[s]=0;
f++;
}
}
cout<<setprecision(2)<<std::fixed<<maxn<<endl;
}
}
问题 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
提示
代码
#include<iostream>
#include<algorithm>
#define inf 0x7fffffff
using namespace std;
typedef struct node
{
int l;
int r;
}node;
bool cmp(node a, node b)
{
return a.r < b.r;
}
int main()
{
std::ios::sync_with_stdio(false);
int n, m;
while (cin >> n >> m)
{
node *nnum = new node[n];
node *mnum = new node[m];
for (int i = 0; i < n; i++)
{
cin >> nnum[i].l >> nnum[i].r;
}
for (int i = 0; i < m; i++)
{
cin >> mnum[i].l >> mnum[i].r;
}
sort(nnum, nnum + n, cmp);
for (int i = 0; i < m; i++)
{
int res = 0;
int k = mnum[i].l; //K初始的时候等于m数组的左边界
for (int j = 0; j < n; j++)
{
if ((nnum[j].l >= k))
{
if (nnum[j].r <= mnum[i].r)
{
res++;
k = nnum[j].r; //每次更新成n数组的右边界
}
else //右边界一旦超过，直接扔掉后面的部分结束质询
{
break;
}
}
}
cout << res << endl;
}
delete[] nnum;
delete[] mnum;
}
}
问题 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
提示
代码
#include<bits/stdc++.h>
using namespace std;
int main()
{
int n;
int a[1010],b[1010];
cin>>n;
for(int i=0;i<n;i++)
{
cin>>a[i];
}
memset(b,0,sizeof(b));
b[0]=a[0];
int sum=0;
for(int i=1;i<n;i++)
{
b[i]=max(b[i-1]+a[i],a[i]);
}
for(int i=0;i<n;i++)
{
if(b[i]>sum)
{
sum=b[i];
}
}
cout<<sum<<endl;
}
问题 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
提示
代码
#include<bits/stdc++.h>
using namespace std;
int main()
{
int a[20],b[20];
for(int i=0;i<20;i++)
{
cin>>a[i];
b[i]=a[i];
}
sort(b,b+20);
for(int i=0;i<20;i++)
{
//cout<<b[i]<" ";
int sign=0;
for(int j=0;j<20;j++)
{
if(b[j]<a[i])
{
if(a[i]%b[j]==0)
sign=1;
}
else
break;
}
if(sign==1)
cout<<a[i]<<endl;
}
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
提示
代码
#include<bits/stdc++.h>
using namespace std;
int main()
{
int n;
while(cin>>n&&n!=0)
{
int a[n],b[n];
for(int i=0;i<n;i++)
{
cin>>a[i];
}
for(int i=0;i<n;i++)
{
cin>>b[i];
}
sort(a,a+n);
sort(b,b+n);
int sum=0;
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
{
if(b[i]<a[j])
{
sum++;
a[j]=0;
break;
}
}
}
if(sum>=n/2+1)
{
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
提示
代码
#include<bits/stdc++.h>
#define max(a,b) ((a)>(b)?(a):(b))
using namespace std;
int n,q;
char a[100010];
int ans[100010],p[30];
int main()
{
cin>>n>>q;
cin>>a;
for(int i=n-1;i>=0;i--)
{
ans[i]=1;
for(int j=a[i]-'a'+1;j<26;j++)
ans[i]=max(ans[i],p[j]+1);
p[a[i]-'a']=ans[i];
}
int x;
while(q--)
{
cin>>x;
cout<<ans[x]<<" ";
}
}
问题 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
提示
二分
代码
#include<bits/stdc++.h>
using namespace std;
const int N = 100005;
int a[N];
int n, k;
long long max_position(int x)
{
long long result = 0;
int l = 0, r = -1, num = 0;
while (r < n)
{
if (num < k)
{
if (a[r + 1] <= x)num++;
r++;
}
else
{
result += n - r;
if (a[l] <= x)num--;
l++;
}
}
return result;
}
int main()
{
cin >> n >> k;
int*b=new int[n];
for (int i = 0; i < n; i++)
{
cin >> a[i];
b[i] = a[i];
}
sort(b, b + n);
int len = unique(b, b + n) - b;
int l = 0, r = len - 1;
int ans = 0;
while (l <= r)
{
int mid = (l + r) / 2;
long long ret = max_position(b[mid]);
if (ret >= k)
{
ans = b[mid];
r = mid - 1;
}
else l = mid + 1;
}
cout << ans;
return 0;
}
