GESP-C++五级 题库
武器强化
时间限制:1.0 s
内存限制:512.0 MB
题面描述
小杨有 n 种武器和 m 种强化材料。第 i 种强化材料会适配第 pi 种武器,小杨可以花费 ci 金币将该材料对应的适配武器修改为任意武器。
小杨最喜欢第 1 种武器,因此他希望适配该武器的强化材料种类数严格大于其他的武器,请你帮小杨计算为了满足该条件最少需要花费多少金币。
输入格式
第一行包含两个正整数 n,m,含义如题面所示。
之后 m 行,每行包含两个正整数 pi,ci,代表第 i 种强化材料的适配武器和修改花费。
输出格式
输出一个整数,代表能够使适配第 1 种武器的强化材料种类数严格大于其他的武器最少需要花费的金币。
输入样例
4 4
1 1
2 1
3 1
3 2
输出样例
1
样例解释
花费 1,将第三种强化材料的适配武器由 3 改为 1。此时,武器 1 有 2 种强化材料适配,武器 2 和武器 3 都各有 1 种强化材料适配。满足适配第 1 种武器的强化材料种类数严格大于其他的武器。

对于全部数据,保证有 1≤n,m≤1000,1≤pi≤n,1≤ci≤109。
#include<bits/stdc++.h>
using namespace std;
#define ll long long
int n, m;
int cnt[1010];
vector<int> cs[1010];
ll calc(int aim) {
int cur_cnt = cnt[1];
ll res = 0;
vector<int> tmp;
for (int i = 2; i<=n; i++) {
int buy = max((int)cs[i].size() - aim + 1, 0);
for (int j = 0; j < buy; ++j) {
res += (ll)cs[i][j];
}
cur_cnt += buy;
for (int j = buy; j < cs[i].size(); ++j) {
tmp.push_back(cs[i][j]);
}
}
sort(tmp.begin(), tmp.end());
for (int i = 0; i < aim - cur_cnt; i++) {
res += (ll)tmp[i];
}
return res;
}
signed main() {
// freopen("06.in", "r", stdin);
cin >> n >> m;
for (int i = 1; i <=m; i++) {
int p, c;
cin >> p >> c;
cnt[p]++;
cs[p].push_back(c);
}
for (int i = 1; i <=n; i++) {
sort(cs[i].begin(), cs[i].end());
}
ll ans = 1e18;
for (int i = max(cnt[1], 1); i <= m; ++i) {
ans = min(ans, calc(i));
}
cout << ans << "\n";
}小杨的武器
时间限制:1.0 s
内存限制:512.0 MB
题面描述
小杨有 n 种不同的武器,他对第 i ii 种武器的初始熟练度为ci。
小杨会依次参加 m 场战斗,每场战斗小杨只能且必须选择一种武器使用,假设小杨使用了第 i 种武器参加了第 j 场战斗,战斗前该武器的熟练度为ci′,则战斗后小杨对该武器的熟练度会变为 ci′+aj。需要注意的是,aj可能是正数,0 或负数,这意味着小杨参加战斗后对武器的熟练度可能会提高,也可能会不变,还有可能降低。
小杨想请你编写程序帮他计算出如何选择武器才能使得 m 场战斗后,自己对 n 种武器的熟练度的最大值尽可能大。
输入格式
第一行包含两个正整数 n,m,含义如题面所示。
第二行包含 n 个正整数 c1,c2,...,cn,代表小杨对武器的初始熟练度。
第三行包含 m 个正整数 a1,a2,...,am,代表每场战斗后武器熟练度的变化值。
输出格式
输出一个整数,代表 m 场战斗后小杨对 n 种武器的熟练度的最大值最大是多少。
输入样例
输出样例
一种最优的选择方案为,第一场战斗小杨选择第一种武器,第二场战斗小杨选择第二种武器。

对于全部数据,保证有 1≤n,m≤105,−104≤ci,ai≤104。
#include <bits/stdc++.h>
using namespace std;
const int N = 100010;
int a[N], c[N];
int main(){
int n, m;
cin>>n>>m;
int mx = -10000;
for (int i = 1; i <= n; ++ i){
cin>>c[i];
mx = max(mx,c[i]);
}
for (int i = 1; i <= m; ++ i){
cin>>a[i];
}
for (int i = 1; i <= m; ++ i){
if (n == 1 || a[i] > 0){
mx += a[i];
}
}
cout<<mx<<"\n";
return 0;
}黑白格
时间限制:1.0 s
内存限制:512.0 MB
题面描述
小杨有一个n行m列的网格图,其中每个格子要么是白色,要么是黑色。
小杨想知道至少包含k个黑色格子的最小子矩形包含了多少个格子。
输入格式
第一行包含三个正整数n,m,k,含义如题面所示。
之后n行,每行一个长度为m的01串,代表网格图第i行格子的颜色,如果为0,则对应格子为白色,否则为黑色。
输出格式
输出一个整数,代表至少包含k个黑色格子的最小子矩形包含格子的数量,如果不存在则输出0。
输入样例
输出样例
样例解释
对于样例1,假设(i,j) 代表第i 行第j列,至少包含5个黑色格子的最小子矩形的四个顶点为(2,4),(2,5),(4,4),(4,5),共包含6个格子。
数据范围

对于全部数据,保证有1≤n,m≤100,1≤k≤n×m。
#include<bits/stdc++.h>
using namespace std;
const int N = 110;
int w[N][N];
int sum[N][N];
int n,m;
int main(){
int k;
cin>>n>>m>>k;
for(int i=1;i<=n;i++){
string s;
cin>>s;
for(int j=1;j<=m;j++){
w[i][j]=s[j-1]-'0';
sum[i][j]=sum[i][j-1]+w[i][j];
}
}
int ans = 0;
for(int i=1;i<=m;i++){
for(int j=i;j<=m;j++){
vector<int> num;
int now = 0;
for(int l=1;l<=n;l++){
int tmp = sum[l][j]-sum[l][i-1];
now+=tmp;
num.push_back(now);
if(now>=k){
if(ans ==0)ans=(j-i+1)*l;
else ans=min(ans,(j-i+1)*l);
int L=1,R=l;
while (L < R){
int mid = L + R + 1 >> 1;
if (now-num[mid-1]>=k) L = mid;
else R = mid - 1;
}
if(now-num[L-1]>=k){
if(ans ==0)ans=(j-i+1)*(l-L);
else ans=min(ans,(j-i+1)*(l-L));
}
}
}
}
}
cout<<ans<<"\n";
}1.二维数组存储对应格子颜色的值
2.使用前缀和的技巧来快速计算任意子矩形内的格子数量。这样一来,不需要重复遍历每个可能的子矩形来计算其中的黑色格子数,从而节省时间
3.通过检查每个可能的子矩形,计算其中的黑色格子数量。找到一个最小的子矩形,使得其中至少有 k 个黑色格子。
4.使用二分查找的技巧,在内部循环中快速定位满足条件的子矩形大小
5.最后,我们输出这个最小子矩形的面积。如果不存在满足条件的子矩形,则输出0
小杨的幸运数字
时间限制:1.0 s
内存限制:512.0 MB
题面描述
小杨认为他的幸运数字应该恰好有两种不同的质因子,例如,12=2×2×3 的质因子有2,3,恰好为两种不同的质因子,因此12是幸运数字,而30=2×3×5 的质因子有2,3,5,不符合要求,不为幸运数字。
小杨现在有n个正整数,他想知道每个正整数是否是他的幸运数字。
输入格式
第一行包含一个正整数n,代表正整数个数。
之后n行,每行一个正整数。
输出格式
输出n行,对于每个正整数,如果是幸运数字,输出1,否则输出0。
输入样例
输出样例
样例解释
7的质因子有7,只有一种。
12的质因子有2,3,恰好有两种。
30的质因子有2,3,5,有三种。
数据范围

对于全部数据,保证有1≤n≤104,每个正整数ai满足2≤ai≤106。
#include<bits/stdc++.h>
using namespace std;
map<int,int> mp;
const int N = 1e5+10;
int calc(int x) {
int res = 0;
set<int> s;
for (int i = 2; i * i <= x; i++) {
if (x % i == 0) {
s.insert(i);
while (x% i == 0){
x/= i;
}
}
}
if (x != 1) {
s.insert(x);
}
return (int)s.size();
}
int a[N];
int main(){
int n;
cin>>n;
long long ans = 0;
int pre = 0;
for(int i=1;i<=n;i++){
cin>>a[i];
int x = calc(a[i]);
if(x==2)cout<<"1\n";
else cout<<"0\n";
}
}1.计算输入数据的质因子的个数。具体实现中,可以从最小的质数开始试除,统计不重复的质因子个数。
2.当质因子个数为2时,返回1表示是幸运数字,否则返回0。
成绩排序
问题描述
有N名同学,每名同学有语文、数学、英语三科成绩。你需要按如下规则对所有同学的成绩从高到低排序:
1. 比较总分,高者靠前;
2. 如果总分相同,则比较语文和数学两科总分,高者靠前;
3. 如果仍相同,则比较语文和数学两科的最高分,高者靠前;
4. 如果仍相同,则二人并列。
你需要输出每位同学的排名,如遇x人并列,则他们排名相同,并留空后面的x-1个名次。例如,有3名同学并列第1,则后一名同学自动成为第4名。
输入描述
第一行一个整数N,表示同学的人数。
接下来N行,每行三个非负整数ci,mi,ei分别表示该名同学的语文、数学、英语成绩。
保证0≤ci,mi,ei≤150。
输出描述
输出N行,按输入同学的顺序,输出他们的排名。
注意:请不要按排名输出同学的序号,而是按同学的顺序输出他们各自的排名
特别提醒
在常规程序中,输入、输出时提供提示是好习惯。但在本场考试中,由于系统限定,请不要在输入、输出中附带任
何提示信息。
样例输入 1
样例输出 1
数据规模
对于30的测试点,保证N≤100,且所有同学的总分各不相同。
对于所有测试点,保证2≤N≤104。
#include <iostream>
#include <algorithm>
#include <tuple>
using namespace std;
const int MAX_N = 10005;
tuple<int, int, int, int> students[MAX_N];
int main() {
ios::sync_with_stdio(false);
int N;
cin >> N;
for (int i = 0; i < N; ++i) {
int c, m, e;
cin >> c >> m >> e;
students[i] = make_tuple(c + m + e, c + m, max(c, m), i);
}
sort(students, students + N, greater<tuple<int, int, int, int>>());
int rank[N];
int curr_rank;
tuple<int, int, int> last_student = make_tuple(-1, -1, -1);
for (int i = 0; i < N; ++i) {
if (make_tuple(get<0>(students[i]), get<1>(students[i]), get<2>(students[i])) != last_student) {
last_student = make_tuple(get<0>(students[i]), get<1>(students[i]),get<2>(students[i]));
curr_rank = i + 1;
}
rank[get<3>(students[i])] = curr_rank;
}
for (int i = 0; i < N; ++i) {
cout << rank[i] << endl;
}
return 0;
}B-smooth 数
题面描述
小杨同学想寻找一种名为B-smooth 数的正整数。
如果一个正整数的最大质因子不超过B,则该正整数为B-smooth 数。
小杨同学想知道,对于给定的n和B,有多少个不超过n的B-smooth 数。
输入格式
第一行包含两个正整数n,B,含义如题面所示。
输出格式
输出一个非负整数,表示不超过n的B-smooth 数的数量。
样例输入
样例输出
样例解释
在不超过10的正整数中,3-smooth 数有{1,2,3,4,6,8,9},共7个。
数据范围

对于全部数据,保证有1≤n≤106,1≤B≤106。
#include<bits/stdc++.h>
using namespace std;
int main() {
int n, B;
cin >> n >> B;
assert(1 <= n && n <= 1e6);
assert(1 <= B && B <= 1e6);
vector<bool> vis = vector<bool>(n + 5, false);
vector<int> mx_prime_factor = vector<int>(n + 5, 0);
vector<int> prime;
mx_prime_factor[1] = 1;
for (int i = 2; i <= n; i ++) {
if (! vis[i]) {
mx_prime_factor[i] = i;
prime.push_back(i);
}
for (int p : prime) {
if (1ll * p * i > n)
break ;
vis[i * p] = 1;
mx_prime_factor[i * p] = max(mx_prime_factor[i * p],max(mx_prime_factor[i], p));
if (i % p == 0)
break ;
}
}
int ans = 0;
for (int i = 1; i <= n; i ++)
ans += (mx_prime_factor[i] <= B);
cout << ans;
return 0;
}巧夺大奖(2023.9C++五级)
时间限制:1.0 s
内存限制:128.0 MB
问题描述
小明参加了一个巧夺大奖的游戏节目。主持人宣布了游戏规则:
1、游戏分为n个时间段,参加者每个时间段可以选择一个小游戏。
2、游戏中共有n个小游戏可供选择。
3、每个小游戏有规定的时限和奖励。对于第i个小游戏,参加者必须在第Ti个时间段结束前完成才能得到奖励Ri。
小明发现,这些小游戏都很简单,不管选择哪个小游戏,他都能在一个时间段内完成。关键问题在于,如何安排每个时间段分别选择哪个小游戏,才能使得总奖励最高?
输入描述
输入第一行,包含一个正整数n。 既是游戏时间段的个数,也是小游戏的个数。约定1≤n≤500。
输入第二行,包含n个正整数。第i个正整数为Ti,即第i个小游戏的完成期限。约定1≤Ti≤n。
输入第三行,包含n个正整数。第i个正整数为Ri,即第i个小游戏的完成奖励。约定1≤Ri≤1000。
输出描述
输出一行,包含一个正整数C,为最高可获得的奖励。
样例输入1
7
4 2 4 3 1 4 6
70 60 50 40 30 20 10
样例输出1
230
样例解释1
7个时间段可分别安排完成第4、2、3、1、6、7、5个小游戏,其中第4、2、3、1、7个小游戏在期限内完成。因此,可以获得总计40+60+50+70+10=230的奖励。
#include <iostream>
#include <algorithm>
using namespace std;
int n = 0;
struct game_t {
int T, R;
} games[500];
bool game_cmp(game_t x, game_t y){
return x.R > y.R;
}
bool arrange[500];
int main() {
cin >> n;
for (int i = 0; i < n; i++)
arrange[i] = false;
for (int i = 0; i < n; i++)
cin >> games[i].T;
for (int i = 0; i < n; i++)
cin >> games[i].R;
sort(games, games + n, game_cmp);
int sum = 0;
for (int i = 0; i < n; i++) {
for (int t = games[i].T - 1; t >= 0; t--)
if (!arrange[t]) {
arrange[t] = true;
sum += games[i].R;
break;
}
}
cout << sum << endl;
return 0;
}