A

首先對(duì)于 A1 題，可以加減任意實(shí)數(shù)，結(jié)論是答案為 YES 當(dāng)且僅當(dāng)沒有度數(shù)為 \(2\) 的點(diǎn)。必要性顯然，充分性通過下面的構(gòu)造來證明。
A2 題的構(gòu)造：考慮隨便找一個(gè)葉子節(jié)點(diǎn)為根，記為 \(rt\)。則對(duì)于任何一個(gè)非根節(jié)點(diǎn) \(u\)，我們可以實(shí)現(xiàn)將根到該點(diǎn)的路徑上的邊權(quán) \(+w\)，其中 \(w\) 為任意偶數(shù)，其余邊權(quán)不變。如果 \(u\) 是葉子，那么直接執(zhí)行操作 \((rt,u,w)\)；否則 \(u\) 點(diǎn)子樹內(nèi)一定有兩個(gè)來自不同子樹的葉子，設(shè)為 \(v_1,v_2\)，則執(zhí)行 \((rt,v_1,\frac{w}{2}),(rt,v_2,\frac{w}{2}),(v_1,v_2,-\frac{w}{2})\). 那么我們直接自底而上每次計(jì)算出要新加的權(quán)值然后按這種方法構(gòu)造即可。
時(shí)間復(fù)雜度 \(O(n)\) 或 \(O(n^2)\)，操作次數(shù)不超過 \(3n\).
代碼: A1: 56571529 A2: 74629864

B

由于 \(\forall i,j, a_i-a_j\neq 0\)，原條件等價(jià)于 \((a_i-a_j)(a_i+a_j)(a_i^2+a_j^2)=a_i^4-a_j^4=k(a_i-a_j)\). 把 \((a_i^4-ka_i)\mod p\) 丟進(jìn) set 中即可。
時(shí)間復(fù)雜度 \(O(n\log p)\).
代碼: 74623487

C

首先對(duì) \(a_i\) 排序?？紤]對(duì)每個(gè) \(i\) 求出有多少個(gè)權(quán)值 \(\ge i\) 的子序列。直接設(shè) \(f[i][j]\) 表示長(zhǎng)度為 \(i\) 的序列末尾是 \(a_j\) 的方案數(shù)，前綴和轉(zhuǎn)移即可做到一次 DP 復(fù)雜度 \(O(nk)\)，那么總的復(fù)雜度就是 \(O(nk\max a_i)\).
考慮優(yōu)化，我們發(fā)現(xiàn)價(jià)值一定不超過 \(\frac{\max a_i}{k-1}\)，于是就做完了。
時(shí)間復(fù)雜度 \(O(n\max a_i)\).
代碼: 74622276

D

首先對(duì) \(a_i\) 排序并令 \(a'_i=\max^n_{j=1} a_j-a_i\). 目標(biāo)轉(zhuǎn)化為給所有的 \(a_i\) 同時(shí)加上一個(gè)數(shù) \(X\)，最小化所有數(shù) \(1\) 的數(shù)位個(gè)數(shù)總和。
考慮數(shù)位 DP，設(shè) \(f[i][j]\) 表示 \(X\) 的 \(0\) 至 \((i-1)\) 位是 \(j\)，這時(shí)發(fā)現(xiàn)只有一個(gè)后綴的 \(a_i\) 會(huì)發(fā)生進(jìn)位。于是把第二維改成前 \(j\) 小的數(shù)不會(huì)發(fā)生進(jìn)位 (后面的數(shù)會(huì)發(fā)生進(jìn)位)，轉(zhuǎn)移分類討論一下，發(fā)現(xiàn)只需要把所有數(shù)按 \(\mod 2^{i+1}\) 的值排序然后求出每個(gè)前綴內(nèi)有多少個(gè)第 \(i\) 位為 \(1\) 的數(shù)就可以做到 \(O(1)\) 轉(zhuǎn)移。應(yīng)該可以用歸并排序優(yōu)化復(fù)雜度。
時(shí)間復(fù)雜度 \(O(n\log n\log W)\) (\(W=\max a_i\)) 或 \(O(n\log W)\).
代碼: 74606189

E

題解: https://www.cnblogs.com/suncongbo/p/12591476.html

總結(jié)

以上是生活随笔為你收集整理的Codeforces 1188 题解的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。