文章目錄

• • 二分答案的作用
  • 堆和區(qū)間
  • 很糙ddp
  • 線段樹合并
  • 網(wǎng)絡(luò)流結(jié)論の1
  • 樹上莫隊
  • 對角線與GCD
  • 區(qū)間與掃描線與方案數(shù)
  • 歐拉歐拉*1
  • 斯坦納樹
  • 切比雪夫距離
  • 二分匹配結(jié)論の1
  • min-max容斥
  • 計算幾何の -1

---

二分答案的作用

求最大值最小$or$最小值最大

將求值問題轉(zhuǎn)換為判斷問題

在判斷問題之間相互轉(zhuǎn)換

---

堆和區(qū)間

當(dāng)查詢前$k$個最值區(qū)間時可以將開始時先將區(qū)間丟入堆中，每次取出堆頂然后將區(qū)間按照答案分裂成兩個存入堆中

[NOI2010]超級鋼琴【RMQ,堆】
[十二省聯(lián)考2019]異或粽子【可持久化Trie,堆】

---

很糙ddp

將權(quán)值改為矩陣，然后將運算改成廣義矩陣乘法
然后用區(qū)間數(shù)據(jù)結(jié)構(gòu)維護即可
[模板]動態(tài)DP【矩陣乘法,樹鏈剖分,線段樹】
保衛(wèi)王國【動態(tài)dp,最小覆蓋集】
迷宮【ddp,線段樹,矩陣乘法】

---

線段樹合并

首先是必要的動態(tài)開點，然后合并時從需要合并的兩顆線段樹的根出發(fā)

若兩邊都有左節(jié)點那就遞歸左節(jié)點(右節(jié)點同理)

若只有一邊有左節(jié)點那就讓合并后的樹直接連接向左節(jié)點(右節(jié)點依舊同理)

時間復(fù)雜度$:O(n\log n)$
時間復(fù)雜度證明(很糙):

我們不難發(fā)現(xiàn)合并的最大復(fù)雜度是最小的那顆子樹的大小，那么因為只有$n$次插入那么一棵樹最多$n\log n$個節(jié)點，但是因為是最小的那顆子樹大小，所以不可能每顆子樹都是$nlogn$個節(jié)點，所以對于每個節(jié)點最多被作為最小的子樹合并$\log n$次。

證畢

([NOI2013模擬]法法塔的獎勵【權(quán)值線段樹,線段樹合并】)[https://blog.csdn.net/Mr_wuyongcong/article/details/95209896]

---

網(wǎng)絡(luò)流結(jié)論の1

結(jié)論:最小割中對于一條邊$(x,y)$在殘量網(wǎng)絡(luò)中$s$可以到達$x$不能到達$t$且$y$可以到達$t$不能到達$x$那么這條邊是必割邊

證明:

在殘量網(wǎng)絡(luò)上$s$可以到達$x$且$y$可以到達$t$那么說明若該邊不割那么$s$就可以通過該邊到達$t$。假設(shè)在$s$到$x$的路上有同樣長度的一條道路且割掉后可以使$s$到達$x$那么在殘量網(wǎng)絡(luò)上該邊的流量必定為0，因為切割掉$x?>y$的流量也必定會經(jīng)過該邊所以在殘量網(wǎng)絡(luò)上$s$就不可以到達$x$了。所以該假設(shè)不成立。

證畢
秘密任務(wù)【最短路,網(wǎng)絡(luò)流最小割】

---

樹上莫隊

維護一個歐拉序，然后在歐拉序上進行莫隊即可。
[NOI2013模擬]蘋果樹【樹上莫隊,LCA】

---

對角線與GCD

$n?m$的矩陣對角線會穿過$n+m?(n,m)$個格子
證明:

對于若$(n,m)==1$(互質(zhì))則會經(jīng)過$n+m?1$個格子，所以我們可以將$n?m$拆分成$gcd(n,m)$個$n/gcd(n,m)?m/gcd(n,m)$的格子于是我們發(fā)現(xiàn)答案就是$$(n/gcd(n,m)+m/gcd(n,m)?1)?gcd(n,m)$$
也就是$$n+m?gcd(n,m)$$

證畢

蛋糕切割【數(shù)論,GCD】

---

區(qū)間與掃描線與方案數(shù)

對于$x,y$，給出若干個限制如下:
若$x\in [L{x}_i,R{x}_i]$時要求$y\in /[L{y}_i,R{y}_i]$

那么我們可以建立一個$(L{x}_i,L{y}_i,R{x}_i,R{y}_i)$的矩陣然后掃描線求矩陣的總覆蓋面積即可。

[Noip提高組模擬1]樹【線段樹,掃描線,倍增】

---

歐拉歐拉*1

$$\phi (m!)=m!\prod _{i=1}^k\frac{p_i?1}{p_i}$$
[SDOI2008]沙拉公主的困惑【線性篩,歐拉函數(shù),逆元】

---

斯坦納樹

一張圖，求一個最小權(quán)的生成樹要求包含指定的點。

用狀態(tài)壓縮$dp$后用$SPFA$轉(zhuǎn)移(因為有后效性)
挖寶藏(treasure)【斯坦納樹,SPFA,狀壓】

---

切比雪夫距離

定義:
$$di{s}_{i,j}=max\{|x_i?x_j|,|y_i?y_j|\}$$

用法:

將曼哈頓距離轉(zhuǎn)換為切比雪夫距離，讓$(x,y)$變?yōu)?span id="ze8trgl8bvbq" class="katex--inline">$(x+y,x?y)$。與一個點距離$\le D$的點就變?yōu)榱嗽诟狞c為中心的$2?D$長的正方形內(nèi)。

將切比雪夫距離轉(zhuǎn)換為曼哈頓距離，讓$(x,y)$變?yōu)?span id="ze8trgl8bvbq" class="katex--inline">$(\frac{x+y}{2},\frac{x?y}{2})$。然后就可以使用二維前綴和進行計算。

世界第一的猛漢王【切比雪夫距離,掃描線】

---

二分匹配結(jié)論の1

每個極大匹配都是完全匹配的充要條件是在完全匹配中每個聯(lián)通塊兩邊點數(shù)相同且都是滿二分圖。

證明

證畢

---

min-max容斥

$$max\{S\}=\sum _{T\in S}min\{T\}?(?1{)}^{|T|?1}$$

---

計算幾何の -1

對于一個這樣的三角形
$BC$和$CA$中有一條斜率比$AB$小，一條比$AB$大

---

總結(jié)

以上是生活随笔為你收集整理的学习手记(2019/7/05~2019/8/31)——快乐暑假的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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