A: 递归求解
题目描述
请使用递归编写一个程序求如下表达式的计算结果：
S(1) = 1/2
S(2) = 1/2 + 1/6
S(3) = 1/2 + 1/6 + 1/12
S(4) = 1/2 + 1/6 + 1/12 + 1/20
......
S(n) = 1/2 + 1/6 + 1/12 + 1/20 + 1/30 + ......
输入n (1<n<=1000)，输出表达式S(n)的值（精确到小数点后六位）。
请编写一个递归程序实现该功能。输入
单组输入，输入一个正整数n，1<n<=1000。
输出
输出表达式S(n)的计算结果（精确到小数点后六位）。
样例输入 Copy
2样例输出 Copy
0.666667
思路：观察一下得知分母是项数*(项数+1)得来的
#include<stdio.h>
#define long long ll;
double fun(int n,int m,double s){
if(m>n){
return s;
}
else{
fun(n,m+1,s+1.0/(m*(m+1)));
}
}
int main(){
int n;
scanf("%d",&n);
printf("%lf\n",fun(n,2,0.5));
return 0;
}B: 挑选奖品
题目描述
X星人参加了一档幸运大抽奖节目，凭借无敌好运气中了一等奖。节目组给他准备了一个奖品箱，这个箱子中一共有M个格子，每个格子中只能放一个奖品。
现在一共有N个不同的奖品供X星人挑选，不同的奖品其价值不一定相等。
“贪心的”X星人希望所挑选的奖品的价值和最大，需要你编写一个程序帮他计算出所能得到的最大价值和。输入
单组输入。
第1行包含两个正整数M和N，分别表示奖品箱中格子的数量和奖品的总数。（1< M<=10^5且1<N<=10^5）
第2行包含N个正整数，分别表示N个奖品的价值，两两之间用空格隔开。输出
奖品箱中所有奖品的最大价值和。
样例输入 Copy
3 5 1 3 2 6 5样例输出 Copy
14
思路：因为挑选价值最大，所以我们从价值最大的开始选，总共选m个。因为数据范围是1e5，所以冒泡排序On2的做法会超时，我们采用快速排序，如果用c++的直接sort函数就行了，并且极限数据会爆int的数据范围，所以采用long long。
#include<stdio.h>
#define ll long long
int a[100005];
void quickSort(int l,int r){//是从大到小的快速排序
if(l>r){
return;
}
int tt=a[l];
int i=l;
int j=r;
int t;
while(i!=j){
while(i<j&&a[j]<=tt){
j--;
}
while(i<j&&a[i]>=tt){
i++;
}
if(i<j){
t=a[i];
a[i]=a[j];
a[j]=t;
}
}
a[l]=a[i];
a[i]=tt;
quickSort(l,i-1);
quickSort(i+1,r);
}
int main(){
int m,n;
scanf("%d%d",&m,&n);
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
}
quickSort(1,n);
ll s=0;
for(int i=1;i<=m;i++){
s+=a[i];
}
printf("%lld\n",s);
return 0;
}C: 排列蛋卷
题目描述
刚考完研的TC同学这段时间在家闲得慌，因此他决定学点新手艺。今天他学习的内容是：做蛋卷。
由于是第一次做蛋卷，TC同学做出来蛋卷长短不一。看着这些长度都不一样的蛋卷，TC同学的强迫症又犯了。他希望能够拿出其中部分蛋卷，使得留下来的蛋卷能够按照长度从大到小的次序排列。
请问他最少需要拿出多少根蛋卷？输入
单组输入，对于每一组测试数据，第1行N表示蛋卷的总数量（n<=1000)。
第2行包含N个正整数，分别表示每一根蛋卷的长度。（单位：厘米）
保证在同一组输入数据中每一根蛋卷的长度均不一样。输出
输出最少需要拿出的蛋卷数量。
样例输入 Copy
5 15 18 17 11 12样例输出 Copy
2
思路：看完题发现就是最长上升子序列改成了最长下降子序列，然后用n减去长度就行了，其实是一样的，数据范围也不大可以采用On2的做法
#include<stdio.h>
#define ll long long
int a[1005],dp[1005];
int max(int a,int b){
return a>b?a:b;
}
int main(){
int n;
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
}
int s=0;
for(int i=1;i<=n;i++){
dp[i]=1;
for(int j=0;j<i;j++){
if(a[i]<a[j]){
dp[i]=max(dp[i],dp[j]+1);
}
}
s=max(s,dp[i]);
}
printf("%d\n",n-s);
return 0;
}D: 最大收益
题目描述
小X是一位精明的投资人，他每次都能够做出正确的投资判断。
现在有N个项目，每个项目的总投资额和总收益已知，并且每一个项目都允许小X只投资一部分，当然也就只能拿到一部分收益。
现在小X决定拿出M万元钱来进行投资，请你帮他设计一个算法来计算最大收益和。输入
单组输入，对于每一组数据，第1行包含两个正整数，分别是M和N，其中M<=10^6，N<=100。
接下来N行每行均包含两个正数（不一定是正整数），第1数字表示第N个项目的总投资额（万元），第2个数字表示第N个项目的总收益（万元），两个数字之间用空格隔开。输出
小X可以获得的最大收益和（万元，结果四舍五入保留两位小数）。
样例输入 Copy
100 4 50 10 20 10 40 10 50 20样例输出 Copy
37.50
思路：首先计算每个项目单位投资的收益，然后按照单位收益从高到低排序，优先投资单位收益高的项目(使用结构体排序)，这样可以就最大化我们的总收益。
#include<stdio.h>
#define ll long long
typedef struct S{
double u,v,s;
}ss;
int main(){
int m,n;
ss a[1005],t;
scanf("%d%d",&m,&n);
for(int i=0;i<n;i++){
scanf("%lf%lf",&a[i].u,&a[i].v);
a[i].s=a[i].v/a[i].u;
}
for(int i=0;i<n-1;i++){
for(int j=0;j<n-i-1;j++){
if(a[j].s<a[j+1].s){
t=a[j];
a[j]=a[j+1];
a[j+1]=t;
}
}
}
double mm=0;
double sum=m;
for(int i=0;i<n&&sum>0;i++){
if(sum>=a[i].u){
mm+=a[i].v;
sum-=a[i].u;
}
else{
mm+=a[i].s*sum;
sum=0;
}
}
printf("%.2lf\n",mm);
return 0;
}E: 最小积分
题目描述
Kimi和Sunny决定在线组队玩一个数字游戏，该游戏的规则如下：
(1) 游戏系统随机生成两组正整数，每组N个数字，两组正整数可能不一样；
(2) 每个游戏团队两个人，每个人拿其中一组数字；
(3) 每一轮两个人从自己的那组数字中各取出一个数字，将两个数字相乘作为这一轮的积分，取出的数字不能再重复使用；
(4) 一共玩N轮，将每轮的积分求和，得到一个总积分；
(5) 总积分最小的队伍获胜。
现在需要你编写一个程序帮Kimi和Sunny计算出最小积分和。输入
单组输入。
第1行输入一个正整数N，N不超过100。
第2行输入N个不超过1000的正整数，表示Kimi拿到的数字，两两之间用空格隔开。
第3行输入N个不超过1000的正整数，表示Sunny拿到的数字，两两之间用空格隔开。输出
输出最小积分和。
样例输入 Copy
3 3 1 2 4 3 5样例输出 Copy
22
思路：这题就是一个贪心，我们使得最小积分和最小，那就让最大的去跟最小的乘以此类推。两个排序 一个从大到小 一个从小到大就解决了
数据范围不大，均可以采用冒泡排序
#include<stdio.h>
#define ll long long
int a[105],b[105];
int main(){
int n;
scanf("%d",&n);
for(int i=0;i<n;i++){
scanf("%d",&a[i]);
}
for(int i=0;i<n;i++){
scanf("%d",&b[i]);
}
for(int i=0;i<n-1;i++){
for(int j=0;j<n-i-1;j++){
if(a[j]>a[j+1]){
int t=a[j];
a[j]=a[j+1];
a[j+1]=t;
}
}
}
for(int i=0;i<n-1;i++){
for(int j=0;j<n-i-1;j++){
if(b[j]<b[j+1]){
int t=b[j];
b[j]=b[j+1];
b[j+1]=t;
}
}
}
int s=0;
for(int i=0;i<n;i++){
s+=a[i]*b[i];
}
printf("%d\n",s);
return 0;
}F: 数字迷宫
题目描述
X星有一个很神秘的数字迷宫。这个迷宫是一个由若干小方格区域组成的矩阵，一共包含M行和N列。每一个小方格中都有一个正整数，表示经过这个方格区域所需要的能量值。
现在小Z从最左边的列任选一个方格作为出发点，每一次只能向右边、右上或右下方向走一格，但不能走出数字迷宫，最终要到达最右边的列。
请你编写一个程序，输出消耗的总能量最少的那条路线所对应的总能量值（总能量值包含起点方格和终点方格所需能量值）。输入
单组输入。
第1行输入两个正整数M和N，分别表示数字迷宫的行和列，M和N均不超过1000，两者之间用一个英文空格隔开。
接下来M行，每行包含N个正整数，每个正整数对应经过一个小方格区域所需的能量值，每个能量值均不超过100。同一行的两个正整数之间用一个英文空格隔开。输出
输出一个正整数，表示总能量最少的那条路线所对应的总能量值。
样例输入 Copy
3 3 3 4 1 6 1 8 3 7 2样例输出 Copy
5
思路：这题是动态规划，用dp[i][j]表示到达当前位置前的最小能量，则得到dp[i][j]=a[i][j]+min(dp[i-1][j-1],dp[i][j-1],dp[i+1][j-1])，这个值的贡献就是a[i][j]+从三个方向来的最小值，特判一下第一列和最后一列只有两个方向来的。
#include<stdio.h>
#define ll long long
int a[1005][1005];
int dp[1005][1005];
int min(int a,int b,int c){
int t=a<b?a:b;
return t<c?t:c;
}
int mmin(int a,int b){
return a<b?a:b;
}
int main(){
int m,n;
scanf("%d%d",&m,&n);
for(int i=0;i<m;i++){
for(int j=0;j<n;j++){
scanf("%d",&a[i][j]);
}
}
for(int i=0;i<m;i++){
dp[i][0]=a[i][0];
}
for(int j=1;j<n;j++){
for(int i=0;i<m;i++){
if(i==0){
dp[i][j]=a[i][j]+mmin(dp[i][j-1],dp[i+1][j-1]);
}
else if(i==m-1){
dp[i][j]=a[i][j]+mmin(dp[i][j-1],dp[i-1][j-1]);
}
else{
dp[i][j]=a[i][j]+min(dp[i-1][j-1],dp[i][j-1],dp[i+1][j-1]);
}
}
}
int mm=dp[0][n-1];
for(int i=1;i<m;i++){
if(dp[i][n-1]<mm){
mm=dp[i][n-1];
}
}
printf("%d\n",mm);
return 0;
}又见小青蛙跳台阶(两种做法)
不管是什么做法都算是斐波那契递推式
题目描述
一个有N级台阶的楼梯，一只小青蛙的初始位置是第0级台阶，它一次可以跳1级台阶，也可以一次跳2级台阶。
现在已知这个楼梯中有两级是坏的，分别是第X级和第Y级，且1<X<Y<N。
请问小青蛙跳到第N级台阶一共有多少种跳法？输入
单组输入。
输入一行包含三个正整数X，Y和N，N<=20，1<X<Y<N，两两之间用英文空格隔开。输出
输出小青蛙跳到第N级台阶的跳法数。
样例输入 Copy
2 4 7样例输出 Copy
2
思路1： 这个递推遇到坏的就是0，直接continue就行了
#include<stdio.h>
#define ll long long
int a[30];
int main(){
int x,y,n;
scanf("%d%d%d",&x,&y,&n);
for(int i=1;i<=n;i++){
if(i==x||i==y){
continue;
}
else{
if(i==1){
a[1]=1;
continue;
}
if(i==2){
a[2]=2;
continue;
}
a[i]=a[i-1]+a[i-2];
}
}
printf("%d\n",a[n]);
return 0;
}思路2：利用组合数的知识，第一个坏台阶之前的跳法*中间台阶的跳法*第二个坏台阶之后的跳法
#include<stdio.h>
#define ll long long
int a[30];
int main(){
int x,y,n;
scanf("%d%d%d",&x,&y,&n);
if(x+1==y){
printf("0\n");
return 0;
}
a[1]=1,a[2]=1;
for(int i=3;i<=n;i++){
a[i]=a[i-1]+a[i-2];
}
printf("%d\n",a[x]*a[y-x-1]*a[n-y]);
return 0;
}H: X星礼物问题
题目描述
新的一年又到了，X星最大的企业XYZ公司决定给X星第一小学的小朋友们送一批礼物。
每个小朋友最多只能得到一件礼物（也有可能得不到）。每一件礼物都有一个“喜爱度”，“喜爱度”是一个1-100之间（包含1和100）的数字。
每位小朋友对于礼物的“喜爱度”都有一个预期值，当然有的小朋友预期值高，也有的小朋友预期值低。
XYZ公司希望能够尽量满足每个小朋友的“喜爱度”预期值，送给某位小朋友的礼物的“喜爱度”不能低于这位小朋友的“喜爱度”预期值。
现在一共有M件礼物要发给N个小朋友（N和M均不超过1000），告诉你这M件礼物的“喜爱度”以及N个小朋友的“喜爱度”预期值，请你编写一个程序，统计这M件礼物最多可以满足多少个小朋友的预期值，请输出最多可以满足的人数。输入
单组输入。
第1行输入两个正整数M和N，分别表示礼物的数量和小朋友的个数，N和M均不超过1000，二者用英文空格隔开。
第2行输入M个正整数，表示M件礼物的“喜爱度”值，每个正整数均不超过100，两两之间用英文空格隔开。
第3行输入N个正整数，表示N个小朋友的“喜爱度”预期值，每个正整数均不超过100，两两之间用英文空格隔开。输出
输出最多可以满足的小朋友的人数。
样例输入 Copy
3 3 4 1 8 5 2 6样例输出 Copy
2
思路：均先从小到大排序，数据不大，可以使用冒泡排序，然后对礼物的预期值与实际值进行匹配，不满足则预期值增大，直到最后一个礼物。
#include<stdio.h>
#define ll long long
int a[1005],b[1005];
int main(){
int m,n;
scanf("%d%d",&m,&n);
for(int i=0;i<m;i++){
scanf("%d",&a[i]);
}
for(int i=0;i<n;i++){
scanf("%d",&b[i]);
}
for(int i=0;i<m-1;i++){
for(int j=0;j<m-i-1;j++){
if(a[j]>a[j+1]){
int t=a[j];
a[j]=a[j+1];
a[j+1]=t;
}
}
}
for(int i=0;i<n-1;i++){
for(int j=0;j<n-i-1;j++){
if(b[j]>b[j+1]){
int t=b[j];
b[j]=b[j+1];
b[j+1]=t;
}
}
}
int s=0;
int j=0;
for(int i=0;i<n;i++){
while(j<m&&a[j]<b[i]){
j++;
}
if(j==m){
break;
}
s++;
j++;
}
printf("%d\n",s);
return 0;
}HNUCM的漂亮石头
题目描述
Kimi在HNUCM的美丽校园中散步，他发现在HNUCM的新月湖旁边有很多漂亮的小石头，他想捡一些小石头回去放到新买的花盆中。
他今天带了一个小塑料袋来装石头，但是该塑料袋能够装的石头的总重量不能超过某一个阈值，要不塑料袋肯定会坏掉，因此Kimi想选一些“高质量”的石头。
已知每一块小石头都有一个重量，Kimi还根据小石头的漂亮程度给每一块小石头打了一个分，我们就把这个打分叫做“漂亮度”吧。
Kimi希望塑料袋中的小石头的“漂亮度”之和达到最大值，现在需要请你编写一个程序帮Kimi计算出可以得到的“漂亮度”之和的最大值。输入
单组输入。
第1行输入一个正整数n，表示可供选择的小石头总数量。(1<=n<=1000)
第2行输入一个正整数m，表示小塑料袋可以承受的最大重量。(1<=m<=100)
接下来n行，每行输入两个正整数表示某一块小石头的重量和漂亮度，第1个正整数表示重量，第2个正整数表示漂亮度，两者之间用英文空格隔开。输出
输出小塑料袋中装入的石头的“漂亮度”之和的最大值。
样例输入 Copy
5 10 3 8 2 10 5 13 4 30 3 6样例输出 Copy
48
思路：01背包问题 emm就这样
#include<stdio.h>
#define ll long long
int a[1005][2];
int dp[105];
int max(int a,int b){
return a>b?a:b;
}
int main(){
int n,m;
scanf("%d%d",&n,&m);
for(int i=0;i<n;i++){
scanf("%d%d",&a[i][0],&a[i][1]);
}
for(int i=0;i<n;i++){
for(int j=m;j>=a[i][0];j--){
dp[j]=max(dp[j],dp[j-a[i][0]]+a[i][1]);
}
}
printf("%d\n",dp[m]);
return 0;
}HNUCM的批改作文
题目描述
HNUCM的小王老师给同学们布置了一道小作文题，要求所有同学同时提交并现场批改。
批改完的同学即可以下课，否则就需要等待老师把自己的作文批改完才能够下课。
交小作文的时间到了，N个同学同时把作文提交给了小王老师，小王老师根据大家写的字数估算了一下批改时间（单位：分钟），现在请你编写一个程序帮助小王老师做一个决策，使得所有同学等待作文批改的平均时间最少，请输出最少平均等待时间（单位：分钟）。输入
单组输入。
第1行输入一个不超过100的正整数N。
第2行输入N个不超过20的正整数，每一个正整数对应一个同学的作文批改时间（单位：分钟），两个正整数之间用英文空格分隔。输出
输出所有同学的作文都批改完时的最少平均等待时间（单位：分钟），结果四舍五入保留两位小数。
样例输入 Copy
3 10 5 20样例输出 Copy
18.33
思路：理解一下题目的意思，就是你前面一个人在等的时候，其实我们后面的人都在等，这个时间都是要算上的。数据不大冒泡排序
#include<stdio.h>
#define ll long long
int a[105];
int main(){
int n;
scanf("%d",&n);
double f=0,s=0;
for(int i=0;i<n;i++){
scanf("%d",&a[i]);
}
for(int i=0;i<n-1;i++){
for(int j=0;j<n-i-1;j++){
if(a[j]>a[j+1]){
int t=a[j];
a[j]=a[j+1];
a[j+1]=t;
}
}
}
for(int i=0;i<n;i++){
s+=a[i];
f+=s;
}
printf("%.2lf",35.0/3);
return 0;
}
