CSP2025游记
changchang111
·
·
生活·游记
CSP2025游记
CSP-J
看$T3$，想到了前缀和贪心，然后调了一会就过了。
$T4$~~又是小木棍~~一眼**dp**，想了个$O(n^3)$的做法。后来发现$\sum_{i=1}^{m} l_i$只要大于$2n$就一定可以，就优化到$O(n^2)$了。
### 估分：$100+100+100+100=400
CSP-S
$T2$发现$k\leq10$想到最小生成树$O(m*{\log m}*k*2^k)$，想了$30min$没想到优化就去看$T3$。
$T3$瞪了好久没思路，去看$T4$。$T4$一眼**dp**，但是$30min$没想到转移方程，就回去看$T2$。发现$n\leq 10^4$但$m\leq10^6$，可以先对原图$m$条边减成$n$条。这样就变成$O(n*{\log n}*k*2^k)$了。
写完发现大样例跑了$0.9s$，以为能过就去打$T4$的$n\leq10$和$m=1$或$n$的暴力分。~~$T3$暴力不会写~~
快结束时才发现$T2$大样例只有$n\leq10^3$，这下只能拿$60$分了……也没时间改了，就检查了一下文件就结束了。
### 估分：$100+[60,100]+0+[0,24]=[160,224]
没了