hyf

周冬《生成樹的計數(shù)及其應(yīng)用》

//----------------------------------------------------------------------------------------------------------------------------
排列
    1-n的一個排列i1、i2...in通過兌換變成標(biāo)準(zhǔn)排列1、2...n所需的對換次數(shù)和該排列逆序?qū)€數(shù)奇偶性相同(一個排列中任意兩個數(shù)對換后，逆序?qū)ζ媾夹愿淖?
    記&(a1,a2..an)為(-1)的改排列奇偶性次冪
行列式
    那么一個方陣的行列式det A = ∑(1->n,i1->in) &(i1->in)*(ai1*ai2*...*ain)
    方陣的代數(shù)余子式Mij為方陣A去掉i行j列所有元素后的n-1階方陣的有符號行列式(乘上-1的i+j次冪)
    方陣的主子式等于主對角線上任何一個坐標(biāo)代數(shù)余子式的絕對值
    行列式等于它的任一行（列）的各元素與其代數(shù)余子式的乘積之和
    行列式一行（列）的元素等比例加到另一行（列）上，其行列式不變，故可化解方陣求行列式 O(n^3)
Matrix-Tree定理
    Kirchhoff矩陣C為G的度數(shù)矩陣(主對角線上填各點(diǎn)的度)減去G的鄰接矩陣(故相連點(diǎn)ij則Cij=-1否則為0)
    圖的生成樹個數(shù)即為該圖的kirchhoff矩陣的主子式的絕對值
//----------------------------------------------------------------------------------------------------------------------------

楊弋《Hash在信息學(xué)競賽中的一類應(yīng)用》

//----------------------------------------------------------------------------------------------------------------------------
例1.多維匹配
    基本思想是樸素+hash,用Rabin-Karp計算多維數(shù)組的hash值，相等的才值得樸素比較
    Rabin-Karp: f(s)=∑(i->len(s)) s[i]*p^(len(s)-i) mod q
例2.Equal squares
    和上題一樣的hash,只是這里認(rèn)為hash值相同那么舉著那就相同了，這樣一般出錯率很小
    一個技巧是計算兩個hash,一個用于確定hash表中的位置，另一個則用于比較
例3.不穩(wěn)定匹配
    用數(shù)據(jù)結(jié)構(gòu)維護(hù)hash值
總之就是利用Rabin-Karp的可遞推性，利用各種數(shù)據(jù)結(jié)構(gòu)的特點(diǎn)來快速計算hash值并進(jìn)行維護(hù)。
//----------------------------------------------------------------------------------------------------------------------------

胡伯濤《最小割模型在信息學(xué)競賽中的應(yīng)用》

//----------------------------------------------------------------------------------------------------------------------------
引入
    首先介紹了網(wǎng)絡(luò)流的基本知識和最大流最小割定理
    網(wǎng)絡(luò)的最小割為求最大流后殘留網(wǎng)絡(luò)中與s連通的點(diǎn)集為S,其余為T
    最大流算法推薦sap
分?jǐn)?shù)規(guī)劃
    Min λ=a(x)/b(x) x∈S,b(x)>0
    則λ為f(x)=a(x)/b(x)的最小值
    令g(λ)=min{a(x)-λ*b(x)}
    g（λ）為嚴(yán)格遞減函數(shù) —— ①
    Dinkelbach定理λ為原規(guī)劃的最小值當(dāng)且僅當(dāng)g(λ)=0 —— ②
    那么就可以根據(jù)①②來二分λ
    g(λ)=0 -> λ=λ*
    g(λ)<0 -> λ>λ*
    g(λ)>0 -> λ<λ*
應(yīng)用
    例1.
    求一圖的割集C, 使之平均邊權(quán)最小
        λ=f(x)=∑(WeXe)/∑(Xe)=（WX）/X，若選邊e則Xe=1，否則為0
        則g(λ)=min{(W-λ)X}
        二分λ,求g(λ)的方法是構(gòu)新圖，使We'=We-λ,則要求We'X,則新圖的一個最小和割集，把所有負(fù)邊選入后再最大流求最小割即可
    例2.
        圖的一些定點(diǎn)權(quán)值已經(jīng)給出，邊權(quán)等于兩端點(diǎn)權(quán)值的xor,求最小可能的邊權(quán)和
        由于xor的每位可以單獨(dú)考慮，所以問題轉(zhuǎn)換為點(diǎn)權(quán)為{0,1}，兩端點(diǎn)相同則邊權(quán)為1，求最小邊全和
        把原來所有無向邊變成兩條有向邊，S到所有確定為0的點(diǎn)，所有確定為1的點(diǎn)連到T，求最小割即為答案，因?yàn)榭梢哉J(rèn)為S割集全為0，T割集全為1
最大權(quán)閉合子圖
    閉合子圖指一子圖的任意點(diǎn)后繼都在圖內(nèi)的子圖，可描述事件間必要條件的關(guān)系
    最大權(quán)閉合子圖指最大點(diǎn)權(quán)和的閉合子圖
    構(gòu)造網(wǎng)絡(luò)流： 原圖中邊均保留且容量為正無窮，所有正權(quán)點(diǎn)連到S,負(fù)權(quán)點(diǎn)連到T,容量為點(diǎn)權(quán)絕對值
                 證明原圖的閉合子圖V1與割[S,T]一一對應(yīng)
                 最大權(quán)即為【正權(quán)和-最小割】
最大密度子圖
    Maximize D=∑(Xe)/∑(Xv), Xe表e邊是否存在，Xv表v點(diǎn)是否存在
    則令h(g)=max{∑Xe-∑gXv}, 求h(g)
    由于選擇了邊必須選擇相應(yīng)端點(diǎn)，所以初步算法是用最大權(quán)閉合子圖解決
    改進(jìn)的算法是使h(g)=min{∑gXv-∑Xe},而∑Xe=∑dVi/2-[V,V'],h(g)=min{∑gXv-∑dVi/2+[V,V']}意即最小割[V,V']，并且選擇每個點(diǎn)V要付出代價,這個處理

可以把所有點(diǎn)連向T,容量即為權(quán)值，那么在割內(nèi)的點(diǎn)還要割去權(quán)值的那條邊，無誤。
    若邊帶權(quán)，則把每個點(diǎn)的度數(shù)定義為齊所連邊權(quán)值和
    若點(diǎn)帶權(quán)，則把點(diǎn)權(quán)g換成(g-Pv)
二分圖最小權(quán)覆蓋集
    把原二分圖每條變?nèi)萘孔優(yōu)檎裏o窮，從S向X和Y到T連容量為點(diǎn)權(quán)的邊，最小割即可保證每條邊都至少有一端在割集內(nèi)
二分圖最大權(quán)獨(dú)立集
    總權(quán)值-最小權(quán)覆蓋集
割的性質(zhì)
    1.在給定網(wǎng)絡(luò)中去掉割的邊集則不存在從S到T的路徑
    2.在給定的流網(wǎng)絡(luò)中，任意一個割將點(diǎn)集劃分成兩部分
技巧
    1.用正無限容量排除不參與決策的邊
    2.利用割的定義來分析最優(yōu)性
    3.利用與源或匯關(guān)聯(lián)的邊容量處理點(diǎn)權(quán)
//----------------------------------------------------------------------------------------------------------------------------