校赛选拔赛已经结束了，不管进不进校队，补题都是很重要的！

这场比赛除了个别有算法，其他大部分都是模拟题跟思维题，模拟题是有明显的过程叫你干什么你就干什么的题，主要考察你的代码能力，而思维题是根据题意总结结论的题，考察你的思维能力，而携带纸质资料为了不需要你们直接背诵知识点，是考察运用能力。下面是题解：

题解

A.三月七不会数数

三月七在生日时想数生日蛋糕上的蜡烛，但她总是数错。如果她数到的蜡烛数量为 X 根，而实际上每次她数的数量比真实数量少 Y 根，那么真实的蜡烛数量为：

思路分析

• 已知信息：

  • X：三月七实际数到的蜡烛数
  • Y：每次数错的数量（实际数量比她数到的多的部分）

• 问题转换：

  • 由于每次数到的数量都比实际少 Y 根，只需要将 Y 加到 X 上，就能得到真实的蜡烛数量。

示例说明

假设：

• 三月七数到了 10 根蜡烛（X = 10）
• 每次数错 2 根（Y = 2）

则真实蜡烛数为：

C++ 实现

下面给出一个简单的 C++ 代码示例，演示如何实现该题目：

#include<bits/stdc++.h>
 
#define endl '\n'
 
using namespace std;
 
using ll = long long;

int main(){
    int a, b;
    cin >> a >> b;
    cout << a + b; 
}

c语言实现

#include <stdio.h>
int main(){
    int a,b;
    scanf("%d%d",&a,&b);
    printf("%d",a+b);
    return 0;
}

B.坐电梯

题目描述了一个紧急赶电梯的场景，电梯最初在楼层 ，但需要先去 楼接客，然后才会前往 1 楼。我们需要计算自己在 1 楼等电梯的时间。

电梯运行规则：

• 电梯每秒可以移动一层。
• 到达 楼时会停留 10 秒。
• 然后电梯从 楼直接下降到 1 楼。

解题思路

1. 计算电梯到 楼的时间：

   • 如果 ，电梯需要上升 秒。
   • 如果 ，电梯需要下降 秒。

2. 计算电梯停留时间：

   • 电梯到达 楼后，需要额外停留 10 秒。

3. 计算电梯从 到 1 楼的时间：

   • 电梯从 下降到 1 楼，需要 秒。

最终答案即：

代码实现（c++）

#include<bits/stdc++.h>

#define endl '\n'

using namespace std;

int main(){
	int a, b;
	cin >> a >> b;
	
	int t = 10 + abs(a - b) + b - 1;
	cout << t; 
}

c语言实现

#include <stdio.h>
int main(){
    int a,b;
    scanf("%d%d",&a,&b);
    printf("%d",10 + abs(a - b) + b - 1);
    return 0;
}

C.本手妙手不如举手

题目给定一个奇数 n 代表比赛局数，以及一个长度为 n 的只包含 0 和 1 的字符串。字符串中：

• 1 表示该局比赛小卞同学会获胜，
• 0 表示该局比赛小卞同学会失利。

比赛规则是：获胜局数更多的一方获胜。由于 n 为奇数，小卞同学要获得冠军至少需要赢 (n/2 + 1) 盘。

另外，小卞同学有一次“举手”机会，可以将一局必输的比赛变为必胜。要求：

• 第一行输出：在不使用举手的情况下，小卞同学是否能获得冠军（即赢的局数是否不少于阈值）。
• 第二行输出：如果小卞同学使用举手（也只能使用一次），是否能获得冠军。

思路分析

1. 统计获胜局数
   遍历输入字符串，统计数字 1 的个数，记为 wins。

2. 确定获胜所需的最小局数
   由于总局数为 n（奇数），获胜的最小局数为
   

3. 判断正常情况下是否获胜
   如果 wins >= threshold 则不使用举手时就能获胜，输出 yes；否则输出 no。

4. 判断举手之后是否获胜
   小卞同学举手可以将一局输的变为赢，所以举手后最多可以赢 wins + 1 盘。
   如果 wins + 1 >= threshold 则举手后能够获胜，输出 yes；否则输出 no。

C++ 实现

以下给出一个简单的 C++ 代码示例：

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

int main() {
    int n;
    cin >> n;
    string s;
    cin >> s;
    
    int wins = 0;
    for (char c : s) {
        if (c == '1') {
            wins++;
        }
    }
    
    int threshold = n / 2 + 1;
    
    // 第一行：正常情况下是否能获胜
    if (wins >= threshold) {
        cout << "yes" << endl;
    } else {
        cout << "no" << endl;
    }
    
    // 第二行：使用举手后是否能获胜
    if (wins + 1 >= threshold) {
        cout << "yes" << endl;
    } else {
        cout << "no" << endl;
    }
    
    return 0;
}

c语言实现

#include <stdio.h>
const int N=100005;
int main(){
    int n;
    scanf("%d",&n);
    char str[N];
    getchar();
    scanf("%s",str);
    int c0=0;
    int c1=0;
    for(int i=0;i<n;i++){
        if(str[i]=='0'){
            c0++;
        }
        else{
            c1++;
        }
    }
    if(c1>c0){
        printf("yes\n");
    }
    else{
        printf("no\n");
    }
    if(c1+2>c0){
        printf("yes\n");
    }
    else{
        printf("no\n");
    }
    return 0;
}

D.年度最佳游戏

题目要求从互联网上的 n 条信息中找出一个游戏代码，该游戏的出现次数最少。如果多个游戏的出现次数相同，则选择最后一次出现位置最靠后的游戏代码。

分析

1. 统计出现次数
   遍历输入字符串，统计每个游戏（大写字母）的出现次数。

2. 记录最后出现位置
   在遍历的同时记录每个游戏最后一次出现的索引（可以使用 0-based 索引）。

3. 确定候选游戏

   • 首先选出出现次数最少的游戏。
   • 如果多个游戏出现次数相同，则选取最后一次出现位置最靠后的那个。

4. 输出要求
   最终输出一个大写字母，严格小写的 yes 或 no 规则在本题中不适用，只需输出游戏的代码即可。

C++ 实现

下面给出一个 C++ 代码示例：

#include <iostream>
#include <string>
#include <vector>
using namespace std;

int main() {
    int n;
    cin >> n;
    
    string s;
    cin >> s;
    
    // 初始化频率和最后出现位置的数组
    vector<int> freq(26, 0);
    vector<int> lastOccurrence(26, -1);
    
    for (int i = 0; i < n; i++) {
        int idx = s[i] - 'A';
        freq[idx]++;
        lastOccurrence[idx] = i; // 更新最后一次出现的位置
    }
    
    // 选择出现次数最少的游戏
    int minFreq = n + 1; // 初始设一个大值
    char ans = 'A';
    int lastPos = -1;
    
    // 遍历所有可能出现的游戏（A-Z）
    for (int i = 0; i < 26; i++) {
        if (freq[i] > 0) { // 只考虑出现过的游戏
            if (freq[i] < minFreq) {
                minFreq = freq[i];
                ans = 'A' + i;
                lastPos = lastOccurrence[i];
            } else if (freq[i] == minFreq && lastOccurrence[i] > lastPos) {
                // 当频率相同时，选择最后出现位置更靠后的游戏
                ans = 'A' + i;
                lastPos = lastOccurrence[i];
            }
        }
    }
    
    cout << ans << endl;
    return 0;
}

c语言实现

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int main() {
    int n;
    scanf("%d", &n);
    
    // 动态分配字符串空间
    char *s = (char*)malloc((n + 1) * sizeof(char));
    if (!s) {
        fprintf(stderr, "Memory allocation failed\n");
        return 1;
    }
    scanf("%s", s);
    
    // 初始化频率数组（自动清零）和最后出现位置数组
    int freq[26] = {0};
    int last_occurrence[26];
    memset(last_occurrence, -1, sizeof(last_occurrence));  // 使用memset初始化为-1
    
    // 遍历字符串更新数据
    for (int i = 0; i < n; i++) {
        int idx = s[i] - 'A';  // 转换为0-25的索引
        freq[idx]++;
        last_occurrence[idx] = i;
    }
    
    // 寻找出现次数最少且最后出现的字符
    int min_freq = n + 1;
    char ans = 'A';
    int last_pos = -1;
    
    for (int i = 0; i < 26; i++) {
        if (freq[i] > 0) {
            // 发现更小的频率，或者相同频率但更晚出现
            if ((freq[i] < min_freq) || 
                (freq[i] == min_freq && last_occurrence[i] > last_pos)) {
                min_freq = freq[i];
                ans = 'A' + i;
                last_pos = last_occurrence[i];
            }
        }
    }
    
    printf("%c\n", ans);
    return 0;
}

E.资源规划

本题要求我们计算给定区间内的货币总数。已知有 n 天，每天可以获得一定数量的货币，并且接下来有 m 次询问，每次询问给定区间 [L, R]，需要计算第 L 天到第 R 天的货币之和。

思路分析

由于每天的货币数和询问次数都可能比较大（最多 10^5 条数据），若对每个询问从 L 到 R 遍历计算，时间复杂度可能较高。因此我们采用前缀和的方法，先预处理出一个前缀和数组，然后对于每个区间查询，可以在 O(1) 的时间内获得答案。

具体步骤如下：

1. 构建前缀和数组
   定义 prefix[0] = 0，然后对于 1 ≤ i ≤ n，有
   其中 a_i 表示第 i 天获得的货币数。

2. 快速求区间和
   对于每个查询区间 [L, R]，可以利用前缀和数组计算
   

3. 注意数据范围
   题目中给出的货币数可能非常大（例如 10^9），且 n 的上界为 10^5，所以区间和可能超过 32 位整数的范围。需要使用 long long 类型来存储前缀和及计算结果。

C++ 实现

下面给出完整的 C++ 代码示例：

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;
    
    // 使用 long long 存储数据
    vector<long long> arr(n);
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }
    
    // 构建前缀和数组，prefix[0] = 0
    vector<long long> prefix(n + 1, 0);
    for (int i = 1; i <= n; i++) {
        prefix[i] = prefix[i - 1] + arr[i - 1];
    }
    
    // 处理 m 次查询
    while (m--) {
        int L, R;
        cin >> L >> R;
        // 利用前缀和数组计算区间和
        long long sum = prefix[R] - prefix[L - 1];
        cout << sum << "\n";
    }
    
    return 0;
}

c语言实现

#include <stdio.h>
#include <stdlib.h>

int main() {
    int n, m;
    scanf("%d %d", &n, &m);
    
    // 动态分配数组存储数据
    long long *arr = (long long*)malloc(n * sizeof(long long));
    for (int i = 0; i < n; i++) {
        scanf("%lld", &arr[i]);
    }
    
    // 构建前缀和数组，prefix[0] = 0
    long long *prefix = (long long*)calloc(n + 1, sizeof(long long));
    for (int i = 1; i <= n; i++) {
        prefix[i] = prefix[i - 1] + arr[i - 1];
    }
    
    // 处理 m 次查询
    while (m--) {
        int L, R;
        scanf("%d %d", &L, &R);
        // 计算区间和并输出
        long long sum = prefix[R] - prefix[L - 1];
        printf("%lld\n", sum);
    }
    return 0;
}

java 实现

import java.util.*;
import java.math.*;
public class Main{
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        int m=sc.nextInt();
        long []arr = new long[n+1];
        for(int i=1;i<=n;i++){
            arr[i]=sc.nextInt();
        }
        for(int i=1;i<=n;i++){
            arr[i]+=arr[i-1];
        }
        while(m-->0){
            int x=sc.nextInt();
            int y=sc.nextInt();
            System.out.println(arr[y]-arr[x-1]);
        }
    }
}

F.打怪（eazy）

在本题中，你需要用有限的攻击力 M 杀死尽可能多的怪物，每个怪物拥有一定的血量 a[i]，只有当你对某个怪物累计造成的伤害至少等于其血量时，该怪物才会死亡。每造成 1 点伤害，你的攻击力就会减少 1 点。如果剩余攻击力不足以对某个怪物造成足够的伤害，那么该怪物无法被击杀。

思路分析

为了最大化击杀的怪物数，我们希望以最小的“花费”杀死怪物，即优先选择血量较低的怪物，因为这样能用更少的攻击力换取一次击杀。具体步骤如下：

1. 排序
   将所有怪物的血量从小到大排序。

2. 贪心选择
   遍历排序后的怪物列表：

   • 如果当前剩余攻击力 M 大于等于怪物的血量，就花费对应的攻击力将其击杀，并更新剩余攻击力。
   • 否则，无法击杀后续更高血量的怪物，终止遍历。

3. 注意数据范围
   本题数据规模不大（N ≤ 1000），且 M 的数值可能很大（最多 10^9），使用基本数据类型即可完成计算。

示例分析

例如：

• 示例1
  输入：N=4, M=10, 血量序列：2, 5, 8, 10
  排序后为：2, 5, 8, 10
  依次击杀：先用2点，剩余8；再用5点，剩余3；后续8、10均无法击杀。
  最终击杀怪物数为 2。

• 示例2
  输入：N=4, M=19, 血量序列：10, 2, 8, 7
  排序后为：2, 7, 8, 10
  依次击杀：先用2点，剩余17；再用7点，剩余10；再用8点，剩余2；剩余的10无法击杀。
  最终击杀怪物数为 3。

C++ 实现

以下是对应的 C++ 代码实现：

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int N;
    long long M;
    cin >> N >> M;
    vector<long long> health(N);
    for (int i = 0; i < N; i++) {
        cin >> health[i];
    }
    
    // 按照血量升序排序
    sort(health.begin(), health.end());
    
    int killCount = 0;
    for (int i = 0; i < N; i++) {
        if (M >= health[i]) {
            M -= health[i];
            killCount++;
        } else {
            break;
        }
    }
    
    cout << killCount << endl;
    return 0;
}

c语言实现

#include <stdio.h>
#include <stdlib.h>

// 比较函数用于qsort排序
int compare(const void *a, const void *b) {
    long long arg1 = *(const long long *)a;
    long long arg2 = *(const long long *)b;
    if (arg1 < arg2) return -1;
    if (arg1 > arg2) return 1;
    return 0;
}

int main() {
    int N;
    long long M;
    scanf("%d %lld", &N, &M);
    
    // 动态分配数组
    long long *health = (long long *)malloc(N * sizeof(long long));
    
    for (int i = 0; i < N; i++) {
        scanf("%lld", &health[i]);
    }
    
    // 排序
    qsort(health, N, sizeof(long long), compare);
    
    int killCount = 0;
    for (int i = 0; i < N; i++) {
        if (M >= health[i]) {
            M -= health[i];
            killCount++;
        } else {
            break;
        }
    }
    
    printf("%d\n", killCount);
    return 0;
}

题解

在本题中，你有 N 只怪，每只怪的血量分别为 a[i]；同时你拥有 M 点攻击力，每次对怪物造成 1 点伤害会消耗 1 点攻击力。当你对某个怪物累计造成的伤害达到该怪物的血量时，该怪就会死亡。不过如果某个怪的血量超过你当前剩余的攻击力，那么你就无法把它打死（因为你不能让攻击力变为负数）。

此外，你还拥有一个特殊技能“八雷飞度”，它可以无视怪物血量直接秒杀一个怪物，但该技能只能使用 K 次。目标是：在合理使用普通攻击和特殊技能的情况下，最多能打死多少个怪？

思路分析

直观策略是：

1. 尽可能用普通攻击
   使用普通攻击杀死血量较低的怪物。因为普通攻击需要消耗等量的攻击力，所以我们应该优先选择那些血量低、花费少的怪物。
2. 合理利用特殊技能
   对于那些血量过高（普通攻击无法消耗足够的攻击力将其杀死）的怪物，或是在普通攻击过程中剩余攻击力不足以杀死下一个怪物时，可以用特殊技能进行秒杀。但特殊技能使用次数有限（最多 K 次）。

由于普通攻击的成本和怪物血量直接相关，要在有限的攻击力 M 内杀死尽可能多的怪物，我们可以先将怪物按血量从小到大排序，然后依次累加血量，统计能用普通攻击杀死的怪物数记为 p。也就是说，选取最便宜的 p 只怪使得它们的血量总和不超过 M。

接下来，对于剩下的 N - p 只怪物，只能通过使用特殊技能来杀死，每次技能可秒杀一个怪，但最多只能使用 K 次。

因此，最多能打死的怪物数为：

其中：

• p：普通攻击能杀死的怪物数（选取了血量最低的那些怪物）。
• min(K, N - p)：剩余的怪物中，通过特殊技能能杀死的个数（技能最多用 K 次，但剩余怪物不足 K 个时只能杀剩下的怪物）。

示例说明

• 示例1
  输入：N = 4, M = 10, K = 1，怪物血量为 [2, 5, 8, 10]
  排序后：[2, 5, 8, 10]
  普通攻击：

  • 用 2 点攻击力杀死第一个怪物，剩余攻击力 10-2=8。
  • 用 5 点攻击力杀死第二个怪物，剩余攻击力 8-5=3。
  • 第三个怪物血量 8 大于剩余攻击力 3，无法用普通攻击杀死。
    因此，p = 2。
    剩余怪物数 = 4 - 2 = 2，但特殊技能只能用 1 次，所以额外能杀死 1 个。
    总计杀死数 = 2 + 1 = 3。

• 示例2
  输入：N = 4, M = 19, K = 4，怪物血量为 [10, 2, 8, 7]
  排序后：[2, 7, 8, 10]
  普通攻击：

  • 2 点 → 剩余 19-2=17
  • 7 点 → 剩余 17-7=10
  • 8 点 → 剩余 10-8=2
  • 第四个怪物血量 10 大于剩余攻击力 2，无法用普通攻击杀死。
    因此，p = 3。
    剩余怪物数 = 4 - 3 = 1，特殊技能最多杀 1 个（min(4, 1)=1）。
    总计杀死数 = 3 + 1 = 4。

C++ 实现

下面给出一个 C++ 代码示例：

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int N, K;
    long long M;
    cin >> N >> M >> K;
    vector<long long> health(N);
    for (int i = 0; i < N; i++) {
        cin >> health[i];
    }
    
    // 按照怪物血量从小到大排序
    sort(health.begin(), health.end());
    
    // 用普通攻击能杀死的怪物数
    int normalKills = 0;
    long long remainingAttack = M;
    for (int i = 0; i < N; i++) {
        if (remainingAttack >= health[i]) {
            remainingAttack -= health[i];
            normalKills++;
        } else {
            break;
        }
    }
    
    // 剩余怪物数
    int remainingMonsters = N - normalKills;
    // 特殊技能能杀死的怪物数（不超过 K 次）
    int specialKills = min(K, remainingMonsters);
    
    int totalKills = normalKills + specialKills;
    cout << totalKills << "\n";
    
    return 0;
}

c语言实现

#include <stdio.h>
#include <stdlib.h>

// 比较函数用于qsort排序
int compare(const void *a, const void *b) {
    long long arg1 = *(const long long *)a;
    long long arg2 = *(const long long *)b;
    if (arg1 < arg2) return -1;
    if (arg1 > arg2) return 1;
    return 0;
}
int min(int a,int b){
    if(a<b){
        return a;
    }
    return b;
}
int main() {
    int N;
    long long M;
    int k;
    scanf("%d %lld %d", &N, &M, &k);
    
    // 动态分配数组
    long long *health = (long long *)malloc(N * sizeof(long long));
    
    for (int i = 0; i < N; i++) {
        scanf("%lld", &health[i]);
    }
    
    // 排序
    qsort(health, N, sizeof(long long), compare);
    
    int killCount = 0;
    for (int i = 0; i < N; i++) {
        if (M >= health[i]) {
            M -= health[i];
            killCount++;
        } else {
            break;
        }
    }
    
    printf("%d\n", min(killCount+k,N));
    return 0;
}

java 实现

import java.util.*;
import java.io.*;
import java.math.*;

public class Main{
    //归并排序
    static void merge(long[] arr, int left, int mid, int right){
        long []b=new long[right-left+1];
        int i=left,j=mid+1,k=0;
        while(i<=mid&&j<=right){
            if(arr[i]<=arr[j]){
                b[k++]=arr[i++];
            }else{
                b[k++]=arr[j++];
            }
        }
        while(i<=mid){
            b[k++]=arr[i++];
        }
        while(j<=right){
            b[k++]=arr[j++];
        }
        for(int p=0;p<b.length;p++){
            arr[left+p]=b[p];
        }
    }
    static void mergeSort(long[] arr, int left, int right){
        if(left>=right){
            return;
        }
        int mid=(left+right)/2;
        mergeSort(arr,left,mid);
        mergeSort(arr,mid+1,right);
        merge(arr,left,mid,right);
    }

    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        long m=sc.nextLong();
        int k=sc.nextInt();
        long[] arr=new long[n];
        for(int i=0;i<n;i++){
            arr[i]=sc.nextInt();
        }
        //归并排序，复杂度O(nlogn)
        mergeSort(arr,0,n-1);
        int count=0;
        for(int i=0;i<n;i++){
            m-=arr[i];
            if(m>=0){
                count++;
            }
            else{
                break;
            }
        }
        System.out.println(Math.min(n,count+k));
    }
}