专栏文章

no.10

NNTT__int128
个人记录参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@ming2cct
此快照首次捕获于
2025/12/02 01:49
3 个月前
此快照最后确认于
2025/12/02 01:49
3 个月前
查看原文

no.10 总结

T1 monster

正解

不难发现，答案为 ∑T⊆{1,2,⋯ ,n}(max⁡i∈Tai−Card⁡({ai∣i∈T}))\sum\limits_{T\subseteq\{1,2,\cdots,n\}}\left(\max\limits_{i\in T}a_i-\operatorname{Card}(\{a_i|i\in T\})\right)，其中，Card⁡(T)\operatorname{Card}(T) 为集合 TT 中元素个数。
考虑把两部分拆开来算。
第一部分：从小往大枚举 aia_i，则答案为 ∑i=1n2i−1ai\sum\limits_{i=1}^n2^{i-1}a_i。
第二部分：假设序列 aa 去重后为 b1,b2,⋯ ,blb_1,b_2,\cdots,b_l，出现次数为 c1,c2,⋯ ,clc_1,c_2,\cdots,c_l，则答案为 ∑i=1l(2li−1)⋅2n−li\sum\limits_{i=1}^l(2^{l_i}-1)\cdot2^{n-l_i}。
直接计算即可。

T2 and

20 pts

直接 BFS 判联通块。

40 pts

发现所有黑色格子联通，因此 lx=ly=0l_x=l_y=0 时答案为 00。

T3 climb

40 pts

贪心。
设 [a,b][a,b] 的最高点为 dd，分开计算 a→da\to d 与 d→bd\to b（其实两端时差不多的）。
贪心，每次往右上一格，高度够了就直接往右，被挡住了就往上。

正解

考虑如何快速计算 a→da\to d。
设 [a,d][a,d] 中 hi−ih_i-i 最大值位置为 rr，发现就是 a→ra\to r 直接升，r→dr\to d 升一段右一段。这么一定最优。
然后上 ST 表即可。

T4 starwar

20 pts

枚举起点，BFS 看哪个距离近。

35 pts

树。
直接选 11 的儿子里面子树大小最大的即可。

40 pts

乱搞，当 n>100n>100 时只枚举 11 的儿子作为起点。

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...