杂(diao)题大赏

蒟蒻之泪 / 2024-10-09 / 原文

USACO的一些small Trick 题，可以康康

核心Trick使用粗体强调

1.Breakdown P

删改加不多说

考虑$K$很小，不妨meet in the middle，此时$k = 4$

处理出只包含一条边，两条边的“小组件”去“拼出”最短路，每次加边只需要更新新边端点涉及的组件以及最短路即可

2.Making Friends P

扫一遍，每个点向比他大的点建关系，然后合并

可以用$set$，也可以使用线段树合并

3.Palindromes P

考虑每一对字母移到某区间对称位置的贡献，位置$l,r$，区间$[L,r]$，贡献$|l + r - L - R|$

分奇偶性讨论，每次由内向外从一对扩展到另一对，使用树状数组维护$l + r$,$L + R$

4.Tractor Paths P

倍增

预处理出每个区间向左/右跳$2^i$步最远能跳到哪个区间，这个可以求出第一问

对于第二问，考虑前缀和，沿用上面的倍增，求出$2^i$步内有多少个特殊区间，最后使用右-左即为答案

5.Mana Collection P

推式子

设确定要收集的点集为${c_k}$，对应到达时刻为${t_k}$那么有式子$ans = \sum\limits_{i = 1}^k m_{c_k}\times t_k$

考虑时间拉满肯定不劣，所以$t_i = s - \sum\limits_{j = i}^{k - 1}d(c_j,c_{j + 1})$

带入:

\[\begin{aligned} ans &= \sum\limits _{i = 1}^{k}m_{c_i}(s - \sum\limits_{j = i}^{k - 1}d(c_j,c_{j + 1})) \\&= s\sum_{i = 1}^k m_{c_i} - \sum\limits _{i = 1}^{k}m_{c_i}\sum\limits_{j = i}^{k - 1}d(c_j,c_{j + 1}) \\&= s\sum_{i = 1}^k m_{c_i} - \sum\limits _{i = 1}^{k - 1}d(c_i,c_{i + 1})\sum\limits_{j = 1}^{i}m_{c_i} \end{aligned}\]

之所以把后面变一下，是方便状压预处理

\[dp_{S,i} = min(dp{s,k} + sum{s} \times d(k,j)) \]

第一维表示选的点集，第二维是终点，$d$用$Floyd$预处理,$sum = \sum_{i = 1}^k m_{c_i}$

然后回到式子，发现可以令$B = - \sum\limits _{i = 1}^{k - 1}d(c_i,c_{i + 1})\sum\limits_{j = 1}^{i}m_{c_i}$,也就是$dp_{S,c_k}$，$K = \sum_{i = 1}^k m_{c_i}$，$x = s$就是直线，可以上李超树，注意终点不同的要放入不同的树中

动态维护即可，复杂度没问题