XP03B班-04【补题】

userId_undefined
.҈̊̔柠.҈̊̔̇̊͐七
出道萌新时空双修者快乐小狗倔强青铜

2026-08-15 20:43:20

发布于：浙江

13阅读
0回复
0点赞

@随机【童靴】 @得去搞点吃的
@༺ཌༀ夕阳の刻痕.皮皮虾ༀད༻
@编程爱好者

一张笑脸
时间限制：1000ms
内存限制：128MB

微笑具有一些特殊的能力。比如说：爱笑的女孩运气不会太差。又比如说：张口莫骂赔礼者，伸手不打笑脸人。总之，学习弥勒：开口便笑，笑古笑今，凡事付之一笑。

输入格式
无。

输出格式
输出下面的笑脸。
^_^

样例组
输入#1

输出#1

^_^

答：
输出:

^_^

代码：

#include<bits/stdc++.h>
using namespace std;

int main(){
	cout<<"^_^"; 
	return 0;
}

面积比较
时间限制：1000ms
内存限制：128MB

小码君有一个边长为 a 的正方形，小码酱有一个长宽分别为 b,c 的矩形，请你告诉小码君正方形面积是否更大。

输入格式
仅一行三个正整数 a,b,c

输出格式
输出仅一行一个字符串，若正方形面积更大则输出 YES，否则输出 NO。

样例组
输入#1
复制
5 4 6
输出#1
复制
YES
输入#2
复制
7 5 10
输出#2
复制
NO
提示说明
【数据范围】
对于 100% 的数据，1≤a,b,c≤10910^9

【样例 1 解释】
正方形面积为 25，矩形面积为 24。

【样例 2 解释】
正方形面积为 49，矩形面积为 50。

答：

比较aa与bc的大小

代码

#include<bits/stdc++.h>
using namespace std;

int main(){
	long long a,b,c;
	cin>>a>>b>>c;
	if(a*a>b*c) cout<<"YES";
	else cout<<"NO";
	return 0;
}

卷王爬楼梯
时间限制：1000ms
内存限制：128MB

有 N 级的台阶，你一开始在底部，每次可以向上迈最多3级台阶（最少1级），问到达第 N 级台阶有多少种不同方式。

输入格式
输入一个整数 n（0<n≤30）。

输出格式
输出上到第 n 级台阶一共有多少种方法。

样例组
输入#1
复制
3
输出#1
复制
4
提示说明
样例一解释：

上到 3 级台阶总共有 4 种方案。

答：

前缀和不必多说

代码

#include<bits/stdc++.h>
using namespace std;
long long dp[110];
int n;
int main(){
	cin>>n;
	dp[1]=1;
	dp[2]=2;
	dp[3]=4;
	for(int i=4;i<=n;i++){
		dp[i]=dp[i-1]+dp[i-2]+dp[i-3];
	}
	cout<<dp[n];
	return 0;
}

石子合并（考试版）
时间限制：1000ms
内存限制：128MB

有 N 堆石子排成一排，编号为 1,2,3,…,N。

第 i 堆石子的质量为 m
i
​
。

每次操作只能选择相邻的两堆石子进行合并。

如果这两堆石子的质量分别为 x 和 y，那么这次合并的代价为：x+y

合并之后，这两堆石子会变成一堆新的石子，新石子的质量也是：x+y

新石子会继续和左右相邻的石子相邻。

要求把所有石子最终合并成一堆，并使总代价最小，输出这个最小总代价。

输入格式
第一行一个整数 N，表示石子堆数。

第二行 N 个整数：

m1m_1,m2m_2,m3m_3,……，mnm_n

表示每堆石子的质量。

输出格式
输出一行一个整数，表示最小合并总代价。

样例组
输入#1
复制
4
2 5 3 1
输出#1
复制
22
提示说明
样例解释
一种最优合并方案如下：

先合并第 1 堆和第 2 堆：2+5=7

代价为 7，序列变成：7,3,1

再合并第 2 堆和第 3 堆：3+1=4

代价为 4，序列变成：7,4

最后合并剩下的两堆：7+4=11

总代价为：7+4+11=22

所以答案为 22。

数据范围

测试点编号 N mim _i
1∼10 1≤N≤300 1≤mim_i ≤1000

答：

石子合并问题

代码：

#include<bits/stdc++.h>
using namespace std;
int dp[310][310],n,a[310],s[310];

int main(){
	cin>>n;
	for (int i=1;i<=n;i++){
		cin>>a[i];
		s[i]=s[i-1]+a[i];	
	}
	for(int L=2;L<=n;L++){
		for(int j=L,i=1;j<=n;j++,i++){
			dp[i][j]=1e9;
			for(int k=i;k<=j;k++){
				dp[i][j]=min(dp[i][j],(dp[i][k]+dp[k+1][j]+s[j]-s[i-1]));
			}
		}
	}
	cout<<dp[1][n];
	return 0;
}

鱼和熊掌
时间限制：1000ms
内存限制：128MB

有 n 个人得到了鱼，m 个人得到了熊掌，都说鱼和熊掌不能兼得，现在我们要看一看，哪些人同时得到了鱼和熊掌。

输入格式
第一行两个整数 n，m。

第二行 n 个整数，表示得到鱼的人的编号。

第三行 m 个整数，表示得到熊掌的人的编号。

输出格式
输出一行，表示同时得到鱼和熊掌的人的编号，按获得鱼的人名单顺序输出。

样例组
输入#1
4 3
2 15 6 8
8 9 2
输出#1
2 8
提示说明
对于 30% 的数据，0<n,m≤1000

对于100% 的数据，0<n,m≤10510^5

思路

二分搜索

TLE代码

#include<bits/stdc++.h>
using namespace std;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
	long long n,m;
	long long a[100010],b[100010],c[100010];
	cin>>n>>m;
	for(int i=1;i<=n;i++) cin>>a[i];
	for(int i=1;i<=m;i++) cin>>b[i];
    int k=0;
    for(int i=n;i>=1;i--){
        for(int j=1;j<=m;j++){
            if(b[j]==a[i]){
                c[++k]=a[i];
                break;
            }
        }
    }
    for(int i=k;i>=1;i--){
        cout<<c[i]<<" ";
    }
	return 0;
}

二分

#include<bits/stdc++.h>
using namespace std;

int main(){
	int n,m;
    cin>>n>>m;
	int a[100010],b[100010];
	for(int i=1;i<=n;i++) cin>>a[i];
	for(int i=1;i<=m;i++) cin>>b[i];
	sort(b+1,b+m+1);
	for(int i=1;i<=n;i++){
		int p=lower_bound(b+1,b+m+1,a[i])-b;
		if(b[p]==a[i]){
			cout<<a[i]<<" ";
		}
	}
	return 0;
}

草药采集大师
时间限制：1000ms
内存限制：128MB

覅覅是个天资聪颖的孩子，他的梦想是成为世界上最伟大的医师。为了考验他的资质，医师带他来到一个神秘的山洞，里面生长着各种珍稀草药。

山洞里有 M 株不同的草药，每株草药需要 tit_i
​
时间采集，并且具有viv_i
​
的价值，每株草药最多只能采集一次。覅覅总共有 T 单位的时间可以用来采药。

请你帮助覅覅设计一个采集方案，使得在限定时间内采集的草药总价值最大。

输入格式
第一行包含两个整数 T 和 M，分别表示总可用时间和草药数量。
接下来 M 行，每行两个整数tit_i 和 viv_i，表示采集第 i 株草药所需时间和其价值。
输出格式
输出一个整数，表示在规定时间内可以采集的草药的最大总价值。
样例组
输入#1
70 3
71 100
69 1
1 2

输出#1
3

提示说明
【样例 1 解释】
最佳方案是采集第 2 株和第 3 株草药：
总时间：69+1=70
总价值：1+2=3
数据范围

测试点 T 范围 M 范围 tit_i范围 viv_i范围
1−3 1≤T≤100 M=3 1≤tit_i≤100 1≤viv_i≤100
4−5 1≤T≤100 1≤M≤100 1≤tit_i≤100 viv_i=1
6−10 1≤T≤1000 1≤M≤1000 1≤tit_i≤1000 1≤viv_i≤1000

答

纯背包

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=30010;
ll dp[N];
int n,m;

int main(){
	cin>>m>>n;
	for(int i=1;i<=n;i++){
		int t,v;
		cin>>t>>v;
		for(int j=m;j>=t;j--){
			dp[j]=max(dp[j],dp[j-t]+v);
		}
	}
	cout<<dp[m];
	return 0;
}

装箱问题
时间限制：1000ms
内存限制：128MB

有一个箱子容量为 V，同时有 n 个物品，每个物品有一个体积。

现在从 n 个物品中，任取若干个装入箱内（也可以不取），使箱子的剩余空间最小。输出这个最小值。

输入格式
第一行共一个整数 V，表示箱子容量。

第二行共一个整数 n，表示物品总数。

接下来 n 行，每行有一个正整数，表示第 i 个物品的体积。

输出格式
共一行一个整数，表示箱子最小剩余空间。

样例组
输入#1
24
6
8
3
12
7
9
7
输出#1
0
提示说明
对于 100% 数据，满足 0<n≤30，1≤V≤20000。

答

#include<bits/stdc++.h>
using namespace std;
int m,n;
int dp[20010];
int w[40];
int main(){
	cin>>m>>n;
    for(int i=1;i<=n;i++) cin>>w[i]; 
    for(int i=1;i<=n;i++){
        for(int j=m;j>=w[i];j--){
            if(dp[j]<dp[j-w[i]]+w[i]){
                dp[j]=dp[j-w[i]]+w[i];
            }
        }
    }
    cout<<m-dp[m];
}

小码君买饮料
时间限制：1000ms
内存限制：128MB

小码君准备参加一次长途徒步活动。出发前，他来到商店购买饮料作为补给。

商店里一共有 N 种饮料，编号为 0 到 N−1。

其中编号为 i 的饮料价格为cic_i元，容量为 lil_i毫升。

由于小码君想多尝试不同种类的饮料，所以每种饮料最多只能购买 1 瓶。

同时，为了保证路上有足够的补给，小码君希望购买的饮料总容量不少于 L 毫升。

在满足容量要求的前提下，小码君希望总花费尽可能少。

请你帮小码君计算，至少需要花多少钱。

如果无论如何都无法买到总容量不少于 L 毫升的饮料，输出 no solution。

输入格式
第一行两个整数 N,L。

接下来 N 行，依次描述编号为 0,1,…,N−1 的饮料。

每行两个整数 cic_i,lil_i，表示第 i 种饮料的价格和容量。

输出格式
输出一行。

如果可以满足要求，输出一个整数，表示最少花费。

如果不能满足要求，输出：no solution

样例组
输入#1

5 100
100 200
2 50
4 40
5 30
3 20
输出#1

9

输入#2

5 141
100 200
2 50
4 40
5 30
3 20

输出#2

100

输入#3

4 141
2 50
4 40
5 30
3 20
输出#3

no solution

提示说明
样例解释 #1
可以购买第 1,2,4 种饮料。

它们的总容量为：50+40+20=110

总花费为：2+4+3=9

虽然也可以购买第 1,3,4 种饮料，总容量为：50+30+20=100

但是花费为：2+5+3=10 不是最优。

所以答案为 9。

样例解释 #2
如果只购买后四种饮料，总容量为：

50+40+30+20=140

仍然小于 141，不能满足要求。

因此只能购买第 0 种饮料，它的容量为 200，花费为 100。

所以答案为 100。

样例解释 #3
所有饮料全部购买，总容量为：

50+40+30+20=140

仍然小于 141。

所以无法满足要求，输出 no solution。

数据范围与子任务表

子任务 测试点 分值 限制 / 特殊性质
1 1∼8 40 N≤20, 1≤L≤100, lil_i≤100
2 9∼14 30 lil_i≤100
3 15∼20 30 无特殊限制
对于所有数据，保证：

1≤N≤500

1≤L≤2000

1≤cic_i,lil_i ≤10610^6

代码：

#include<bits/stdc++.h>
using namespace std;
long long n,l,c[1000010],r[1000010],dp[1000010];
int main() {
	cin>>n>>l;
	for(int i=1; i<=n; i++) {
		cin>>c[i]>>r[i];
	}
	for(int i=0; i<=l; i++)dp[i]=1e18;
	dp[0]=0;
	for(int i=1; i<=n; i++) {
		for(int j=l; j>=1; j--) {
			dp[j]=min(dp[j],dp[max(j-r[i],1LL*0)]+c[i]) ;
		}
	}
	cout<<dp[l];
	return 0;
}

248 游戏
时间限制：1000ms
内存限制：128MB

贝西在手机上玩一个数字合并游戏。

游戏开始时，给定一个长度为 N 的整数序列 a1a_1,a2a_2,a3a_3,……,ana_n
其中每个数都在 1∼40 之间。

在一次操作中，贝西可以选择两个相邻且相等的数，将它们合并成一个新的数。

如果选择的两个数都是 x，那么合并后得到的新数为：x+1

例如：7,7 可以合并成：8

每次合并后，序列长度会减少 1，剩余数字的相对顺序保持不变。

贝西希望通过若干次合并，使最终序列中出现的最大数字尽可能大。

请你求出她最多能够得到多大的数字。

输入格式
第一行一个整数 N，表示序列长度。

接下来 N 行，每行一个整数，表示序列中的一个数。

输出格式
输出一行一个整数，表示通过若干次合并后，最终能够得到的最大数字。

样例组
输入#1
4
1
1
1
2
输出#1
3
提示说明
样例解释
初始序列为：1,1,1,2

一种做法是先合并前两个 1：1,1,1,2→2,1,2

此时两个 2 不相邻，无法继续合并，最大值只能得到 2。

更优的做法是：

先合并第 2 个和第 3 个 1：1,1,1,2→1,2,2

再合并两个相邻的 2：1,2,2→1,3

最终可以得到最大数字 3。

所以答案为 3。

数据范围与子任务表
对于所有数据，保证：

2≤N≤248

1≤aia_i≤40

子任务 测试点 分值 限制 / 特殊性质
1 1∼5 20 N≤12
2 6∼10 20 任意相邻两数不同
3 11∼15 20 所有 $a_i 相同
4 16∼20 20 N≤120
5 21∼25 20 无特殊限制

共 25 个测试点，每个测试点 4 分。

代码

#include <bits/stdc++.h>
using namespace std;
int n, a[250];
int dp[250][250];

int main() {
	cin >> n;
	int maxn = 0;
	for(int i = 1; i <= n; i++) {
		cin >> a[i];
		dp[i][i] = a[i];
		maxn = max(maxn, dp[i][i]);
	}
	for(int len = 2; len <= n; len++) {
		for(int i = 1; i + len - 1 <= n; i++) {
			int j = i + len - 1;
			for(int k = i; k < j; k++) {
				if(dp[i][k] && dp[k+1][j] && dp[i][k] == dp[k+1][j]) {
					dp[i][j] = max(dp[i][j], dp[i][k] + 1);
					maxn = max(maxn, dp[i][j]);
				}
			}
		}
	}
	cout << maxn;
	return 0;
}
userId_undefined
去预览
0/2000

全部评论 1

热门讨论