今天也是不颓 。
所以到底是颓还是不颓？
没搞懂。
等洛谷上有题解了再去看一遍。
神 tm Adhoc。
考虑对于一个已经选好的路径，我们找到高度相差最大的两个点，显然有结论：在这俩点里转来转去肯定是比当前路径更优的。于是我们直接找到一对 ∣ h u − h v ∣ |h_u - h_v| ∣ h u − h v ∣ u , v u,v u , v ∣ h u − h v ∣ 2 \frac{|h_u - h_v|}{2} 2 ∣ h u − h v ∣
只能说我太蠢了。
自己想到了 75 % 75\% 75% 100 % 100\% 100%
想到之前考试有道题。设所有的数异或和为 s u m sum s u m s u m = 0 sum = 0 s u m = 0 s u m sum s u m n n n 1 1 1 1 1 1
考虑分类讨论，设有 c n t cnt c n t 1 1 1
有偶数数个 0 0 0 n n n
当 c n t ≡ 1 ( m o d 4 ) cnt \equiv 1 \pmod 4 c n t ≡ 1 ( mod 4 ) 1 1 1 1 1 1 当 c n t ≡ 3 ( m o d 4 ) cnt \equiv 3 \pmod 4 c n t ≡ 3 ( mod 4 ) 1 1 1 有奇数个 0 0 0 n n n
当 c n t ≡ 1 ( m o d 4 ) cnt \equiv 1 \pmod 4 c n t ≡ 1 ( mod 4 ) 当 c n t ≡ 3 ( m o d 4 ) cnt \equiv 3 \pmod 4 c n t ≡ 3 ( mod 4 ) 0 0 0 唐题。
我们考虑 dp。d p i dp_i d p i i i i d p i = d p i − 1 + ∑ d p j dp_i = dp_{i - 1} + \sum dp_j d p i = d p i − 1 + ∑ d p j j j j ( j , i ] (j,i] ( j , i ]
考虑如何快速求这个 ∑ d p j \sum dp_j ∑ d p j b e l i bel_i b e l i ( 视为 1 1 1 ) 视为 − 1 -1 − 1 s u m j sum_j s u m j b e l i = j bel_i = j b e l i = j d p i dp_i d p i ()()，第 3 3 3 1 1 1 )( 并不是一个合法的括号序列。我们考虑如何 ban 掉这种情况。
我们发现出现这种情况当且仅当有 k ∈ ( j , i ] k \in (j,i] k ∈ ( j , i ] b e l k < b e l i bel_k < bel_i b e l k < b e l i i i i b e l i bel_i b e l i b e l bel b e l l s t lst l s t [ 1 , b e l i − 1 ] [1,bel_i - 1] [ 1 , b e l i − 1 ] l s t lst l s t s u m b e l i sum_{bel_i} s u m b e l i d p i = d p i − 1 + s u m b e l i dp_i = dp_{i - 1} + sum_{bel_i} d p i = d p i − 1 + s u m b e l i i i i s u m b e l i sum_{bel_i} s u m b e l i d p i dp_i d p i
最后的答案就是 d p n dp_n d p n
还是 赛格门特吹 好用。
听 dpfs 讲的。
考虑 dp，设 d p i dp_i d p i i i i k k k
d p i = min { d p i − 1 + w i 直接删掉 i d p j − 1 + s u m w i − s u m w j − 1 + s u m c i − s u m c j + w j 不删 i dp_i = \min\begin{cases} dp_{i - 1} + w_i & \text{直接删掉 } i \\ dp_{j - 1} + sumw_i - sumw_{j - 1} + sumc_i - sumc_j + w_j & \text{不删 } i \end{cases} d p i = min { d p i − 1 + w i d p j − 1 + s u m w i − s u m w j − 1 + s u m c i − s u m c j + w j 直接删掉 i 不删 i 其中 s u m w i sumw_i s u m w i w w w s u m c i sumc_i s u m c i i i i [ j , i ] [j,i] [ j , i ] j j j s u m c j − w j sumc_j - w_j s u m c j − w j j j j [ j , i ] [j,i] [ j , i ] k k k
考虑优化。对于每个颜色开一个 m i n min min d p j − s u m w j − 1 − s u m c j + w j dp_j - sumw_{j - 1} - sumc_j + w_j d p j − s u m w j − 1 − s u m c j + w j k − 1 k - 1 k − 1 m i n min min d p i = min { d p i − 1 + w i , m i n c i + s u m w i + s u m c i } dp_i = \min\{dp_{i - 1} + w_i,min_{c_i} + sumw_i + sumc_i\} d p i = min { d p i − 1 + w i , mi n c i + s u m w i + s u m c i }
后日谈 明天的模拟赛和重庆八中联考。又可以丢 CW 的脸了。
每次一看到这个高达 16.7 % \color{#ff0000}16.7\% 16.7%
There’s no time left.
日记 1045 字 · 4 分钟
