C++ GESP 2023年6月真题 c++历年真题解析

单项选择

判断题

3

编程实战

1. 因数分解

题目分析

依次将 2、3、4、5、6 ... 除尽。

参考程序

#include <iostream>
#include <cstdio>
using namespace std;

typedef long long LL;

LL n;

int main() {

 cin >> n;
 
 bool is_first = true;
 for(int i = 2; i <= n / i; i++){
  if(n % i == 0){
   int x = 0;
   while(n % i == 0){
    x++;
    n /= i;
   }
 
   if(!is_first)
    cout << " * ";
   if(x == 1) cout << i;
   else cout << i << "^" << x;
   
   is_first = false;
  }
 }
 
 if(n > 1){
  if(!is_first) 
   cout << " * ";
  cout << n << endl;
 }
  
 return 0;
}

2. 巧夺大奖

题目分析

贪心算法：先按照奖励从大到小排序，再按照结束时间从后先前枚举，如果有空闲时间，就累加该奖励。

参考程序

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

const int N = 510;

struct Node{
 int t; // 截止时间 
 int r; // 收益 
 bool operator < (const Node& x) const{
  return r > x.r;
 }
}node[N];

int n;
int T[N];

int res = 0;

int main() {
 
 cin >> n;
 for(int i = 1; i <= n; i++) cin >> node[i].t;
 for(int i = 1; i <= n; i++) cin >> node[i].r;
 
 sort(node + 1, node + n + 1);
  
 for(int i = 1; i <= n; i++){
  for(int j = node[i].t; j >= 1; j--){
   if(T[j] == 0){
    T[j] = node[i].r;
    res += node[i].r;
    break;
   }
  }
 }
 
 cout << res << endl;
 
 return 0;
}