no.10
NTT__int128
·
·
个人记录
no.10 总结
T1 monster
正解
不难发现，答案为 \sum\limits_{T\subseteq\{1,2,\cdots,n\}}\left(\max\limits_{i\in T}a_i-\operatorname{Card}(\{a_i|i\in T\})\right)，其中，\operatorname{Card}(T) 为集合 T 中元素个数。
考虑把两部分拆开来算。
第一部分：从小往大枚举 a_i，则答案为 \sum\limits_{i=1}^n2^{i-1}a_i。
第二部分：假设序列 a 去重后为 b_1,b_2,\cdots,b_l，出现次数为 c_1,c_2,\cdots,c_l，则答案为 \sum\limits_{i=1}^l(2^{l_i}-1)\cdot2^{n-l_i}。
直接计算即可。
T2 and
20 pts
直接 BFS 判联通块。
40 pts
发现所有黑色格子联通，因此 l_x=l_y=0 时答案为 0。
T3 climb
40 pts
贪心。
设 [a,b] 的最高点为 d，分开计算 a\to d 与 d\to b（其实两端时差不多的）。
贪心，每次往右上一格，高度够了就直接往右，被挡住了就往上。
正解
考虑如何快速计算 a\to d。
设 [a,d] 中 h_i-i 最大值位置为 r，发现就是 a\to r 直接升，r\to d 升一段右一段。这么一定最优。
然后上 ST 表即可。
T4 starwar
20 pts
枚举起点，BFS 看哪个距离近。
35 pts
树。
直接选 1 的儿子里面子树大小最大的即可。
40 pts
乱搞，当 n>100 时只枚举 1 的儿子作为起点。