CSP漫游坠机记🤔😭😋😡😭

cmd1343 · 2026-11-02 09:15:46 · 生活·游记

::::info[AI总结]{open}

以下为AI生成。

音晶在岛上跳着 long long 的舞，我伸手去接，接住了一个 int。

它断了。

不是音晶断了，是我以为它能装下 10^{12} 的那颗心断了。堆里的最小值在尖叫：

“你为什么不给我开龙龙！”

我捂着耳朵跑，跑进地铁口，花 w_i 分钟下到站厅，又花 t_{i,j} 走到站台，发现站台上站满了 e[2000010] 个幽灵，每一个都在重复同一句话：

“重边。重边。重边。”

它们是我亲手建的。同一对线路，在 20 个站重复相遇，每次相遇都 add 两条边，边权是 t_i+t_j，像极了我在错误 DP 上反复蠕动的样子——明明确认了反例，却还在原地 add。

链式前向星站在终点，举着一块牌子：

“不是说我是最好的存图算法吗？”

邻接矩阵从旁边路过，冷冷地取了个 `min`，把一万条重边压成一条，头也不回地走了。

前言

看了那么多游记速切T1T2，感觉自己这种奇异搞笑，不断犯错，成绩低下，T1T2写两遍的游记还是太少了，于是随便写了一篇。

本文按时间顺叙。

省流：T1堆和中间变量没开long long，挂。

T2链式前向星没开大，如果使用邻接矩阵取min可以满分，挂。

考场策略爆炸、算法不错导致两道能 AC 的题被long long、重边数组和重复思考拖累，T1T2浪费时间导致T3一团乱麻思绪混乱，本来200就很低了，这样一搞又少了不知道多少分。

day -?

结束集训，在机房里面呆了几天。

充分意识到自己代码水平的低下。

事实上的确如此。

day 0

应急复习了一堆图论板子。

事后证明一个都没用上。

day 0.5

得知早上的题目有细节错误。

然后下午考试直接忽略了这一点。

day 1

进考场前网易云音乐随到了幻想哀歌，不吉利于是换成了航船赞歌。

携带四枚健达巧克力进入考场。

开考

进入考场。拆开巧克力吃了第一根。

快速浏览四道题的题面并想了一下。

T1（第一阶段）

在这个地方浪费了大量时间。

对T1预期只有6种做法：反贪，贪，搜，DP，模，二分。

最开始想的是一个二分，枚举某个位置是否能达成最好点数。

然后发现参数太多很难用。

想起来和一道题很像于是写了一个意味不明DP。

当时还想出来了一个莫名其妙的u,代表这一段的值，最后又删掉了。（浪费了15min）

具体解释一下，dp[i].len代表以i为结尾的最长合法可抬升子序列长度（可抬升子序列指操作后每一个点的值都是和最后一个点的初始值一样的子序列）

sort(a+1,a+n+1);
dp[1].cost=0;//花费为0 长度为1 
dp[1].len=1; 
    for(long long i=2;i<=n;i++)
    {
        //扬升资格与花费：len*(a[i]-a[i-1]) 可以让它继续延续 
        if(dp[i-1].cost+1LL*dp[i-1].len*(a[i]-a[i-1])<=m)
        {
            dp[i].cost=dp[i-1].cost+1LL*dp[i-1].len*(a[i]-a[i-1]);
            dp[i].len=dp[i-1].len+1LL; 
        }
        else
        {
            dp[i].cost=0;
            dp[i].len=1;
        }
    }

最后把len的最大值跑了就行。

然后样例3炸了。

::::error[错误]

我在这里调了30min，思考为什么这样是错的，而且在得出结论之后竟然没改还在质疑自己的做法并且随机写东西。（总而言之，当抬升段花费过高时，将前面花费极高的移除来尽可能延长，如果实在不行就开新的）

实际上，不需要思考为啥做法是错的。只要疯狂蠕动就可以了。 ::::

T2（第一部分）

观察T2，初次被题面吓住，以为很难，于是打了一个特殊性质 A的暴力解。（直接建边每次查询都跑一次迪杰斯特拉），测样例发现自己4s+，坠入绝望之中。

::::error[错误]

我不应该在没有想正解的情况下就去写T2的暴力。

要相信自己是最棒的。（结果也证明了：我T2想了一会就出来了，甚至比T1折腾时间还少）
------------
上厕所，思考退役之后的人生。
::::error[错误]

为什么要在上厕所的时候悲伤？

T3

这个时候预估自己是要坠机了，T1思路错，T2看不出。😡（最后也是换了一个方法坠机的）。

本来想写特殊情况和暴力，但是犹犹豫豫最后思路挂了，红温状态下没法写。可惜了如果我冷静下来的话也不至于这样。

T1（第二部分）

根据之前拿的好思路写正解，写了一个反悔贪心。

如果能延续扬升序列就继续扬升。

如果不能延续扬升序列就不断pop前面的劣直到可以扬升。

粗略证明一下是对的。 ::::error[错误]

我建立堆和临时变量的时候没有注意到要开龙龙。

没有手搓最大样例。

为下文做铺垫。

5:16完成重构代码。把之前的注释掉了。

::::info[可以看出没有开long long]

long long cost=0,u=a[1],len=1;//现在值保持在u 花费了cost 长度为x 
    q.push(a[1]);//弹出来的要是最小值 
    for(int i=2;i<=n;i++) 
    {
        long long costi=a[i]-u;
        if(cost+costi*len<=m)
        {
            q.push(a[i]);//进去
            u=a[i];
            cost=cost+costi*len;
            len++;
            ans=max(ans,len);
        }
        else//不行的话 
        {
            //无法扬升 
            int ke=0;
            while(1)
            {
                if(q.empty())
                {
                    break;//弹出所有仍然不能扬升 
                }
                if(cost+costi*len<=m)//终于可以了 
                {
                    ke=1;
                    break; 
                }
                long long kr=q.top();
                len--;
                q.pop();
                cost-=(u-kr);//白培养了 收回这一部分 
                ans=max(ans,len);
            }
            if(ke)
            {
                q.push(a[i]);//进去
                u=a[i];
                cost=cost+costi*len;
                len++;
                ans=max(ans,len);
            }
            else
            {
                while(!q.empty()) 
                    q.pop();
                q.push(a[i]);
                cost=0;
                u=a[i];
                len=1;
                ans=max(ans,len);
            }   
        } 
    }

::::

十分高兴。

T2（第二部分）

冷静了，想正解。

对地铁精心拆解。分析一下造成时间的只有这几种情况：

进站：口->厅->台
换乘站：台->厅->台
出站：台->厅->口

出入可以预处理。

发现只有在换乘线路的时候才会增加时间。

于是重建图，做线路图的全源最短路。

ans=\min_{i\in \text{huant}[x],\; j\in \text{huant}[y]} \left( w_x+t_{i,x}+\text{disp}[i][j]+t_{j,y}+w_y \right)

节点 1\sim n 代表线路。
读入时维护 huant[v]：经过站 v 的所有线路及所有在 v 换乘的 t 值。
每当读到线路 i 经过站 v，就与 huant[v] 中已有的每条线路 j 建双向边，边权 huant[v][i].t+huant[v][j].t。 ::::error[错误]

我在重构代码的时候套用了原版的迪杰斯特拉和图。

且没有意识到会有大量的重边。

e数组没有开大。

这警示我们重构代码最好重新开一个文件。

意识到自己只会迪杰斯特拉，以为复杂度要飞了，于是崩溃测样例（根本没有想到Floyd）。

发现跑得飞快，就懒得做全量检查，也懒得自己造大样例（抽样测试了一下），🤪。

::::error[错误]

最好不要干这种傻事。

一定要讨论时空复杂度和优化。
# 剩下的时间
玩了一下linux。
::::error[错误]

我的水平还不会因为 NOI Linux 的平台差异而爆零，为啥要检查NOI linux下的情况。

被你省独有的各种表格折腾，反复看自己的freopen。

::::error[错误]

这些表格应该在没有思路的时候写。

出考场

意识到自己两道题做法都对，预估分数160→200，比较高兴。

回家

提交测试，发现自己两道题都有锅（没开龙龙，边爆炸）。

玉玉了。

发现自己的分数足以进NOIP，考再高也进不了WC，顶多是OIerDB上有一个难看的黄色三位数。（至少不是和去年一样S组美美隐身了）。

于是下载终末地玩玩。

但是包体太大了。

检查后发现两道题在不改核心思路的情况下均能AC。

这让我更加😡。

T1 改long long。
T2 把链式前向星换成了邻接矩阵500*500，每次建边取min，好像过了，无言以对，不是说链式前向星是最好的存图算法吗。

说句闲话

如果我成功避开非智力因素和策略问题，应该是T1调两次出正解，T2调一次出正解，多出来的时间整理T3思路打暴力，检查T1T2细节，大概250体面收场。

可惜现实没有如果。

一些有趣的事实

至少这不是NOIP 2026，也不是CSP 2027，还有机会，还有得救。
至少我T1T2的做法没有问题，就是速度、策略、思路、心态的问题。
下辈子记得检查数组和大样例测试的每一条输出，不要再抽样检查了。
我这个分数在同龄人里面应该算是奇异搞笑的水平了。
就算我达成了理论最高分也不是特别好（洛谷上一堆速切T1T2的），还是要加训。
文化课是好文明。
不要觉得自己没有能力挑战T2（泛指在个人水平附近的题目，对我这种半吊子就是T2），然后写一个莫名其妙的暴力。
将暴力升级为正解的时候不要犯懒，最好检查一遍留下的东西会不会炸。
主要是时间经过浪费后导致的不足（平时模拟赛4.5h）、T2懒得检查样例输出和T1官方大样例没发现bug这几个问题。当然还是要怪自己的。
写正解超出自己水平的题目的暴力时不要犹豫，有多少想法就写多少，不追求完美。
考场上不要玉玉或者狂喜。
注意构造出题人不给的极端样例。
时间分配不合理。没必要在开比赛快速浏览的时候看T4。
善用fc。
时间主要被重复的思考浪费（比如T1第一遍想做法的时候反复尝试自己已经排除的做法，T2写了两遍，T3瞎折腾，看T4）。以及多次反复不断关注freopen却不关注数组。
这场比赛本来就是肚子的为我们准备的模拟赛。
本人文章写作水平有限，请多多谅解。
加训，NOIP给自己争一个蓝钩。