专栏文章

CSP-S 2024 游记 & 题解

jjesse1216
生活·游记参与者 3已保存评论 2

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
2 条
当前快照
1 份
快照标识符
@mhza8hpr
此快照首次捕获于
2025/11/15 04:00
4 个月前
此快照最后确认于
2025/11/29 04:50
3 个月前
查看原文

CSP-S 2024\textbf{CSP-S 2024} 游记

没报 J\textbf J 组，上午在学校上数学课，某同学带了 NOI\textbf{NOI} 辞典过去听课。。。中午回家吃饭，下午不到两点就到了考场，发现不让进。在外面溜达了一会，碰到一堆大神，但周围也很多小学生，感觉要被单调队列了。
终于让进了，坐下后先把背景换成了“暴力出奇迹”，小企鹅还挺可爱的。默写了一下快读快写板子，结果输入输出负数写错了，第二题调试时候改了快读，快写错到最后不过不影响。。。
14:3014:30 开题，直接看第一题，当成了贪心 + 模拟做，用了快 3030 分钟才搞完。写了个批处理文件测了大样例，一遍过，自信地交了上去。
接下来看第二题，为什么用简单物理背景出题，还给了三条公式。。。一眼看出是两道黄题（二分查找、最小点覆盖）拼接起来的，开始写，边界调了半天，16:1016:10 左右搞定。
第三题题面写的乱七八糟，还定义了个 CC 数组，瞪出了一个 n2n^2 DP，结果打着打着发现了后效性，立刻全删。突然发现贪心：最优情况下每个点只可能与左侧最近相同数产生得分。简单举了个例子证了一下，转化成类似选区间问题，就是 O(n)O(n) DP。开始写代码，1010 分钟过去大样例一个没过。此时已是 17:2017:20。出去上了个厕所，发现外面好冷。回来再一分析发现空区间可以直接选。调整了一下代码，样例 11 过掉，样例 22 差两个点。突然发现边界写的乱七八糟，改了一下过了，感谢样例强度。1818 点整。
只剩半个小时了，第四题题面又很古怪，来来回回读了三遍读懂了，手模了样例，4040 分（可能是 6060）暴力思路想了出来，但是代码可能比较长写不完，果断放弃想特殊性质。8/168/16 分（不确定）代码用 1515 分钟写完。一遍过，交了上去。最后 55 分钟，开始收拾东西，心想今年又考砸了，前面做题太慢，最后一题暴力没拿满，悲伤。预估分数 100+100+100+[8,16]=[308,316]100+100+100+[8,16]=[308,316]。
周六找了个时间重写了遍前三题代码，交到洛谷上都满分，心里踏实了一些。周日有人把压缩包密码破开了（怎么这么快），把考场代码交了上去，100+100+100+28=328100+100+100+28=328，心想最后一题数据什么情况。看了数据范围发现 T=1T=1 时这种做法确实不是很好卡。
周中计蒜客又出了估分系统，100+100+100+40=340100+100+100+40=340，数据水到家了吧。
最终分数 100+100+100+8=308100+100+100+8=308，数据强度还是可以的。

P1∼P3\textbf{P1}\sim\textbf{P3} 题解

决斗（duel\texttt{duel}）

题目描述

洛谷题目链接。
今天是小 Q 的生日，他得到了 nn 张卡牌作为礼物。这些卡牌属于火爆的“决斗怪兽”，其中，第 ii 张卡代表一只攻击力为 rir_i，防御力也为 rir_i 的怪兽。
一场游戏分为若干回合。每回合，小 Q 会选择某只怪兽 ii 以及另一只怪兽 j(i≠j)j(i \neq j)，并让怪兽 ii 向怪兽 jj 发起攻击。此时，若怪兽 ii 的攻击力小于等于怪兽 jj 的防御力，则无事发生；否则，怪兽 jj 的防御被打破，怪兽 jj 退出游戏不再参与到剩下的游戏中。一只怪兽在整场游戏中至多只能发起一次攻击。当未退出游戏的怪兽都已发起过攻击时，游戏结束。
小 Q 希望决定一组攻击顺序，使得在游戏结束时，未退出游戏的怪兽数量尽可能少。

我的考场做法

贪心：先让能力较低的怪兽打最小的，再让其他怪兽把他打死。
先算出每种能力值的怪兽出现次数 cnticnt_i。设 aia_i 表示 ii 能力值且还可以攻击的怪兽个数，bib_i 表示 ii 能力值且还未被攻击的怪兽的个数。一开始 ai=bi=cntia_i=b_i=cnt_i。
从小到大遍历 ii，每一次让 aia_i 个怪兽尝试消灭更小的怪兽。用双指针解决。时间复杂度 O(n+r)O(n+r)。

其他人的做法

题目等价于将排序后的 rr 划分成严格上升子序列数目最小值，也就等于 rr 中出现个数最多的数出现的次数。时间复杂度 O(n+r)O(n+r) 或 O(nlog⁡2n)O(n\log_2 n)（取决于排序算法）。

超速检测（detect\texttt{detect}）

题目描述

洛谷题目链接。
这个周末，主干道上预计出现 nn 辆车，其中第 ii 辆车从主干道上距离最南端 did_i 的位置驶入，以 viv_i 的初速度和 aia_i 的加速度做匀加速运动向北行驶。我们只考虑从南向北的车辆，故 vi>0v_i > 0，但 aia_i 可正可负，也可以为零。当车辆行驶到主干道最北端（即距离最南端为 LL 的位置）或速度降为 00（这只可能在 ai<0a_i < 0 时发生）时，我们认为该车驶离主干道。
主干道上设置了 mm 个测速仪，其中第 jj 个测速仪位于主干道上距离最南端 pjp_j 的位置，每个测速仪可以设置开启或关闭。当某辆车经过某个开启的测速仪时，若这辆车的 瞬时速度超过了道路限速 VV，那么这辆车就会被判定为超速。注意当车辆驶入与驶出主干道时，如果在对应位置有一个开启的测速仪，这个测速仪也会对这辆车进行测速。
上司首先想知道，如果所有测速仪都是开启的，那么这 nn 辆车中会有多少辆车被判定为超速。
其次，为了节能，部门想关闭一部分测速仪。然而，他们不希望漏掉超速的车，也就是说，当 nn 辆车里的某辆车在所有测速仪都开启时被判定为超速，他们希望在关闭一部分测速仪以后它依然被判定为超速。上司还想知道在这样的条件下最多可以关闭多少测速仪。

我的考场做法

先算出这些车辆通过哪些测速仪时会被判定为超速，分类讨论。
  • ai=0a_i=0，汽车进行匀速直线运动：
    • vi≤Vv_i\le V，则汽车在整段道路上都没有超速。
    • vi>Vv_i>V，则汽车从进入道路开始都是超速的，二分算出进入道路后第一个测速仪，则从这个测速仪到最后一个测速仪都是超速的。
  • ai<0a_i<0，汽车进行减速直线运动：
    • vi≤Vv_i\le V，则汽车在整段道路上都没有超速。
    • vi>Vv_i>V，则从行驶到 V2−vi22ai+di\dfrac{V^2-v_i^2}{2a_i}+d_i 前（不含）都超速了，仍用二分计算。
  • ai>0a_i>0，汽车进行加速直线运动：
    • vi>Vv_i>V，则汽车进入道路后一直超速。
    • vi≤Vv_i\le V，则汽车行驶到 V2−vi22ai+di\dfrac{V^2-v_i^2}{2a_i}+d_i 后（不含）就一直超速。
善用 lower_bound 和 upper_bound（注意区别：前者是第一个 ≥\ge 给定值的最小元素，后者是 >>）。
这样第一问答案被计算完了。考虑第二问：每个被判定为超速的汽车被某个区间内的测速仪记录，为了保证仍然被抓到，这个区间内需要有测速仪开启。
问题转化为给定若干区间，选出尽可能少的点使得每个区间都有选出的点。
很典型的贪心：按右端点排序，依次遍历区间，如果没有被覆盖，选右端点。（也可左端点排序进行贪心，但略复杂，容易写错。）
时间复杂度 O(nlog⁡2(nm))O(n\log_2(nm))。

染色（color\texttt{color}）

题目描述

洛谷题目链接。
给定一个长度为 nn 的正整数数组 AA，你要将 AA 中的每个数染成红色或蓝色之一，然后按如下方式计算最终得分：
设 CC 为长度为 nn 的整数数组，对于 AA 中的每个数 AiA_i（1≤i≤n1 \leq i \leq n）：
  • 如果 AiA_i 左侧没有与其同色的数，则令 Ci=0C_i = 0。
  • 否则，记其左侧与其最靠近的同色数为 AjA_j，若 Ai=AjA_i = A_j，则令 Ci=AiC_i = A_i，否则令 Ci=0C_i = 0。
你的最终得分为 CC 中所有整数的和，即 ∑i=1nCi\sum \limits_{i=1}^n C_i。你需要最大化最终得分，请求出最终得分的最大值。

我的考场做法

先预处理出每个数 AiA_i 左侧最近的相同的数 ApiA_{p_i}。则这一对数对答案做出贡献当且仅当 Api+1∼Ai−1A_{p_i+1}\sim A_{i-1} 同色，且与 ApiA_{p_i} 和 AiA_i 不同色。
转化成一个区间 [pi,i][p_i,i]，其权值为 AiA_i。现在要从这 (≤)  n−1(\le)\;n-1 个区间中选出若干个，使得和最大。选出的任意两个区间 [pi,i],[pj,j]  (i<j)[p_i,i],[p_j,j]\;(i<j) 需满足以下两条中的一条：
  • pj<pi=i−1<i<jp_j<p_i=i-1<i<j，即第一个区间长为 22，且包含于第二个（不含端点）；
  • i≤pji\le p_j，即要么不交，要么交集恰好为 {i}\{i\}。
动态规划：dp[i]dp[i] 表示上一个区间结尾为 ii 的答案。转移方程 dp[i]=max⁡(dp[i−1],dp[p[i+1]]+Ai+1+∑i=p[i+1]+2iAi×[p[i]=i−1])dp[i]=\max(dp[i-1],dp[p[i + 1]]+A_{i+1}+\sum_{i=p[i+1]+2}^{i}A_i\times[p[i]=i-1])，可以前缀和优化。最终答案 dp[n−1]dp[n-1]。时间复杂度 O(n+A)O(n+A)。

其他人的做法

评论

共 2 条评论，欢迎与作者交流。

正在加载评论...