本文主要是介绍【24.2】【24.3】,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
题目
【题解】2024牛客寒假算法基础集训营2
【题解】2024牛客寒假算法基础集训营3
Tokitsukaze and Slash Draw
思路:同于最短路板子题。在这道题学习了一下新的方法,时间复杂度优化了一个 log 且代码不再使用最短路算法使其更短。时间复杂度 O ( n × m ) O(n\times m) O(n×m) 。
博客:同余最短路的转圈技巧
AC代码:https://www.luogu.com.cn/paste/20a8rsrz
Tokitsukaze and Power Battle (easy)
思路:我开始的思路是把序列左移一位然后维护 p r e i − a i + 1 pre_i-a_{i+1} prei−ai+1 和 p r e i pre_i prei ,但这样应该比较麻烦。题解的思路是直接查询 s u m ( l , r ) − 2 × a r sum(l, r) - 2\times a_r sum(l,r)−2×ar 。用线段树维护 p r e i − 2 × a i pre_i - 2\times a_i prei−2×ai ,用树状数组维护 p r e i pre_i prei 即可。
hard版本是区间最大子段和的类似版,但写起来很麻烦。
AC代码:https://www.luogu.com.cn/paste/qs6ymoe6
Tokitsukaze and Min-Max XOR
思路:这题思路和上一场的01背包比较像。先套路的排序,然后枚举序列右端点,查询前缀中有哪些元素异或起来小于等于 k。
接下来,考虑 ≤ k \leq k ≤k 这个条件,可以将其拆分为若干个区间(类似上场01背包),比如 x = 100110 x=100110 x=100110 ,拆分为 [ 100110 → 100110 ] , [ 100101 → 100100 ] , [ 100011 → 100000 ] , [ 0111111 → 000000 ] [100110\rightarrow100110],[100101\rightarrow100100],[100011\rightarrow100000],[0111111\rightarrow000000] [100110→100110],[100101→100100],[100011→100000],[0111111→000000] 。那么每个区间都有连续若干长度的最低位是可以任意的,那么区间可以表示为 [ 100110 ] , [ 1001 ( 0 ) ? ] , [ 100 ( 0 ) ? ? ] , [ ( 0 ) ? ? ? ? ? ] [100110],[1001(0)?],[100(0)??],[(0)?????] [100110],[1001(0)?],[100(0)??],[(0)?????] ,括号表示枚举的是哪一位,然后用 01trie 查询即可。
AC代码:https://www.luogu.com.cn/paste/jw2uul96
智乃的“黑红树”
思路:分层 bfs。之前也做过类似的题。
AC代码:https://www.luogu.com.cn/paste/nfg4lnll
智乃的相亲活动
思路:期望的线性性: E ( x + y ) = E ( x ) + E ( y ) E(x+y)=E(x)+E(y) E(x+y)=E(x)+E(y) ,与独立性无关。
另: E ( x y ) = E ( x ) × E ( y ) E(xy)=E(x)\times E(y) E(xy)=E(x)×E(y) ,当且仅当两者独立。
AC代码:https://www.luogu.com.cn/paste/vll4areq
chino’s bubble sort and maximum subarray sum(hard version)
思路:考虑获得最大子段和的过程:若干个元素右移,若干个元素左移,且两者之间是前者在左后者在右,有分界点。然后这样的话,可以考虑维护每一个前缀和后缀的相关值。
定义 d p ( i , j , k ) dp(i, j, k) dp(i,j,k) 表示前缀 i i i 中,最终参与到最大子段和的长度为 j j j ,且交换次数恰好为 k k k 。如果 a i a_i ai 参与到最大子段,那么不需要交换出 ( i − j , i ] (i-j,i] (i−j,i] 这个区间,即从 d p ( i − 1 , j − 1 , k ) dp(i-1,j-1,k) dp(i−1,j−1,k) 转移。否则,需要交换出去,交换次数为 j j j ,且将 ( i − 1 − j , i − 1 ] (i-1-j,i-1] (i−1−j,i−1] 这个区间交换到了 ( i − j , i − 1 ] (i-j,i-1] (i−j,i−1] ,即从 d p ( i − 1 , j , k − j ) dp(i-1,j,k-j) dp(i−1,j,k−j) 转移。
最后统计答案的步骤比较麻烦,没写出来。
未AC代码:https://www.luogu.com.cn/paste/4wiq21n8
这篇关于【24.2】【24.3】的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!