簡(jiǎn)單dp

A

首先枚舉時(shí)間 \(t\)，\(t\in[0,\max b_i-\min a_i]\)，然后對(duì)于每個(gè)人 \(i\) 可以求出一個(gè)行李的范圍，這個(gè)范圍的行李滿足：這些行李到達(dá) \(b_i\) 的時(shí)候，時(shí)間都大于等于 \(t\)

然后不難發(fā)現(xiàn)一個(gè)單調(diào)性：

如果把人按照位置從小到大排序，那么后面的人的范圍肯定包含前面的人的范圍

因此考慮對(duì)于人從前往后 dp ，令 \(f[i][j]\) 表示前 \(i\) 個(gè)人選擇了 \(j\) 個(gè)行李的方案數(shù)，假如對(duì)于第 \(i\) 個(gè)人而言，有 \(g[i]\) 個(gè)行李可能夠到他，那么就有轉(zhuǎn)移：

C

首先確定一下策略：

對(duì)于一個(gè)人 \(i\)，會(huì)選定一個(gè) \(j\)，然后把 \(j\) 左邊的都往左一個(gè)一個(gè)地合并到 \(i\) ，右邊同理

然后不難注意到一個(gè)性質(zhì)：

性質(zhì)1：

對(duì)于每個(gè) \(i\) 從左/右合并過來的值至多有 \(\log\) 個(gè)

所以記 \(l[i][j],r[i][j]\) 表示 \(i\) 從左/右合并過來的能夠達(dá)到第 \(j\) 個(gè)值的最靠左/右的位置是多少，然后進(jìn)行二分即可。時(shí)間復(fù)雜度為 \(O(n\log^2n)\)

B

這個(gè)題手玩一下可以注意到一個(gè)性質(zhì)

性質(zhì)1：

如果將首尾相接的節(jié)目看成一個(gè)個(gè)塊，那么最優(yōu)策略中則存在某一種將一個(gè)個(gè)塊再進(jìn)行割分的方式，使得割分完的每個(gè)塊要么起始位置踩在關(guān)鍵點(diǎn)上，要么結(jié)尾位置踩在關(guān)鍵點(diǎn)上

然后樸素的狀壓dp即可

D

考慮二進(jìn)制下的比較，先通過操作把 \(a\oplus b \ge k\) 轉(zhuǎn)化為 \(a\oplus b > k\)

那么意味著至少存在一位使得 \(a\oplus b\) 與 \(k\) 是不同的

然后考慮在 \(trie\) 進(jìn)行樹上背包，為保證不重不漏，我們欽定每一個(gè)匹配在第一位與 \(k\) 不同的那個(gè)位置被計(jì)算即可，所以有狀態(tài) \(f[i][j]\) 表示以 \(i\) 為根的樹里，已經(jīng)（用掉 \(j\) 個(gè) \(a\) 來）和 （（（與 \(i\) 配對(duì)的那個(gè)點(diǎn) \(lnk[i]\) ）的子樹里）的 \(j\) 個(gè) \(b\) ）進(jìn)行匹配的方案數(shù)，然后樸素轉(zhuǎn)移即可

E

首先注意到這個(gè)解的結(jié)構(gòu)，就是分成上下兩個(gè)部分

然后從前往后dp的過程中維護(hù)一個(gè)相對(duì)大小的順序，每次加入數(shù)字的時(shí)候就是把元素插入到這個(gè)相對(duì)大小中即可。具體的，令 \(f[i][j]\) 表示前 \(i\) 個(gè)值里，上面的元素有 \(j\) 個(gè)，下面的元素有 \(i-j\) 個(gè)的情形下，逆序?qū)ψ疃嗍嵌嗌?/p>

不過還需要判斷有無交集，需要使用一個(gè)并查集來處理，時(shí)間復(fù)雜度為 \(O(n^2)\)

F

注意到性質(zhì)：

性質(zhì)1：

你操作不會(huì)超過 \(\log\) 次

性質(zhì)2：

你操作的范圍一定是在笛卡爾樹上的

所以放在笛卡爾樹上進(jìn)行dp即可，令 \(dp[i][j]\) 表示在以 \(i\) 為根的子樹里使用了 \(j\) 次操作后，序列中最大值的最小值是多少，然后進(jìn)行樸素的轉(zhuǎn)移即可，時(shí)間復(fù)雜度 \(O(n\log^2 n)\)

G

神奇亂搞題

H

簡(jiǎn)單題，你只需要注意到序列 \(s\) 滿足以下條件

(1) \(s\) 的最大值要么在最左邊要么在最右邊

(2) \(s\) 只有一個(gè)最大值

(3) \(s\) 去掉最大值得到的序列 \(s'\) 也是好的

因?yàn)槭聦?shí)上 \(f(i)\not = f(j)\iff f(i)>f(j),i>j\)

所以從大往小dp即可，具體的，令 \(dp[i][j]\) 表示目前最小值為 \(i\) 且最大公因數(shù)為 \(j\) 的序列數(shù)量，然后動(dòng)態(tài)維護(hù)一下前綴和：\(sum[x]=\sum_{i}dp[i][x]\)

考慮轉(zhuǎn)移：

對(duì)于 \(i\) 枚舉加入 \(i\) 后最大公因數(shù)變成了 \(d\) ，這個(gè)時(shí)候需要求出 \(\sum_{\gcd(x,i)=d}sum[x]\)

直接枚舉會(huì)爆掉，但是注意到 \(x\) 是 \(d\) 的倍數(shù)，因此可以把 \(sum[x]\) 改為 \(\sum_{\substack{i\\x|y}}dp[i][y]\)

但是這樣求出來的只能保證最大公因數(shù)是 \(d\) 的倍數(shù)，所以可以考慮像前幾天講的一樣，拿莫反處理一下就行了

所以時(shí)間復(fù)雜度是

可以通過本題

I

不難發(fā)現(xiàn)其實(shí)第 \(i\) 位的一個(gè)芯片就相當(dāng)于第一個(gè)位置的 \(fib[i]\) 個(gè)芯片，其中 \(fib[i]\) 表示斐波那契數(shù)列的第 \(i\) 項(xiàng)，所以考慮一個(gè)過程：把所有的位置的芯片都轉(zhuǎn)移到 \(1\) 上，再重新分配，所以假如第 \(i\) 個(gè)位置上有 \(x_i\) 個(gè)芯片，那么如果 \(\sum x_i\cdot fib[i]\) 相等，那么答案相等

所以考慮實(shí)際上累加到第一位的總和不會(huì)超過 \(n\cdot fib[10]\le 90000\) ，所以只需要對(duì)每一種可能的總和進(jìn)行 \(dp\) 即可，這是一個(gè)完全計(jì)數(shù)背包

另外一方面，還需要計(jì)算每一種可能的總和的成本是多少，這個(gè)也可以使用 \(dp\) 來完成，具體的，令 \(cost[i]\) 表示總和為 \(i\) 時(shí)的成本是多少，那么有

J

我知道有人是拿 \(O(1024n)\) 通過的，但是其實(shí)有更優(yōu)美的解法

考慮 \(x^2\) 有什么意義，可以將 \(x\) 進(jìn)行二進(jìn)制拆分，假如 \(x=\sum_{i=0}^9bit[i]\cdot 2^i\)

那么 \(x^2=\sum_{i=0}^9\sum_{j=0}^9bit[i]\cdot bit[j]\cdot 2^{i+j}\) ，考慮對(duì)于每個(gè)有序?qū)?\((i,j)\) 統(tǒng)計(jì)其期望的貢獻(xiàn)即可，

這是因?yàn)橐驗(yàn)?\(\mathbb E(\sum_{i=0}^9\sum_{j=0}^9bit[i]\cdot bit[j]\cdot 2^{i+j})=\sum_{i=0}^9\sum_{j=0}^9\mathbb E(bit[i]\cdot bit[j])\cdot 2^{i+j}\)?

所以實(shí)際上的時(shí)間復(fù)雜度為 \(O(n\log ^2V)\)

K

對(duì)于除了第一行的每一行而言，第一位玩家不能有剩余，就是如果給每一行賦值 \(+1/-1\) 其中 \(-1\) 代表二號(hào)玩家的牌，\(+1\) 代表一號(hào)玩家的牌，那么每一行的每一個(gè)前綴和均不小于 \(0\) ，然后第一行的情況恰好相反，同時(shí)，還要記錄一下除了第一行外其余的行第一位玩家欠了第二位玩家多少個(gè)卡，然后在第一行一起算上

M - 神奇的貪心dp

首先二分答案，然后把每個(gè)元素轉(zhuǎn)換成 \(0/1\)

然后題目就是要求每次去掉連續(xù)的 \(k\) 個(gè)，實(shí)際上我希望去掉的 \(0\) 盡可能多，所以我令 \(f[i]\) 表示 \(1\sim i\) 至多能去掉多少個(gè) \(0\) ，\(g[i]\) 表示 \(i\sim n\) 至多能去掉多少個(gè) \(0\) ，然后通過前綴和優(yōu)化進(jìn)行樸素的 \(dp\) 轉(zhuǎn)移即可

關(guān)于正確性：

這個(gè) \(dp\) 狀態(tài)里并沒有保證選的塊的個(gè)數(shù)，但是事實(shí)上由于 \(f[i],g[i]\) 都是最優(yōu)的，所以不可能會(huì)允許存在 \(\ge k\) 個(gè)位置是沒選到的，也就是說 \(f[i],g[i]\) 的最優(yōu)性天然保證了能去掉足夠多塊

至于為什么要兩個(gè)數(shù)組，這是因?yàn)樾枰幚?\(k|n\) 的情形，要保留 \(k\) 個(gè)不選，就意味著至少存在一個(gè)位置是沒選到的，所以答案是 \(\max_{1\le i\le n}\{f[i-1]+g[i+1]\}\)