A

假設(shè)所有的 \((i+a_i)\) 模 \(n\) 意義下構(gòu)成排列則答案為 YES，否則為 NO.
時間復(fù)雜度 \(O(n)\) 或 \(O(n\log n)\).
代碼: 79150268

B

由于每行每列必須有至少一個 S，所以每行每列為 # 的格子要么構(gòu)成一個連續(xù)區(qū)間要么不存在。
如果某行或列不存在 #，則該行或列的格子必須放在一個不存在 # 的列或行。
于是得到了有解的必要條件：(1) 每行每列 # 的格子要么不存在要么構(gòu)成連續(xù)區(qū)間；(2) “存在一行無 #”和“存在一列無 #”二者要么同時滿足要么同時不滿足。
充分性：每個連通塊全放 S，再隨便一個位置放 N，顯然最優(yōu)。
時間復(fù)雜度 \(O(nm\alpha(nm))\).
代碼: 79341530

C

首先按大小關(guān)系建圖，拓撲排序，有解當(dāng)且僅當(dāng)無環(huán)（全放 \(\exists\) 即可）。
對于一個 \(x_i\) 而言，顯然如果有 \(j\gt i\) 且 \(i,j\) 之間有大小關(guān)系（即存在一條路徑從 \(i\) 到 \(j\) 或從 \(j\) 到 \(i\)），那么 \(j\) 不可以是 \(\forall\).
于是對每個點統(tǒng)計一下能到它的和它能到的點中編號最小的，如果大于它本身就可以是 \(\forall\)，否則設(shè)為 \(\exists\)，這樣的方案是最優(yōu)的。
而這保證了每個 \(\forall\) 是所有和它限制了大小關(guān)系的點中編號最小的，因此一定能構(gòu)造合法解。
時間復(fù)雜度 \(O(n+m)\).
代碼: 79198382

D

由于貢獻關(guān)于 \(b_i\) 是凸的（\(f(b_i+1)-f(b_i)\) 隨 \(b_i\) 的上升而下降），所以可以考慮這樣一個過程：初始時 \(b_i\) 都是 \(0\)，進行 \(K\) 輪，每一輪選擇當(dāng)前 \(b_i\lt a_i\) 且 \(\Delta(b_i)=f(b_i+1)-f(b_i)\) 最大的 \(i\)，把 \(b_i\) 加一。
考慮優(yōu)化：每次選擇的 \(\Delta\) 單調(diào)不升，因此可以二分最終結(jié)束時的 \(\Delta\)，判斷加的輪數(shù)是否 \(\ge K\) 即可。注意二分邊界，有可能 \(\Delta=x\) 的時候個數(shù) \(\lt K\)，\(\Delta=x-1\) 的時候個數(shù) \(\gt K\)，這時候隨便調(diào)整一下即可。
時間復(fù)雜度 \(O(n\log W)\).
代碼: 79350373

E

不難發(fā)現(xiàn)限制形如“在區(qū)間 \([l_i,r_i]\) 中要操作一次 \(u_i\)”. 假設(shè)我們提取出所有的限制（共 \(S\) 個），就可以在 \(O(S\log n)\) 的時間內(nèi)得到答案——用一個優(yōu)先隊列維護，每次時間后推，把所有 $l\le $ 當(dāng)前時間的加入優(yōu)先隊列，然后刪去 \(r\) 最小的。
由 LCT 的經(jīng)典分析可知有用的限制總數(shù)是 \(O(n+m\log n)\) 級別。考慮用 LCT 提取出這些限制。
每一次 access 時，當(dāng)輕重邊切換的時候更新切換的點的限制列表，拉成同一棵 Splay 之后打一個標(biāo)記，表示這些點最后一次被 access 的時間。
注意細節(jié)問題。無論重邊切換成什么（即便是 \(0\)）都要加到列表里，最后對列表進行處理，去掉 \(0\)，合并相鄰相同的。典型錯誤做法是如果切換成 \(0\) 則不加入列表，這樣會導(dǎo)致后面的區(qū)間的 \(l\) 變大。
時間復(fù)雜度 \(O(n\log n+m\log^2 n)\).
代碼: 79797116

F

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

總結(jié)

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

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