1. CF487C Prefix Product Sequence

#構造 #數列 #乘法逆元

簡要題意

是否存在一個長度為 \(n\) 的排列，使得其前綴積在\(\mod n\) 意義下兩兩不同？
如果存在，輸出 \(YES\) 并且換行輸出一個構造的排列；
如果不存在，輸出 \(NO\)。
\(1\le n\le 10^5\)

思路

首先判斷對于每個 \(n\) 是否有解。

我們可以發現對于 4 和質數 總是有解的，而對于其它數總是無解的，因為對于其它數，一定有多個小于它的且不同的數的乘積為它的倍數，而這是前綴積，這樣就會有多個前綴積 \(\mod n\) 后為 \(0\) 。也不能把它們放在最后，因為 \(n\) 在前面也會發生同樣的情況。

然后考慮如何進行構造，首先 \(1\) 應該在最前，因為它放在后面會使兩個前綴積相等，\(n\) 應該在最后，理由在判斷是否時已經說了。

中間我們可以用一個特殊的方法 \(\frac{2}{1} \ ,\ \frac{3}{2} \ ,\ \frac{4}{3} \ ,\ ... \ ,\ \frac{n}{n-1}\) ，這樣前綴積數組就會是 \(1,2,3,4,5,...,0\)，然后求分母的逆元即可。

然后我們來證明中間的數是否可能相等，即在 \(\mod n\) 意義下存在 \(\frac{i+1}{i}=\frac{j+1}{j} \ (1\le i\lt j\lt n)\)。

與 \(i\lt j\) 矛盾，所以中間的數不可能相等，完成。

時間復雜度 \(O(n\log_2 n)\) 或 \(O(n)\)（線性遞推逆元的話）

2. CF1406E Deleting Numbers

#交互題 #構造 #唯一分解定理

簡要題意

在一個序列里存在整數 \(1\) ~ \(n \ (1\le n\le 10^5)\)。有一個特殊的數\(x \ (1\le x\le n)\) 你需要找出這個數，你有三種操作。

\(A \ a\) 表示詢問序列中為 \(a\) 的倍數的數的個數。
\(B \ a\) 表示詢問序列中為 \(a\) 的倍數的數的個數并刪除它們 \(x不會被刪除\) 。
\(C \ a\) 表示答案為 \(a\) 。

你可以詢問不超過 \(10^4\) 次，確定 \(x\) 是什么。

思路

根據唯一分解定理，如果我們知道 \(x\) 的所有質因子，我們就可以通過操作 \(B\) 枚舉質因子的冪次來快速求出 \(x\) 。

因為 \(2*3*5*7*11*13*17=510510\) 所以 \(x\) 最多有 \(6\) 個不同的質因子 ，\(2^{17}=131072\) ,所以 \(x\) 的質因子冪次不會超過 \(16\)。

所以我們如果知道 \(x\) 的質因子有哪些，就可以用不超過 \(16\) 次的次數求解出 \(x\) 。

那么我們如何找出 \(x\) 的所有質因子呢？

暴力的做法是對于每一個質數都先進行一次 \(B\) 操作，再進行一次 \(A\) 操作如果還能夠找到數說明這就是 \(x\) 的質因子。

但 \(10^5\) 內的質數一共有 \(9600\) 多個，每個都這樣做就有接近 \(20000\) 次，不符合題目要求，所以我們考慮如何減少查詢次數。

我們發現嚴重的浪費出現在 \(A\) 操作上，考慮是否可以代替。

我們發現如果前面都使用 \(B\) 操作的話，那么不考慮 \(x\) ，每個質數進行 \(B\) 操作時刪除的個數是一定的（每個數都是被它的最小質因子刪除的），那么如果個數與預處理的不一樣，就說明出現了 \(x\)，此時將這個質數記錄下來即可。

但是我們如果這樣做的話會有一個問題，那就是我們無法知道 \(x\) 的最小質因子，因為那是 \(x\) 第一次被刪，于是我們需要單獨求出 \(x\) 的最小質因子，我們現在還剩大概 \(300\) 次操作。

考慮如何判斷 \(x\) 的最小質因子是否出現，用 \(A \ 1\) 可以求出當前序列中還剩多少個數，記錄一下應該刪除了多少個數，如果與剩下的數的個數加起來不為 \(n\) 說明 \(x\) 的最小質因子已經出現，此時對之前篩過的質數每個進行一次 \(A\) 操作即可找出 \(x\) 的最小質因子，那么消耗的次數是 塊數+塊長 的，此時，將塊長取到 \(\sqrt{cnt} \ (cnt 為質數個數)\) 最優。

總消耗次數大概為 \(cnt+2\times \sqrt{cnt}+16\) 次，不會超過 \(10^4\)。
時間復雜度 \(O(n+cnt)\)

3. CF521D shop

#貪心

簡要題意

一個長度為 \(n\) 的序列 \(A\)，你有 \(m\) 個操作，每個形如 \(t,i,b\)。

若 \(t=1\) 表示將 \(A_i\) 賦值為 \(b\)，\(t=2\) 表示將 \(A_i\) 賦值為 \(A_i+b\)，\(t=3\) 表示將 \(A_i\) 賦值為 \(A_i\times b\)。

你需要選擇最多 \(k\) 個操作，并按一定順序進行使得 \(\prod_{i=1}^{n} A_i\) 值最大。

輸出你選擇了多少個操作并且按操作順序輸出你選擇的操作編號。

\(1\le n\le 10^5,1\le k\le m\le 10^5\)

思路

首先我們發現，如果只有 \(t=3\) 的操作，直接排序，貪心的選擇最大的 \(k\) 個即可。

然后我們考慮如何擴展到加法和賦值操作上。

假定我們已經選好了 \(k\) 個操作，如何操作使得最終值最大，對于每個 \(A_i\) 的操作，我們一定是先賦值，再加，最后乘可以讓它最大。

而對于每個 \(A_i\) 的加法，我們一定是按照從大往小進行選擇的，所以我們選擇對于 \(A_i\) 的第 \(j\) 個加法的前提就是前 \(j-1\) 個加法均已被選擇，那么我們就可以知道選擇第 \(j\) 個加法時，當前 \(A_i\) 的值為多少，那么對于每個加法，我們均可以將它改寫為乘法的形式，如 \(a+b\Rightarrow a\times \frac{a+b}{a}\)。那么我們就可以將其放入乘法的序列中進行貪心的選擇。

最后我們剩下一個賦值操作，我們肯定最多對每個數賦值一次且是選擇最大的數進行賦值，那么我們只需保留對于每個 \(A_i\) 最大的賦值操作，并且由于我們的賦值操作是在最初進行的，所以本質上是將 \(A_i\) 加上一個數，我們可以將它改寫成加法，如 \(a\to b \Rightarrow a+(a-b)\)，直接扔進加法操作種排序即可。

到此我們已經完成了加法和賦值操作的轉換，直接貪心的選前 \(k\) 個即可。

這里記錄一下思考時遇到的一個小問題，就是我們要求的是賦值操作在最開始進行，而將它變成加法排序后，它不一定是最大的加法也就是它不一定第一個操作，那么我們還可以保證算法的正確性嗎？

答案是可以的，因為最后轉為乘法后可以打亂操作順序，我們仍可以將賦值操作提到第一個進行操作，舉個栗子。

設原數為 \(x\) 賦值操作為 \(x\to y\)，有加法操作 \(z_1 \ge z_2\ge ...\ge z_a \ge y-x \ge z_{a+1}\ge z_{a+2} \ge ...\ge z_b\)

那么我們最終轉為乘法操作的乘積為 \(\frac{y+\sum_{i=1}^b z_i}{x}\)，無論怎么改變順序答案不變。

4. CF1481F AB Tree

#多重背包DP

簡要題意

一棵 \(n\) 個節點的樹，你需要往 \(x\) 個節點上的填一種字符，往剩下 \(n-x\) 個節點上的另一個字符，每個節點的字符串為根到它路徑上節點的字符所組成的字符串。
問你如何填字符，使得 \(n\) 個節點的不同字符串的數量最少。

\(1\le n\le 10^5,0\le x\le n\)

思路

首先我們很明顯可以發現答案至少為樹的高度。
此時把我們樹按高度進行分層，考慮最優策略如何讓答案為樹的高度。

可以發現每一層的節點都會被給到相同的字符。

但這需要有幾層的 \(size\) 之和為其中一種字符的數量，我們不可能每次都遇上這種條件，這只是答案的下界。

所以考慮沒有幾層的 \(size\) 之和為其中一種字符的數量時，我們應該怎么辦。

題目中子節點的字符由父節點進行提供，那么一旦其中一層有孩子的節點所擁有的字符不同，那么它傳下去之后會讓答案以幾何倍數增長。

我們貪心的想，肯定優先滿足這些有孩子的節點，而一棵樹中同一層有孩子的節點只會有 \(\lfloor \frac{n}{2} \rfloor\) 個，完全可以滿足。

具體的，現在已經填好了第 \(i\) 層，準備填 \(i+1\) 層，未填節點一共有 \(size\) 個，會有孩子的節點最多有 \(\lfloor \frac{size}{2} \rfloor\) 個，\(a,b\) 中一定有一個剩余數量 \(\ge \lfloor \frac{size}{2} \rfloor\)，所以可以先把非葉子節點賦上相同的字符，如果可以覆蓋整層就覆蓋。

覆蓋不了就說明有一種字符已經被用完，用另一種字符賦給剩下所有節點，不會給再造成任何額外的貢獻，那么只有這一層葉子節點與非葉子節點不同，答案增加 \(1\)，所以答案上界為樹高加 \(1\) 。

判斷用背包DP（裝入對象為每層 \(size\)）解決。
然而，\(n\le 10^5\)，樸素的01背包會T飛，考慮對DP進行優化。
我們可以發現每層 \(size\) 會有大量重復，可以用多重背包二進制優化進行求解。
分析時間復雜度，發現最劣情況下，\((1+2+3+4+5+...+x)=\frac{x(x+1)}{2}=n\)，\(x\) 為 \(\sqrt n\) 級，有 \(x\) 個物品，所以它的時間復雜度最劣大概是 \(O(n \sqrt n )\) ;
題目還要要求輸出方案，在 DP 過程中記錄決策方案，在記錄有多少大小為 \(x\) 的層，進行染色。

5. CF878E Numbers on the blackboard

#貪心

簡要題意

一個長度為 \(n\) 的序列 \(a\)，你每次可以選擇 \(\forall i(1\le i\lt n)\) 將 \(a_i\) 和 \(a_{i+1}\) 變為 \(a_i+2\times a_{i+1}\)，注意是刪除 \(a_i\) 和 \(a_{i+1}\) 后在它們原有的位置中插入一個數。
\(q\) 次詢問，每次問 \(l_i\) 到 \(r_i\) 的數能組成的最大值，對 \(10^9+7\) 取模。

\(1\le n,q\le 10^5,-10^9\le a_i\le 10^9,1\le l_i\le r_i\le n\)

思路

我們發現只有兩種不同的操作方式，從左往右合并一段區間和從右往左合并一段區間。
分別考慮兩種方式對答案的貢獻。

從左往右
對于形容 \(x_1,x_2,x_3,...,x_{len}\) 的序列每次選擇開頭的數與后一個數合并，最后對答案的貢獻就是 $$1\times x_1+\sum_{i=2}^{len} 2\times x_i$$
從右往左
對于形容 \(x_1,x_2,x_3,...,x_{len}\) 的序列每次選擇末尾的數與前一個數合并，最后對答案的貢獻就是 $$\sum_{i=1}^{len} 2^{i-1} \times x_i$$
于是我們發現原序列中的每個數最后對答案的貢獻為 \(2^k (1\le k\lt n)\) 次，貪心的考慮讓正數的系數盡可能的大，負數的系數盡可能小，而我們發現從左往右的合并方式只能用于合并 \(len\) 個數，沒有辦法進行貪心，所以我們考慮先從右往左將原序列合并成若干個塊，最后從左往右合并為一個數。

而從右往左將原序列合并成若干個塊的過程中，對于一個塊中的數有 \(k_i=k_{i-1}+1 (k_1=0)\)

一個明顯的貪心是遇到正數就將它加入已有塊，遇到負數就單獨開一個塊儲存，但是一個簡單的樣例即可卡掉這個貪心，如 \(11,11,11,-3,11\) 最優的應該是將它分為 \(1\) 塊，而這個貪心策略會把它分成\(3\) 塊，我們考慮為什么會出現這種情況。

發現只要當前塊貢獻是正數，就可以向前一個塊合并，因為這樣這個塊的貢獻就被放大了 \(2^{l}\)，\(l\) 為前一個塊的塊長，而前一個塊的系數并沒有改變無論是正數還是負數，且它就算是合并到了第一個塊沒有了最后從左往右合并的 \(2\) 的倍數，因為 \(l\ge 1\)，這是不劣的。所以我們有了一個貪心策略，如果當前塊貢獻為正，向前合并直到貢獻為負或只剩一個塊。

這里需要注意一下，如果序列是全正數，合并幾次就會到達 long long 上限，而我們發現每個塊最小為 \(-10^9\)（就是 \(a_i\) 最小的情況，不與其它塊合并。而我們合并每個塊是將后一個塊 \(\times 2^l\) 加上前一個塊，而 \(l\) 最小是 \(1\)，所以如果一個塊的大小超過了 \(10^9\)，它就一定可以合并到第一個塊，直接賦值為 \(+ \infty\)，計算時特判即可。

那么現在我們將原始的序列合并為了若干個塊，需要用從左往右的方式將它合并為 \(1\) 個塊，然而，我們每次詢問 \(l_i\)~\(r_i\) 并不一定是整塊，需要單獨處理左右的散塊，可以將詢問離線下來，按 \(r_i\) 從小到大排序，每次處理到 \(r_i\)，中間的整塊和右邊的散塊用前綴和優化一下，左邊的散塊單獨拆開，可以用類似 \(hash\) 提取字段和的方式提取一個后綴，不要忘了中間的整塊和右邊的散塊合并時有一個而的倍數。

時間復雜度 \(O(n\log_2 n)\)