赛爱死批额令额雾杠姐斜杠爱死游记

xie_T34 · 2025-11-03 11:11:02 · 生活·游记

考完有点小破防导致游记写得很水，最终成绩发布以后给我气笑了，故重置。

Day <0

打板子，打根本不是人的模拟赛，和同学一起在机房里面打牌，和同学在机密航天把把丢人撤离。

神秘模拟赛里面包含了一大坨神秘题，比如用 a-b 排序，用 \frac{a+b}{2} 排序的神秘小贪心，随机化 DP 的，卡 SPFA 但是不完全卡的，放子序列自动机的。

Day 0

出校门第一件事：买一包士力架！

考点在遥远的绵阳，无法与 ARIS1_25 顺利面积了。😭😭😭

但是星期五中午就放学，下午回家可以爽打三角洲。😋😋😋

老朋友送了我飞龙 S.4，这下又不得不玩战争雷霆了。😋😋😋

晚上到了酒店带队教练把手机收了，所以那天晚上没有回复各位朋友的消息，在这里说一声抱歉。

Day 1

J

上午考 J 组！酒店早餐我吃的是豆浆配小笼包，味道不错。教练要求必须穿校服！（不是 CW 的校服）但是我没有接到任何通知啊？

原校校服我都不知道扔到哪个角落去了......

教练还说为什么别人都穿了校服就我不穿。因为别人都是直接从学校来的啊......就我是从家里来的。

教练让我穿另外一个不考 J 的同学的校服。

臭！！死！！我！！了！！😭😭😭

（据了解，这是整个机房里面最不爱卫生的入）

在校门口照完合照就进去了。南山特有的内校学生沉浸式引导，体验一级棒！

进入考场，开始打缺省源，我不喜欢 ios，所以用的是我的老缺省源。

#include<bits/stdc++.h>
#define ll long long
using namespace std;
inline ll read(){
    ll x=0,w=1;
    char ch=0;
    while(ch<'0'||ch>'9'){
        if(ch=='-')w=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=(x<<3)+(x<<1)+(ch^48);
        ch=getchar();
    }
    return x*w;
}
void write(ll x){
    if(x<0){
        putchar('-');
        x=-x;
    }
    static int sta[35];
    int top=0;
    do{
        sta[++top]=x%10,x/=10;
    }while(x);
    while(top)putchar(sta[top--]+'0');
}
int main(){

    return 0;
}

开题！

上善若水。

哎哟一上来就看懂了 T4，CSP-J 特有的喜欢棍木。

但是还是要从 T1 开始慢慢打，今年主要把精力放在 S 上面，所以并不是很期望 AK，毕竟 AK 只是个好看点的 1=，我们学校注重奖项，而不是分数。

老师临考前给了我一包薯片，但是是黄瓜味的。

所以到底谁在喜欢黄瓜味和青柠味的薯片啊！！！！！！我觉得这纯纯异端吧。。。管它的，能吃。

T1 是并非神秘串串题。思路就是把字符串中的数字提取到桶中，然后倒序输出。慢慢打不着急，15 分钟的时候切掉了。

T2 是并非大模拟题。直接拿 for 跟着座位走就是了。一看样例怎么不对劲？啊，先输出列再输出行。还好样例测完了，刚开始那个输出 2 2 是真的阴，还没有大样例。现在差不多过了 20 分钟。（T1 用时是 T2 三倍的原因是我们压缩密码晚发了 5 分钟，又花了几分钟通览题面）

感觉今年比去年还简单，去年 T2 神秘走过来走过去不大不小模拟卡我半小时。感觉今年可以试试上个 350。

T3 开！诶诶这不对吧？J T3 放个位运算。有些初一小朋友可能看不懂是真的。（这是绵阳考点，SC 信息教育资源匮乏的学校基本都在这里）

诶诶这不对吧？我怎么没思路？不过看到区间，做个前缀和是不劣的。

嘶还是没有思路，打个 O(n^2) 暴力呗，注意我们找到合法区间以后可以进行一个小剪枝，即把遍历的左端点起点移到当前找到的区间的右端点处。测一下大样例。诶诶？怎么过 2\times10^5 了？

分析了一下，这个代码在随机数据下很有通过率。但是要是构造一个无合法区间的数据，我们就完了！怎么办怎么办？有了！

我们记 cnt_{i,j} 为 1\sim i 的数二进制表示下第 j 位为 1 的前缀和。当我们判断区间 [l,r] 时，若 k 的第 j 位为 1 但是 cnt_{r,j}-cnt_{l-1,j}=0，说明怎么都拼不出来一个 k，直接跳过当前区间的内层枚举！测了一下大样例跑得更快了。

不愧是机房乱搞之神。🤓🤓🤓

保底 60 到手，预期能有 80。

不过这个做法还是拿脚都能卡，但是我们要心怀希望！为了防止在低数据下出现奇怪错误。我加了一个数据分讨，只有 n\ge 2\times 10^5 时才会启用该剪枝功能。（记住这个分讨）

现在差不多是一个小时。去骗点 T4 的分就能上 300！

T4，开！看到 998244353 内心一震，已经放弃思考正解了。

诶诶？DFS 居然能有 40？直接启动！

居然给了 \max_{i=1}^n a_i=1 的部分分，这种情况下每个方案都是合法的，故答案为 \sum_{i=3}^n C(n,i)。

两个小时了。诶诶？怎么就两个小时了？？？我还是太菜了。😭😭😭😭

管它的，100+100+[60,100]+64=[324,364]，怎么说都是个一等奖。开始吃薯片！😋😋😋😋

达成成就：在 CSP 里面 CSP（吃薯片）。

CSP 考场上考生 be like：

一不小心吃得大声了点，前面的同学往我这瞟了一眼（禁三警告）。吃完了，怎么还剩一个多小时啊！！锁屏睡觉！！

睡不着。😡😡😡

老师不让玩冲浪啊啊啊啊啊啊。

考试还剩 30 分钟 be like：

（罚坐这一块）

终于出考场力！！！

S

J 都那么简单，S 是不是也是糖糖题啊。

人杰地灵。

开！

T1，怎么这么眼熟？

三个参数，\frac{n}{2} 的限制。

模拟赛做过！！！部分分甚至有 c_i=0，原题这一块。😋😋😋😋😋😋

让我想想啊，模拟赛只有两个参数，这里有三个，怎么拓展？

首先还是调整法，假设全选 A，然后取前 \frac{n}{2} 个调整后代价最小的定在 A，后面的同学按次大值分配。总的来说就是用 \max(B,C)-A 升序排序。

样例全过！不愧是 Copy-Create-Few（复制多，创造少）。

诶诶？大样例怎么没过？

人工对拍启动！

第一组样例就有问题？调试一下。

怎么已经半个小时了。不要慌，T1 是有眉头的，再冲一下。

嘶，调了十多分钟还有问题。那应该是策略的问题了。

基于调整法，每个同学都选自己最想要的一个社团，那么最多只会有一个社团超过 \frac{n}{2} 的限制，这个时候再按上述排序就是对的了！

嗯，这个思路应该没问题，开始重构！

五十分钟，大样例全过！

T2 急速启动！

最小生成树啊。刚好是没复习过的算法。😰

我【数据删除】考前复习了最短路差分约束强连通分量缩点拓扑排序一大堆板子，你告诉我【数据删除】考最小生成树？？？

静下心来慢慢想。

嗯，兑，然后想不出来了。先把 16 分的裸最小生成树拿了。

观察到 k 很小，正解肯定是和 2^k 枚举有关的，CCF 换了新机子，复杂度顶到上限应该也是 OK 的，同时注意到只有最小生成树的边是有用的，所以我们只需要保留最小生成树的边，然后 2^k 枚举乡村情况，跑新的最小生成树。但是我没有想到把乡村当成点然后做最小生成树。😭😭😭

怎么什么关键点都想到了，就是没有想到这个在其他人眼中很平常的转化。

所以我的复杂度成功做到了与 O(n^2) 有关。因为一个乡村新增 O(n^2) 条边，我得拿邻接矩阵来存。

特殊性质也是平方的，劣完了。

最难绷的是，在邻接矩阵 B_{u,v} 中定义边权为 \min_{i=1}^k a_{i,u}+a_{i,v} 疑似是假的，而我从头至尾都没有发现。

写完 16 分以后尝试实现我的 O(n^2) 思路，但是写成一坨了，所以我在两个小时时先去写 T3 了。

T3 写了个超级大暴力，赛后分析复杂度是 O(nqL^2) 的。

T4 写了 O(n!) 暴力，以及在其它数据下输出 0。

写完这两道差不多三个小时了，啃点士力架！

我要放弃了吗？不！我不能放弃，必须坚持到最后一刻！

回到 T2，面对那一大坨，以及不满一个小时的剩余时间，我选择了——重构。

奇迹出现了，重构代码之后，大样例没有出现 WA 的情况，只有 AC 和 TLE 的情况。TLE 的点也跑了 5s 而已，在心里赌 CCF 的机子能过！

重构完我感觉人生圆满了，但是因为 T2 T3 超神秘复杂度导致我估不出来分。不过预估能有 180。

还剩十分钟结束怎么办？

（罚坐这一块）

终于出考场力！！！

后日谈

得知自己 S T2 暴力假了以后一度破防了两天并选择了休学回家。

后面心情好点了，但是还是很郁闷。

最终成绩发布了：

J：100+100+95+64=359

S：100+40+35+12=187

？你的意思是我的 J T3 平方算法差点过了？

？你的意思是我的 S T2 神秘假算一分不挂？

？你的意思是我的 S T3 超级暴力有 35？

？你的意思是我的 S T4 输出 0 能拿 4？

气笑了。

后面我把只有 n\ge 2\times 10^5 时才会启用剪枝的特判给删掉了，交到洛谷上面去。

过了？？？？？？？？？？

最慢点 80 毫秒？？？？？？？？？？？？

CCF 怎么这种数据都不会造？太一般了。

后面光速赛后写出 S T2 T3，要是考场上想到了 O(nk) 建边而非 O(n^2) 建边，那就是皆大欢喜了。😭😭😭

不过不用顶着绿勾过一辈子了，挺好的。😋😋😋

可惜了我的 7 勾。😭😭😭