CSP-S 2025 游记

· · 生活·游记

博客园 可能食用更佳。

Day -4 ~ Day 0 (10.27~10.31)

既然是 CSP，为啥不能是在 cs1.6 中发 P 话呢：

对的对的，没错我就是 1 血反杀 4 人的那个，那一把在小镇神秘角落阴死了 OMITW，但是同一地点不同时间我用相同的枪阴死了不同人物也是个人物了。

然后队友也是个人物，在家里一直买投掷物乱扔投掷物，还好我跑得快不然就要吃闪了。

当然了我还去提瓦特大陆与幽境危战的灵主大战几十回合终于肘赢了：https://cdn.luogu.com.cn/upload/image_hosting/gh4ot92u.png

然后我请问了你既要我们参加体艺节开幕式的班级展演又不让我们参加后两天的体艺节和文艺晚会是何意味，搁着左右脑互博？

然后周五那天本来能喝奶茶/果茶，结果被告知第二天要考试怕我们喝了睡不着，但我不是下午才考试吗？？？然后奈雪的这个牛油果味奶昔也是依托大芬，喝出了不知道什么味道反正就是很难喝。

Day 1 (11.1)

周六早上看了点板子，结果下午没一个考的。

激情 cs1.6，仍然是在那个神秘点位阴死了很多人。

下午 13:30 就起床了，然后赶往科学楼考场。

14:10 到的考场，座位号为 1 的门口位一点都不好，然后发现自己没带透明水杯，那我没话说了只好少点出去喝水了，虽然一直到考试结束我都没有出去喝水（）。

14:27 下发了解压密码，感觉这次解压密码有点复杂。

14:30 创建选手文件夹，顺便把 check 要的 4 个题目的英文名先打了，然后开始看题。

T1 一开始以为是神秘 dp，看了眼数据发现 n=10^5 直接懵逼了，考虑贪心。

思考了 20min 未果，跑去看了眼 T2，用了 3min 发现是最小生成树，心里踏实了点就跑回去看 T1 了。

又思考了 20min 想出了一种贪心做法，分别对 a_{i,1},a_{i,2},a_{i,3} 进行排序，对于取了 a_{i,1} 前 \frac{n}{2} 大的数，后面取 \sum_{i=\frac{n}{2}+1}^{n} \max\{ a_{i,2},a_{i,3} \} 即可，对于 a_{i,2} 和 a_{i,3} 同理可得，时间复杂度为 \mathcal O(n \log n)，但很显然这样贪心是错误的，因为我连第二个样例都无法通过。

又思考了 20min 实在想不出来，决定打一下 T2。

约 15:30 开的 T2，大概这个时候监考员说了句“发呆的时候不要看别人的屏幕，以免被监控拍到误以为作弊”，反正我是没绷住的。

赛时看到 2^k=1024 不管了直接做了，结果不知道为啥忘记了原图可以只保留最小生成树上的 n-1 条边，总共存了 (m+nk) 条边，然后还忘记怎么打 Prim 了所以打的是 Kruskal，复杂度直接起飞了，然后并查集还没写按秩合并/启发式合并，写了个 \mathcal O(m \log m + (m+nk) \log (m+nk) + 2^k (m+nk) \log (n+k))，大洋里在赛时跑了 1.5s 感觉要完蛋，虽然是稍微剪了下枝但不知道要挂到几分了。

写完 T2 大概是 16:00，看了 3min T3 发现看不懂，于是先开了 T4，发现只会阶乘暴力了，想试着弄一下 A、B 性质结果被打飞了，容斥推不出来，遗憾只能获得 n \leq 18 的暴力分，打完 T4 已是 16:20。

T3 看了好久才看懂，赛时打了两个 map 来维护，过了样例感觉还行，后面就没管了，继续试图攻克 T1，此时大概是 16:55。

约 17:30 的时候，某位小朋友的电话手表响了（我请问了你是怎么过安检的），小朋友试图解释，然后被监考员发现了并把手表放出去了，我和我旁边那位小朋友一直在憋笑，监考员试图让考场保持安静，后面小朋友哭了，因为我坐在门口位所以不知道是哪位小朋友要试图 cos IOI 2024 国家队选手，反正当时场面挺混乱的。

18:00 的时候实在想不出怎么做 T1 了，遂检查了一下文件读写，并把程序扔去虚拟机跑了一下，发现没报错，然后就不管了，然后就在看着自己的键盘发呆（强调是自己的键盘而不是别的东西），或者是在草稿纸上不知道写了些什么东西。

18:20 监考员提醒把文件大小记在准考证上。

18:25 关闭了所有窗口。

18:27 考试结束，无法调出T1，有点破防，感觉今年的题比去年难，尤其是 T1 和 T2。

受不了了回家爽抽，与剧诗大战 3h 终于满星12层了：https://cdn.luogu.com.cn/upload/image_hosting/197ypfev.png

此时已经熬到了凌晨两点，然后爽睡到了10点然后接着爽抽。

下午打 codm 排位打破防了，神人队友打个热点站既不进点又不在点外断人是何意味，这次忍住了没有开麦问候队友，一群混子。

Day 2+ (11.2+)

赛后第二天回到机房的时候按着回忆打了下程序，交到洛谷民间数据大概是 15+88+0+8，显然 T2 是虚高了，T1 不知道能有多少个测试点能过，T3 我的 map 居然爆零了我服了，改了一下用 map + substr 可得 \texttt{35pts} 我真是服了。

再次看 T1 发现原来是反悔贪心，直接每一个都先选最大的，钦定对于每一个 i 最大值与次大值的差为 tmp_i，然后对于 cnt_x > \frac{n}{2},x=1/2/3 的 i 选前 (cnt_x-\frac{n}{2}) 小的 tmp_i 即可，时间复杂度为 \mathcal O(n \log n)，我服了原来 \frac{n}{2} 这个条件是这么用的吗，打了 10min 就过了，火大。

T2 改了一下，再把并查集搞了个启发式合并，时间复杂度为 \mathcal O(m \log m + nk \log nk + 2^k nk \alpha(n+k))，过了洛谷民间数据就没管了。

完了怎么我 T3 也没判断 |t_1| \neq |t_2|，那我没话说了。（upd on 11/5：欸数据还真保证了 |t_1|=|t_2|）

补完 T1、T2 就开始写游记了，没心情做题，分比去年低了好多，所以我还能去 NOIP 吗。

upd：10+64+0+8

upd on 11/6

666 T2 剪枝 \mathcal O(m \log m + (m+kn) \log (m+kn) + 2^k kn \log (k+n) ) 可过。

评测记录 https://www.luogu.com.cn/record/245605015

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e4+5,M=1e6+5,K=15;
const ll INF=0x3f3f3f3f3f3f3f3f;
int n,m,k,tot,c[K],fa[N+K];
bool vis[N];
ll ans;
struct Edge
{
    int u,v,w;
}e[M+K*N];
int find(int x)
{
    return fa[x]^x?fa[x]=find(fa[x]):x;
}
ll Kruskal()
{
    for(int i=1;i<=n;i++) fa[i]=i;
    sort(e+1,e+1+n,[](Edge a,Edge b){return a.w<b.w;});
    int cnt=1; ll res=0;
    for(int i=1;i<=tot;i++)
    {
        int u=find(e[i].u),v=find(e[i].v),w=e[i].w;
        if(u==v) continue;
        res+=w;
        if(++cnt==n) break;
    }
    return res;
}
void solve(int now,int cnt_used,ll cost)
{
    if(now>k)
    {
        for(int i=1;i<N+K;i++) fa[i]=i;
        int cnt=1; ll res=cost;
        for(int i=1;i<=tot;i++)
        {
            if(res>ans) break;//这里剪枝
            if(e[i].u>n&&!vis[e[i].u-n]) continue;
            int u=find(e[i].u),v=find(e[i].v),w=e[i].w;
            if(u==v) continue;
            fa[u]=v,res+=w;
            if(++cnt==n+cnt_used) break;
        }
        return ans=min(ans,res),void();
    }
    if(cost+c[now]<=ans)
    {
        vis[now]=true;
        solve(now+1,cnt_used+1,cost+c[now]);    
    }
    vis[now]=false;
    solve(now+1,cnt_used,cost);
}
int main()
{
    freopen("road.in","r",stdin);
    freopen("road.out","w",stdout);
    scanf("%d%d%d",&n,&m,&k),tot=m;
    for(int i=1;i<=m;i++)
        scanf("%d%d%d",&e[i].u,&e[i].v,&e[i].w);
    ans=Kruskal();
    int subA=0;
    for(int i=1;i<=k;i++)
    {
        scanf("%d",&c[i]),subA+=(!c[i]);
        for(int j=1;j<=n;j++)
        {
            int w;
            scanf("%d",&w),subA+=(!w);
            e[++tot]=(Edge){n+i,j,w};
        }
    }
    if(k&&subA==k*(n+1)) return puts("0"),0;
    sort(e+1,e+1+tot,[](Edge a,Edge b){return a.w<b.w;});
    solve(1,0,0);
    printf("%lld",ans);
    return 0;
}

666 剪枝没剪干净导致的