Codeforces Round #884(Div. 1 + Div. 2) 題解（目前A~E，未完待續(xù))
CF1844A
題意
組數(shù)據(jù)，每組給定兩個整數(shù)
，兩個人從一個石堆中輪流取石子，每次恰好取
個或者
?個，不能完成取石子者輸。要求構(gòu)造一個后手必勝的石堆
?，要求
?，輸出石堆的石子數(shù)。
數(shù)據(jù)范圍： 。
題解
我寫了一個挺煩的做法：
如果輸入為 ?，輸出
?。
如果輸入為 ?，輸出
?。
否則輸出 ?，因為先手不能取式子，后手勝。
實際上只要輸出 ?即可。
代碼
CF1844B
題意
?組數(shù)據(jù)，每組給定一個正整數(shù)
?，要求構(gòu)造一個
?的排列，使得子區(qū)間
?為素數(shù)的子區(qū)間個數(shù)最多。
題解
?不是素數(shù)，所以要有貢獻，區(qū)間至少包含
?。不妨考慮把
?放在序列中間。
然后觀察到，如果一個區(qū)間不是素數(shù)，它要么不包含 ?，要么至少同時包含
?，所以把
?放在區(qū)間兩端，符合第二種條件的區(qū)間只有一個（全局）。（本質(zhì)是根據(jù) mex 大小分類討論）
代碼
題意
?組數(shù)據(jù)，每組數(shù)據(jù)給定一個長度為
?的數(shù)組
，規(guī)定操作為：選中一個位置
?，移去
?，若
?，移去
?和
?，并在原位置插入
?，求若干次操作之后只剩下一個數(shù)時，剩下的數(shù)最大能是多少。
數(shù)據(jù)范圍：?。
題解
性質(zhì)1：選中任意奇數(shù)長度的子區(qū)間，可以在不影響其它位置的情況下全部刪除。
性質(zhì)2：直接刪除端點若干次，可以不影響其它位置的情況下刪掉一個前綴，后綴同理。
性質(zhì)3：間隔一個奇數(shù)長度的子區(qū)間的兩個數(shù)可以合成一個數(shù)。
性質(zhì)4：考慮在刪掉一個前綴和一個后綴之后，從左起選擇若干個數(shù)，選擇的相鄰兩個數(shù)之間間隔一個長度為奇數(shù)的子區(qū)間，則這個選出來的子序列可以最終合成一個數(shù)。
根據(jù)性質(zhì)4，可以使用動態(tài)規(guī)劃思想求一個子序列，滿足任意相鄰兩個數(shù)間隔一個奇數(shù)長度的子區(qū)間，求子序列和的最大值。
設(shè) ?為選擇了
?的前綴的最大和的子序列大?。ㄩg隔滿足奇數(shù)），枚舉上一個選的數(shù)，有轉(zhuǎn)移方程：
由于取的只是最值，在遞推過程中，對于奇數(shù)序列和偶數(shù)序列，可以分別只保存一個歷史最值進行遞推。
單組數(shù)據(jù)時間復(fù)雜度 ?，空間復(fù)雜度
?。
代碼
題意
?組數(shù)據(jù)，每組給定一個正整數(shù)
?，要求構(gòu)造一個字典為全體小寫字母集合的字符串，滿足：按照順序重排到任意
?的矩陣（
）中后，矩陣中四相鄰的元素不相等。
數(shù)據(jù)范圍： ?。
題解
考慮 ?的所有約數(shù)
?，對每個位置
?有約束：
暴力求 ?的約數(shù)集合（
），從左往右考慮每個位置
?，考慮所有約數(shù)
?，排除所有位置
?已經(jīng)填放的字母，任取一個剩下的字母（不妨取最小）填充當(dāng)前位置
?。
由于 ?的約數(shù)個數(shù)是
?的，這個值在
?時期望遠小于字典大小
?，所以這個填法是正確的。
單組復(fù)雜度 ?。
代碼
CF1844E
題意
?組數(shù)據(jù)，給定一個
?的矩陣賦值
A, B, C 三種字母，并給定 ?條限制，每條形如”對某個
?的子矩陣，主對角線元素相同“或者”對某個
?的子矩陣，副對角線元素相同“，求是否有符合條件的賦值方式。
數(shù)據(jù)范圍：?。
題解
性質(zhì)：將每個 ?的小矩形的情況拼成一個
?的矩陣（以中心為參考），設(shè)主對角線相等為
?，副對角線相等為
??？紤]原矩陣中任意一個相鄰的
?的子矩陣中四個
?的子矩陣的情況：其中有偶數(shù)個
?和偶數(shù)個
?。也就是新矩形中任意一個
?的子矩陣中有偶數(shù)個
?和偶數(shù)個
?，也就是要么全都相等，要么有兩個
?和兩個
。
推論1：在新矩形中，任意一個子矩形的四個角的值有偶數(shù)個 ?和偶數(shù)個
?。
這個性質(zhì)和原推論等價。
證明：可以對新矩陣中的以
?的子矩形為單位進行數(shù)學(xué)歸納。
推論2：在新矩形中，任意兩行要么對應(yīng)列全相等，要么對應(yīng)列全相反。
這個性質(zhì)和原推論等價。
證明：
首先證明相鄰兩行的情況。任取一列，若它們相等：取其相鄰列，必然相等?？梢酝卣沟秸小?/p>
相鄰兩行要么全相等要么全相反，這是一種等價關(guān)系，可以向整個矩陣傳遞。
根據(jù)推論2，我們知道，所有行可以分為兩類，類內(nèi)兩行對應(yīng)列全相等，兩類各區(qū)一行對應(yīng)列全相反。
給定的約束其實就是規(guī)定了新矩形中某個位置必須填 ?或者某個位置必須填
?。那么對于同一列來說，若干個已經(jīng)填了的位置，其實約束了某兩行屬于同類或者不屬于同類。
那么可以用擴展域并查集來處理這些約束，看看結(jié)果是否矛盾。
代碼
