[C/C++]迈出在 CSP 的第一步 CSP-S2024

大家好，我是靳皓旭，没错就是那个人见人爱，花见花开的靳皓旭。你是不是对即将到来的 CSP-S 2024 游记十分期待与激动呢？我也是的。废话不多说，我们开始吧！

这次让我们迈出万里 CSP 路的第一步，这是历史性的一步，更是意义深远的一步，上升到人民，社会，国家。。。。。。扯多了，让我们回到正题，一起看比赛：CSP-S 2024，嗯很深奥，这套题看上去很难。点进去笑了，这是一名 AFO 的初三学生做的题吧！一起看一下描述：

[CSP-S 2024] 决斗

今天是小 Q 的生日，他得到了 n 张卡牌作为礼物。这些卡牌属于火爆的“决斗怪兽”，其中，第 i 张卡代表一只攻击力为 r_i，防御力也为 r_i 的怪兽。

一场游戏分为若干回合。每回合，小 Q 会选择某只怪兽 i 以及另一只怪兽 j(i \neq j)，并让怪兽 i 向怪兽 j 发起攻击。此时，若怪兽 i 的攻击力小于等于怪兽 j 的防御力，则无事发生；否则，怪兽 j 的防御被打破，怪兽 j 退出游戏不再参与到剩下的游戏中。一只怪兽在整场游戏中至多只能发起一次攻击。当未退出游戏的怪兽都已发起过攻击时，游戏结束。

小 Q 希望决定一组攻击顺序，使得在游戏结束时，未退出游戏的怪兽数量尽可能少。

吓死我了，我好害怕啊，不知道怎么才能 AC 这道题了，呜呜呜。呃呃，其实很简单，这是规则，不能违反。我们只能遵守咯。

样例一看，突然间仿佛回到了小学那时候，懵懂无知，天真无邪。。。咔，又跑题了。其实就是输入一堆数，求未退出游戏的怪兽数量的最小值。听到这里，你应该很胸有成竹，但是在打代码前我们先注意一些小细节哦！

1.我们在打代码时应该行首对齐，最好不要顶格，因为以后代码太长会很乱。 2.注意每句末尾加上分号 " 这其实相当于我们C语言中的句号，说活不能一口气一直说下去，要合理添加句号。

一定要做到以上两点哦，从开始就养成好的编程习惯，一定会给你带来好处。

我们一起看一下我打的代码：

#include<bits/stdc++.h>
using namespace std;
const int N=100005;
int a[N],n;
bool cmp(int _,int __){
    return _>__;
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
    }
    sort(a+1,a+n+1,cmp);
    int ans=n;
    for(int i=n,j=n;i>=1;i--){
        if(a[i]>a[j]){
            j--;
            ans--;
        }
    }
    printf("%d",ans);
    return 0;
}

[CSP-S 2024] 超速检测

小 D 新入职了某国的交管部门，他的第一个任务是负责国家的一条长度为 L 的南北主干道的车辆超速检测。为了考考小 D，上司首先需要他解决一个简化的场景。

这个周末，主干道上预计出现 n 辆车，其中第 i 辆车从主干道上距离最南端 d_i 的位置驶入，以 v_i 的初速度和 a_i 的加速度做匀加速运动向北行驶。我们只考虑从南向北的车辆，故 v_i > 0，但 a_i 可正可负，也可以为零。当车辆行驶到主干道最北端（即距离最南端为 L 的位置）或速度降为 0（这只可能在 a_i < 0 时发生）时，我们认为该车驶离主干道。

主干道上设置了 m 个测速仪，其中第 j 个测速仪位于主干道上距离最南端 p_j 的位置，每个测速仪可以设置开启或关闭。当某辆车经过某个开启的测速仪时，若这辆车的瞬时速度超过了道路限速 V，那么这辆车就会被判定为超速。注意当车辆驶入与驶出主干道时，如果在对应位置有一个开启的测速仪，这个测速仪也会对这辆车进行测速。

上司首先想知道，如果所有测速仪都是开启的，那么这 n 辆车中会有多少辆车被判定为超速。

其次，为了节能，部门想关闭一部分测速仪。然而，他们不希望漏掉超速的车，也就是说，当 n 辆车里的某辆车在所有测速仪都开启时被判定为超速，他们希望在关闭一部分测速仪以后它依然被判定为超速。上司还想知道在这样的条件下最多可以关闭多少测速仪。

由于 n 很大，上司允许小 D 使用编程解决这两个问题，于是小 D 找到了你。

如果你对于加速度并不熟悉，小 D 贴心地在本题的“提示”部分提供了有关加速度的公式。

啊呀，这是物理竞赛题吧！吓死我了，我好怕怕呀，不知道怎么才能过这个了。嗯嗯，其实很简单，每辆车超速的区间是连续的，所以可以直接二分，然后就转化成了经典问题之在 n 个区间里选最少的点使得每个区间内部都有一个点被选择。然后我就不会这个贪心了，不过也可以拿 60。

啊呀！我怎么用 %lld 输入了 int！60 分全没了。

[CSP-S 2024] 染色

给定一个长度为 n 的正整数数组 A，其中所有数从左至右排成一排。

你需要将 A 中的每个数染成红色或蓝色之一，然后按如下方式计算最终得分：

设 C 为长度为 n 的整数数组，对于 A 中的每个数 A_i（1 \leq i \leq n）：

• 如果 A_i 左侧没有与其同色的数，则令 C_i = 0。
• 否则，记其左侧与其最靠近的同色数为 A_j，若 A_i = A_j，则令 C_i = A_i，否则令 C_i = 0。

你的最终得分为 C 中所有整数的和，即 \sum \limits_{i=1}^n C_i。你需要最大化最终得分，请求出最终得分的最大值。

这是什么抽象玩意，打个 20 分跑路。

[CSP-S 2024] 擂台游戏

小 S 想要举办一场擂台游戏，如果共有 2^k 名选手参加，那么游戏分为 k 轮进行：

• 第一轮编号为 1, 2 的选手进行一次对局，编号为 3, 4 的选手进行一次对局，以此类推，编号为 2^k - 1, 2^k 的选手进行一次对局。
• 第二轮在只保留第一轮的胜者的前提下，相邻的两位依次进行一场对局。
• 以此类推，第 k - 1 轮在只保留第 k - 2 轮的 4 位胜者的前提下，前两位、后两位分别进行对局，也就是所谓的半决赛。
• 第 k 轮即为半决赛两位胜者的决赛。

确定了游戏晋级的规则后，小 S 将比赛的规则设置为了擂台赛。具体而言，每位选手都有一个能力值 a_1, a_2, \dots , a_{2^k}，能力值为 [0,2^{31}-1] 之内的整数。对于每场比赛，会先抽签决定一个数 0/1，我们将第 R 轮的第 G 场比赛抽到的数记为 d_{R,G}。抽到 0 则表示表示编号小的选手为擂主，抽到 1 则表示编号大的选手为擂主。擂主获胜当且仅当他的能力值 a\geq R。也就是说，游戏的胜负只取决于擂主的能力值与当前比赛是第几轮的大小关系，与另一位的能力值无关。

现在，小 S 先后陆续收到了 n 位选手的报名信息，他们分别告知了小 S 自己的能力值。小 S 会按照报名的先后顺序对选手进行编号为 1, 2, \dots, n。小 S 关心的是，补充尽量少的选手使总人数为 2 的整次幂，且所有选手进行一次完整的擂台游戏后，所有可能成为总冠军的选手的编号之和是多少。

形式化地，设 k 是最小的非负整数使得 2^k\geq n，那么应当补充 (2^k-n) 名选手，且补充的选手的能力值可以任取 [0,2^{31}-1] 之内的整数。如果补充的选手有可能取胜，也应当计入答案中。

当然小 S 觉得这个问题还是太简单了，所以他给了你 m 个询问 c_1,c_2,\dots,c_m。小 S 希望你帮忙对于每个 c_i 求出，在只收到前 c_i 位选手的报名信息时，这个问题的答案是多少。

诶我发现 8 分可做！

啊，我怎么写挂了！算了，已经六点了，不写了，检查 freopen 去了。

今天我们来学习的内容是 Dev-c++ IDE 的使用。

看度娘怎么解释的：Dev-c++ 是指 Dev-c++ IDE。IDE 的意思是碘的内能。

其实 Dev-c++ 就是 develop c++ IDE，主要用 IDE 编写程序。在 IDE 中有多种模式，包括 Release 和 Debug 等。

由此我们可以看出，如果在 Release 中编写了编译命令，在 Debug 中就不会有编译命令了。这就像碳硫磷硫两千零二十四中的第二题一样，如果你忘记了这一点，就会取得 0 的好成绩。

今天的收获可真多，我们学习了 Dev-c++ 的注意事项，Relese 模式还有它与 Debug 模式的区别，讲解之后是不是让你更加了解了编程知识呢，记得消化吸收哦！我是靳皓旭，下次再见！