11.18

• 下午和晚上都要被拉去上文化課（
• dmy DAY5 T2

• 我們可以把 \(a,b\) 的詢問看成一條鏈上掛着一些子樹，通過 \(d_a\) 和 \(d_b\) 的差我們能夠求出 \(x\)

• dmy DAY8 T1

• 可以把 \(f()\) 操作看成 \(x \oplus y = sum\) 的情況下使得 \(x + y\) 儘可能大，故我們可以逐位考慮，若 \(sum\) 這位上為1則無所謂，如果為0的話要麼是兩個1要麼是兩個0，考慮1的情況是否出現，故我們可以得到一個 \(???1??1??\) 的二進制數，考慮它在前面有沒有出現，故我們加入 \(a_i\) 的時候就加入 \(sum_i\)

11.19

• P7406 DP,發現性質題目
• 首先我看出了 \(a_i < a_{i+1}+2\) 可以化為 \(a_i <= a_{i+1}+1\)
• 然後我稍一推導便發現這是從小到大依次放入的，故設 \(f_i\) 為 \([1,i]\) 都放入序列中了的最小代價，定義 \(g_{l,r}\) 為把 \(l-r\) 放入 \([l,r]\)
• \(f_i = \min_{f_j + g_{j+1,i}}\)
• 問題轉化為 \(g_{l,r}\) 該如何求取

• 可以發現 \([1,l-1]\) 已經歸位無需考慮，則我們發現這就是 \(l-r\) 和 \(r+1-n\) 的逆序對個數加上 \(l-r\) 和 \(l-r\)

• P3188 揹包DP，二進制拆位

• 其實是一道很經典的板子拆位題但是我沒做過
• 考慮 \(a \cdot 2^b(a<=10)\)
• 故我們定義 \(f_{i,j}\) 表示在第 \(i\) 位可以選 \(j\) 個 \(1<<i\)
• 如何把第 \(i\) 位與前 \(i-1\) 位拼起來，換句話説如何把 \(i-1\) 位轉到第 \(i\)
• 考慮 \(i\) 位的選數無法對前 \(i-1\) 造成影響，故我們可以考慮 \(w\) 這個東西的前 \(i-1\) 位上的權值儘量選滿，故前 \(i-1\) 位轉移到第 \(i\) 位即為，定義 \(g_{i,j}\) 表示前 \(i\) 位，在第 \(i\) 位上用了 \(j\) 個 \(1<<j\)
• g_{i,j} = max(f_{i,p} + g_{i-1,2*(j-p)+(w>>(i-1) & 1)})
• 轉移即可

• p6554

• 換根DP板題啊/cg，怎麼還是藍（

• P5664

• 首先我想到了容斥，我也想到了要枚舉最多的去DP轉移，但是！我甚至想到了去維護總數與最大數量級的數量關係，但是我沒想到可以維護最大數數量與其他數之和的差！
• 在類似於最大值不能/要超過總數一半的DP問題中，我們可以考慮維護最大值和其他數之和的差
• 之前我應該是見過類似的trick的但是十分久遠，以至於我發散思維想了20min左右都沒想到此題這麼板的解法/jk