2025CSP-J/S游记

· · 生活·游记

-J

压缩包没有后缀名卡了我5min，导致8：35开始做题。

T1T2 25min秒了，开始想T3。

T3诡异异或和，没有思路，看T4。

T4一眼dp，很可惜没有往背包上想，导致一个小时也推不出转移方程，最终打出暴力+数学共64pts。

简单说一下，全1的情况下，答案显然是 C_n^3+C_n^4+......+C_n^n，于是，由二项式定理，得到ans=2^n-C_n^2-C_n^1-C_n^0，直接暴力计算即可。

T3还是不会写，逐打暴力。

预计289~294pts

-S

T1使我想到一道往年的经典dp题目：Emiya，于是开始想dp，死磕，推不出来，后来想到反悔贪心，非常可惜没有继续想下去，先看T2了。为什么不想为什么不想为什么不想为什么不想为什么不想为什么不想为什么不想为什么不想

T2很明显是MST，前4个点甚至是纯MST板子，于是先写库鲁斯卡尔拿到16pts。

然后看特殊性质，这不就是多建两条边么！调了1h写完了部分分，自己造极限数据最慢能跑到3s，应该能过。（机器是3代i3，4G内存，测试时用U9 285K）

小插曲：考试结束前15min发现自己T2读错题了，我当时以为乡镇是结点中的一个，从已有的节点新建边。这15min真的是我人生中的智力巅峰，好在是改出来了。

T3T4看一眼就知道不会，T3暴力都不会打，T4暴力打错了我是蒟蒻ww

T3有同学写的AC自动机，不知道对不对，T4看着像神秘dp，但不会。

T1居然有好多高中同学都不会写，心里平衡了点。

总之，只打了T1T2，估分20~75之间，主要看评测机给不给力。要坠机了，明年再战！

二编：

void merge(int x,int y){
    fa[x]=y;
    return;
}

T2 48pts->0

预计25pts