【复习总结】玫瑰人生 La Vie en Rose
?
La Vie en Rose
?? ??? ?????
??? ??? na na now
?? ?? na na now
I don't wanna make it blue
???? ?? la vie en rose
———IZ*ONE
準備在聯賽前看完我所有的博客
于是每篇寫一個小小的一句話總結
DP
上升序列
主要是要注意最長上升子序列的nlogn求法，即相當于是維護結尾最小元素，二分插入元素，以及前導0的處理方式。
但是一般不會這樣寫，會直接和棧頂比較然后如果比棧頂大就更新棧頂，否則再去二分查找位置。
股票市場
其實這題的背包確實很明顯，但是建模也不是很容易看出來。背包的容量隨著每一天買賣完后進行了變化，而價值也計算的是兩天之差。
連通能力
確認過眼神，是我看不懂的題了TAT
玉米田
這個超級入門狀壓還是會做的幸好qvq。
地圖類狀壓三部曲：預處理合法狀態、預處理第一行、與原地圖比較和合法狀態兩重判斷后轉移
互不侵犯
這個也很裸，差不多的，多預處理一層need，轉移也多了一層而已
炮兵陣地
這個復雜了一些，用到了映射存狀態，細節也很多，但是狀態定義還是沒有變。現在也不考這種狀壓了，太套路了。
消失之物
dp套著容斥考是比較難考慮全狀態的，統計答案用到了逆向思維，用它去填充這一部分等價于用其他的物品去填充剩余部分
Mine
現在來看這個題還是推不對，有幾點，第一是1個炸彈要分左右兩邊，第二是想不到可以直接知道的地方直接推，不知道的地方推所有的方案。還有一些細節，什么起點不能左邊有炸彈，終點不能右邊有炸彈。
桿子的排列
后來看紫書的數學部分的時候才發現是紫書上的題，但是這個狀態定義真的很妙，轉移也簡單地分成了三種情況。
周年紀念日
終于推對了一次。樹形dp是真的很喜歡在點和邊的貢獻上玩花樣，尤其是這種統計全圖答案的題啊。
據說這叫換根法？因為既dfs了子樹對根的貢獻，又用了根對子樹的轉移。不了解。
子串
妙啊~
p這一維真的是太令人舒適了，直接解決了本題最困難的問題，同一個匹配B的串的多個拆分方式。
而這又給了一個提示，往往題上的限制條件會被納入狀態定義的維度中。除了上一句提到的還有。k個子串的限制
飛揚的小鳥
看這道題有點蜜汁混亂，就是關于01背包和完全背包，于是我決定惡補一下
好吧問題解決，二維的01背包可以正序寫。看來還是理解不深刻在背啊。一維的01背包不能正序寫的本質原因是什么？
是階段的問題！j-w[i]是第i-1個階段可以用來更新第i個階段的j，然后j-2*w[i]時j-w[i]已經計算過了，變為了第i個階段。又是第i-1個階段更新第i個階段
但是正序的話j-2*w[i]是第i-1個階段，j-w[i]也是第i-1個階段，這不就涼了嗎
形象一點的解釋在這里
換教室
這個期望dp其實好像也不是很難啊qvq然而是t3.。
算了我昨天才被一個裸得一絲不掛的概率dp教做人了，感覺我一直不是很能掌握這種dp的定義然后轉移很混亂，或者是有的時候在拿概率算有的時候在拿期望算？
于是我決定現在再去研究一下，然后做一道期望/概率dp
做了。。好水啊，感覺難的打擊信心水的也很
干脆找時間把01的這篇看了吧。。
逛公園
去年的T3，感覺也不是很難啊。但是記憶化搜索我寫的真的很少很少很少，感覺自己也沒怎么分清楚了記憶化搜索和dp的一些細微差別
于是又開始惡補
這篇洛谷日報寫得太好了%%%%
感覺這個復習計劃快演變成好文推送了？？
想去寫一道入門的記搜，至少找一下感覺
寶藏
嗨呀居然推出來了這個dp。。上面都沒幾道能再推出來
雖然我推這個把層數也設成了狀態 但是完全不影響 可能是受了上面記憶化搜索的影響所以推的挺快的叭
但是我看我的寫法里面好像沒有記憶化誒..但是已經實現了減少狀壓dp的硬傷——狀態數量了也OK
遺失的二叉樹
這個區間合并的思想可以說是非常實用了，比較標準的區間dp的感覺
在大區間中間找一個點，判斷以這個點為中間結點的兩個小區間是否合法，以及這個中間結點和大區間是否沖突
Average distance
很裸的樹形dp，像之前提到的，在邊上統計。
transaction transacation transaction
其實不難誒，但是我又沒有想到。這個dp+貪心其實是很好的思維方向，最小成本，最大價值。
但是我覺得是不好想到的。
突然想起了那道最短路的最優貿易，其實也是在分開維護成本和代價，然后相減貪心求解。
寫到這里突然發現我把最優貿易咕咕咕掉了，趕緊去補上
?Y
這是唯一一篇我看著很舒服的圖? 因為我畫的圖都太魔性了
正難則反
ZYB's Tree
妙啊！！！！！！！！！！！
這個應該也算換根法？我發現這類題的特征一定是一個答案想要計算出來既要知道子樹的貢獻又要知道父親的貢獻
所以套路就是先子樹后父親
往往是用子樹的一些已知的條件去做第二次dfs
而這個題也類似。但是情況往往也有重復的。
比如這個f[u][j-1]-f[v][j-2]其實也不容易考慮到
Big binary tree
emmm這個題遇到了我是絕對做不來的 離散化 并利用二叉樹的性質?
Magic boy Bi Luo with his excited tree
太困難了 放棄
矩陣
當時考場上調出來的，再看一下還是確定能做出來吧，畢竟也不復雜就是細節
逆序對統計
從貢獻的方式考慮轉移順序
好記的字符串
兩種轉移方式其實都很好想，注意一下是兩種方式都可以預處理出修改后的狀態
校長的煩惱
看了這道題的集合用二進制運算突然有個腦洞
是不是^等價于減法，|等價于加法。那其實那個題根本不用寫得那么復雜
m0就是有1個人可以交的課 m1就是有2個人可以交的課
s0^m0就是減去現在有1個人可以教的課 （s1^m1）|m0 就是減去有兩個人可以交的課再加上有一個人交的課 s2|m1就是加上有兩個人可以交的課
?woc我簡直天才本才 woc我以前真傻，真的
Twenty questions
記憶化搜索+狀壓，邊界很簡單，但是這個轉移真的很迷
Hacker's Crackdown
二進制子集枚舉?
for(int s0=s;s0;s0=(s0-1)&s)相當于忽略0后不斷減1。
Mega Man's Mission
每次遇到統計方案數的dp其實都能很快推出來但是總不知道答案是怎么統計的或者會不會漏的
然而其實只要按著從小到大的推就好了。而一般統計方案數的題都有f[0]=1。而很多位同時轉移的時候比較少，但是也有比如上面的好記的字符串
因為大多數狀壓都是枚舉了所有狀態的，所以每次只需要轉移一位，再后面總會再枚舉到這個轉移后的狀態。
Robot Dog
看的時候就覺得不對勁，果然有個地方寫錯了TAT 約分的時候少乘了個son[i]，居然沒人發現誒。。。
然后這個題真的是很妙，也給了一個警示，就是思維不要被那個順序局限了，可能你需要的只是預處理。這個預處理套預處理最后找到一個O(1)的計算方法是真的很妙了。
LIS的數量
真的看不懂了，一頭霧水，可能當時也沒弄透徹吧，明天找01問問
老大
樹形dp+二分
花園
省選-級別的狀壓了。。太困難了。
看了半天只有一個感悟? 還可以把不符合條件的點當做符合條件的點看 然后同樣的dp計算方案數
紙牌游戲
這個概率dp是很行云流水地就做出來了，又是記憶化搜索
危險的組合
還有一種做法是直接容斥 這又說明很多和數學掛鉤的方案數其實也可以用dp做 又比如前面的那個桿子的排列 其實后面的咕咕咕也是
咕咕咕
也是數學 當時真的是一點也沒往這方面想 f[i]=f[i-j]*C(i,j)這個都可以當結論背了 前提是要1和0的位置無關
小遲的錦標賽
f[i+1][j+1]+=f[i][j]*p[i+1][j] //成功
f[i+1][j]+=f[i][j]*(1-p[i+1][j]) //失敗
等公交
f[s+t[i]]+=f[s]*p[i]是很好推的
但是答案統計是等的時間*等這么長時間的概率 等的時間從T開始算的話那應該是（i-T）? 然后概率就是那個時間段來車的概率
這個上界也比較玄學
數學
余數之和
妙！都不敢相信當時看懂了過后自己是怎么推出來的。。只能說確實花了很長時間鉆研這個題吧
然后第一句求r那也是看了半天，其實都是為了防超過邊界n而已
Agent1
看完這道題信心暴漲 覺得自己啥規律都能找出來23333
其實是因為只用到了高一的一點數列的知識 然后組合數那個又是眾所周知嘛
日常
這個題我已經看不懂了 但是我還是看了一下錯排公式
?D(1)=0 D(2)=1
D(n)=(n-1)*(D(n-1)+D(n-2))
推導：先放第n個元素在第k個位置上，再放第k個元素。
此時第k個元素有兩種放法 如果放在第n個位置 剩下的n-2個元素就有D(n-2)種放法?
如果不放在第n個位置上 那這個n-1個元素合起來有D(n-1)種放法
Candy
這個題其實也蠻好的 到了最后我以為還要求逆元其實根本不用 因為能化成這樣說明10n-1一定有9這個因子，直接弄除數里面去就行了。
這也提醒了快速冪的多種用法
Visible Lattice Points
這個題也蠻經典的了 其實模型還是很容易看出來
The Luckiest number
一個重要結論！！！
axΞ1(mod n)的最小x一定是phi(n)的因數
?
轉載于:https://www.cnblogs.com/NSD-email0820/p/9927269.html
總結
以上是生活随笔為你收集整理的【复习总结】玫瑰人生 La Vie en Rose的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 做一个像人的3d人物建模需要通过什么技术
- 下一篇： 微信红包随机数字_微信随机红包数详解和算