Codeforces 补题记录
首先總結(jié)一下前段時(shí)間遇到過的一些有意思的題。
Round #474 (Div. 1 + Div. 2, combined)? ?Problem G
其實(shí)關(guān)鍵就是n這個(gè)數(shù)在排列中的位置。
這樣對于一個(gè)排列，設(shè)$f[pos] = p$， 那么從位置$1$到位置$pos$最大值被刷新了$a$次，從位置$n$到位置$pos$最大值被刷新了$b$次。
去掉$n$之后，剩下$n-1$個(gè)數(shù)被分成了兩個(gè)部分。
假設(shè)把這$n-1$個(gè)數(shù)分成$a+b-2$個(gè)組，分配給左邊$a-1$個(gè)組，給右邊$b-1$個(gè)組。
對于$n$左邊的數(shù)，每個(gè)組內(nèi)部一定滿足第一個(gè)數(shù)最大，對于$n$右邊的數(shù)，每個(gè)組內(nèi)部一定滿足最后一個(gè)數(shù)最大。
這樣就滿足了題意。
這樣其實(shí)就是一個(gè)環(huán)排列計(jì)數(shù)，具體一點(diǎn)，就是求$n-1$個(gè)數(shù)劃分成$a+b-2$個(gè)集合，每個(gè)集合內(nèi)部再按特定順序圍圈分組的方法的數(shù)目。
這剛好是第一類斯特林?jǐn)?shù)。那么答案為$C(a + b - 2, a - 1) *?S(n - 1, a + b - 2)$。
?
Round #480 Div2? Problem E
去掉$k$個(gè)點(diǎn)，相當(dāng)于保留$n - k$個(gè)點(diǎn)，需要滿足剩下的$n - k$個(gè)點(diǎn)連通。轉(zhuǎn)化為保留$m$個(gè)點(diǎn)，求留下的點(diǎn)的權(quán)值和最大。
以$n$為根（必選），從$n - 1$開始往前選，假設(shè)當(dāng)前已經(jīng)選了$x$個(gè)點(diǎn)，如果當(dāng)前點(diǎn)往上爬，爬到第一個(gè)已經(jīng)被選的點(diǎn)時(shí)的移動距離大于$m - x$，
那么不能選這個(gè)點(diǎn)（因?yàn)檫x了一個(gè)點(diǎn)就必須選他的祖先），否則就選入這個(gè)點(diǎn)，然后選擇所有的他的祖先中未被選擇的點(diǎn)
（也是一步步往上爬，到發(fā)現(xiàn)了被選中的點(diǎn)為止），到選了$m$個(gè)點(diǎn)為止結(jié)束即可。
?
Round #482 (Div. 2) Problem D
預(yù)處理出所有數(shù)的因子。加入一個(gè)數(shù)的時(shí)候在以他的所有倍數(shù)為編號的字典樹中插入這個(gè)數(shù)，（字典樹編號最大為$100$）
查詢的時(shí)候如果$k$小等于$100$，那么在字典樹里查詢，否則直接暴力找。
?
Round #383 (Div. 1)? Problem D
首先預(yù)處理出$c[]$，$c[i]$表示$i$到根上所有邊的每個(gè)字母出現(xiàn)次數(shù)總和的奇偶性，狀態(tài)壓縮后用一個(gè)數(shù)表示。
如果滿足$c[x]$ ^ $c[y] = 1$，$x$到$y$的路徑上的所有字母重排后就可以組成一個(gè)回文串。
考慮dsu on the tree，對于每個(gè)點(diǎn)，求出$f[x]$：滿足$c[i] = x$的所有$i$的深度的最大值。
在遍歷輕兒子的所有后代的時(shí)候一邊更新最大值一邊刷新$f[]$就可以了，重兒子的方法類似。
?
Round #316 (Div. 2)? problem (E)
設(shè)$f(i, x1, y1, x2, y2)$表示A從左上角出發(fā)走了$i$步到達(dá)$(x1, y1)$，B從右下角出發(fā)走了$i$步到達(dá)$(x2, y2)$的方案數(shù)。
看似是$5$維的狀態(tài)，其實(shí)顯然可以轉(zhuǎn)化成$3$維，因?yàn)橹懒?x1$就知道了$y1$，知道了$x2$就知道了$y2$。
枚舉$i$，每次$x1$和寫$x2$有一個(gè)特定的范圍，總狀態(tài)不是很多。用滾動數(shù)組可以把數(shù)組降到二維。
最后統(tǒng)計(jì)答案的時(shí)候判斷一下奇偶就可以了。
?
?
5.22
Round #483 Problem C
狀態(tài)表示$dp[i][now][a][b][c]$， $i$表示第$i$個(gè)人此時(shí)正在電梯里，前$i-1$個(gè)人要么正在電梯上，要么已經(jīng)到達(dá)了目的地，$now$代表當(dāng)前電梯正停在第$now$層，$a$, $b$, $c$代表正在電梯里的三個(gè)人的目的地。
?
記憶化搜索轉(zhuǎn)移即可。
?
5.28
Avito Code Challenge 2018 Problem E
考慮這樣一個(gè)事實(shí)，如果某個(gè)和能被表示出來，那么這個(gè)數(shù)就可以成為最大值。
那么線段樹上跑背包就可以了，用bitset優(yōu)化。
時(shí)間復(fù)雜度$O(nqlogn / w)$
?
5.29
Edu Round 44 Problem G
考慮容斥。
首先不管沖突，計(jì)算答案，對于任意一個(gè)三元組，只要他是三元組就加到$ans0$。
然后對于任意一個(gè)三元組，如果他存在任意一條邊（每條都判），那么就加到$ans1$。
接著對于任意一個(gè)三元組，如果他存在兩條邊（每兩條都判一次），那么就加到$ans2$。
最后把所有三元環(huán)加到$ans3$.
這樣，對于任意一個(gè)三元組
如果他有$0$條邊，那么他被$ans0$計(jì)入了$1$次，最后計(jì)入了答案。
如果他有$1$條邊，那么他被$ans0$計(jì)入了入了$1$次，被$ans1$計(jì)入了$-1$次，最后對答案貢獻(xiàn)是$0$。
如果他有$2$條邊，那么他被$ans0$計(jì)入了入了$1$次，被$ans1$計(jì)入了$-2$次，被$ans2$計(jì)入了$1$次，最后對答案貢獻(xiàn)是$0$。
如果他有$3$條邊，那么他被$ans0$計(jì)入了入了$1$次，被$ans1$計(jì)入了$-3$次，被$ans2$計(jì)入了$3$次，被$ans3$計(jì)入了$-1$次，最后對答案貢獻(xiàn)是$0$。
那么就符合題意了。
?
Round 485 Div1? Problem C
暴力+記憶化搜索。
枚舉到一個(gè)集合的時(shí)候如果發(fā)現(xiàn)這個(gè)集合還沒標(biāo)記過（也就是還沒連通過），那么累計(jì)答案。
然后就把跟這個(gè)集合可以連邊的所有點(diǎn)全部加入這個(gè)連通塊，具體操作是按位異或之后標(biāo)記，并對所有子集標(biāo)記
感覺還是挺考智商的一個(gè)題。
?
6.6
Round 485 Div1? Problem D
先快速冪求出$3^{x}$，滿足$4 * 3^{x} <= n$，然后逐漸逼近。
乘法的時(shí)候要用FFT優(yōu)化，注意一些細(xì)節(jié)。
?
6.7
Round 429 Div1 Problem C
首先其實(shí)這是若干個(gè)連通塊的事情。
因?yàn)槿绻?a * b$和$b * c$都是完全平方數(shù)，那么$a * c$肯定是完全平方數(shù)。
所以這$3$個(gè)數(shù)兩兩都不能在一起。
然后就變成了HDU6116那個(gè)題。搞出卷積，然后暴力（甚至不用NTT）容斥就可以了。
?
6.8
用FFT匹配字符串的經(jīng)典問題，就是加了一個(gè)門限值$K$
因?yàn)橹挥?4$個(gè)字符，所以提取出$4$個(gè)$01$序列。
把S串對應(yīng)的$01$序列每個(gè)$1$位置前后$k$個(gè)都變成$1$，然后按照套路來就可以了。
?
6.9
Round 485 Div1 Problem E
首先$10^{7}$以內(nèi)所有數(shù)最多只有$8$個(gè)質(zhì)因子。
那么對每個(gè)數(shù)分解質(zhì)因數(shù)，然后把詢問拆開來，對每個(gè)質(zhì)因子獨(dú)立求解。
可以證明所有質(zhì)因子要處理的信息的和不超過$nlogn$個(gè)。
把問題轉(zhuǎn)化為求某個(gè)點(diǎn)到根結(jié)點(diǎn)這條鏈上的$min(a[i], x)$的和。
于是就想到了排序，然后一個(gè)個(gè)加進(jìn)樹狀數(shù)組。
維護(hù)兩個(gè)樹狀數(shù)組，每次把那些小于詢問的加到第一個(gè)，把那些已經(jīng)大于詢問的從第二個(gè)減去。
（腦補(bǔ)一下這個(gè)過程）
至于樹狀數(shù)組怎么操作，回想一下差分的思想。
搞出dfs序之后如果要加上某個(gè)點(diǎn)的值，那么對這個(gè)點(diǎn)代表的dfs序區(qū)間差分一下，然后單點(diǎn)求值。
最后把詢問的答案整理一下就可以了。
?
6.13
最近的兩場比賽加起來掉了$160$多分……心累。
直接回藍(lán)名。
主要是后面的題不會，中間的題卡了太久，以及前面的題FST。
教育場就是教育場吧，前面后面的題權(quán)重都一樣，都是$1$
這教育場的G我怎么就去寫點(diǎn)分治了啊……完全沒必要的。
所以跳題是真的虧，這也說明了我垃圾的讀題能力。
div2最近加大了一些難度，個(gè)人覺得Round 487并不是一場很好的比賽，題目難度有點(diǎn)偏高了。
（以及有點(diǎn)毒瘤）
?
6.14-7.29
woc快兩個(gè)月了我一點(diǎn)都沒寫過。
慢慢填坑
EDU 45
F? 直接固定一棵生成樹然后dfs一遍就好了。
G 樹形DP一下就可以，沒必要點(diǎn)分治。注意兒子的信息用完之后得清空，不然會MLE
?
EDU 46
E 固定生成樹之后并查集（類似17沈陽網(wǎng)絡(luò)賽那個(gè)套路），求出每條邊的新權(quán)值
（如果是必經(jīng)之路那么為$1$，否則為$0$）
然后求一下直徑就行了。
F 直接線段樹就好了。離線操作就行。
?
Round 488 Div 1 E
FFT裸題
?
Round 493 Div1
D
其實(shí)只要求出每棵樹的$dp[x][k]$就行，也就是從$x$出發(fā)走$k$步再回到$x$的方案數(shù)。
直接求顯然很難，考慮樹分治。
給每個(gè)點(diǎn)加一個(gè)強(qiáng)行必須經(jīng)過的點(diǎn)，然后計(jì)算貢獻(xiàn)。
這樣在樹分治的過程中一個(gè)點(diǎn)的經(jīng)過區(qū)域剛好被那些分治中心劃分成了最多$log$個(gè)區(qū)域
分治的時(shí)候DP兩個(gè)東西，一個(gè)是從分治中心出發(fā)經(jīng)過$k$步最后到某個(gè)點(diǎn)的步數(shù)。
還有一個(gè)是從分治中心出發(fā)經(jīng)過$k$步中途不能回來并且最后到某個(gè)點(diǎn)的方案數(shù)。
對當(dāng)前子樹的某個(gè)點(diǎn)的答案貢獻(xiàn)就是$∑f[x][i] * g[x][k - i]$
也就是枚舉一個(gè)點(diǎn)經(jīng)過了多少步第一次到達(dá)分治中心，然后在分治中心開始兜兜轉(zhuǎn)轉(zhuǎn)，
最后回到自己。
最后兩棵樹的答案求一下卷積和就行了。
?
Round 483 Div1 E
考慮每個(gè)點(diǎn)往上走一次路線最高能走到哪里。
然后倍增一下。
詢問的時(shí)候先跳到跳一步就能到LCA的那個(gè)位置，
記作$x$和$y$，先判斷能否到達(dá)。
然后討論一下，如果存在一條兩端分別在$x$子樹和$y$子樹里面
就可以直接到了，否則答案還要加$1$
這是一個(gè)二維數(shù)點(diǎn)問題，直接離線樹狀數(shù)組就可以了。
?
Round 439 Div 2 D
首先考慮哪些點(diǎn)要被考慮。
新加的邊兩端的點(diǎn)，這些點(diǎn)到根的所有點(diǎn)。
最多$240$個(gè)點(diǎn)，構(gòu)成了一張新的無向圖。
每個(gè)點(diǎn)是帶權(quán)的，權(quán)值為這個(gè)點(diǎn)管轄的點(diǎn)數(shù)。
然后枚舉起點(diǎn)，搜索一下簡單路徑個(gè)數(shù)即可。
?
Avito Code Challenge 2018
G?動態(tài)開點(diǎn)線段樹跑一下就可以了。
?
Round 395 Div1 E
高中學(xué)弟上黃題！
回滾莫隊(duì)直接艸過去了……
?
轉(zhuǎn)載于:https://www.cnblogs.com/cxhscst2/p/9061855.html
總結(jié)
以上是生活随笔為你收集整理的Codeforces 补题记录的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
