本沙茶自從NOI2011結束以來，陷入危機，具體表現為：編程速度變慢；想題目的時候容易想偏；編程時比較不專注，容易想到別的東西上去；容易受到雜念的干擾。這次危機是本沙茶至今為止遇到的最嚴重的一次危機，到了9月中下旬，這次危機發展到極限，幾乎到了絕望的邊緣。因此，本沙茶在長達1個多月的時間里，沒有什么實質性的進展，也沒有在這個空間里作總結。

在十一假期的前四天里，本沙茶努力調整狀態，終于在10月4日（也就是今天），正式擺脫了危機，恢復到了正常狀態。以后，本沙茶會繼續在這里作總結，同時爭取盡可能大的提高，在本賽季的各項比賽中竭盡全力，爭取好成績。

感謝BZOJ對本沙茶在擺脫危機過程中的幫助。
Orz WJMZBMR等神犇

【背景（神犇不要鄙視）】
本沙茶今年AHOI的時候，遇到裸的最佳匹配的題，竟然把KM算法搞忘了，幸虧是WJMZBMR神犇保佑，臨時亂弄一通，想起來了……這MS反映出了本沙茶以前在看某些經典算法的時候看得不深，木有理解透徹……
前幾天又遇到一道最佳匹配的題，發現KM算法竟然又忘了……米辦法，只有把這個搞死人的算法的具體過程重新看了一遍，終于懂了……
【KM算法及其具體過程】
（1）可行點標：每個點有一個標號，記lx[i]為X方點i的標號，ly[j]為Y方點j的標號。如果對于圖中的任意邊(i, j, W)都有lx[i]+ly[j]>=W，則這一組點標是可行的。特別地，對于lx[i]+ly[j]=W的邊(i, j, W)，稱為可行邊；
（2）KM算法的核心思想就是通過修改某些點的標號（但要滿足點標始終是可行的），不斷增加圖中的可行邊總數，直到圖中存在僅由可行邊組成的完全匹配為止，此時這個匹配一定是最佳的（因為由可行點標的的定義，圖中的任意一個完全匹配，其邊權總和均不大于所有點的標號之和，而僅由可行邊組成的完全匹配的邊權總和等于所有點的標號之和，故這個匹配是最佳的）。一開始，求出每個點的初始標號：lx[i]=max{e.W|e.x=i}（即每個X方點的初始標號為與這個X方點相關聯的權值最大的邊的權值），ly[j]=0（即每個Y方點的初始標號為0）。這個初始點標顯然是可行的，并且，與任意一個X方點關聯的邊中至少有一條可行邊；
（3）然后，從每個X方點開始DFS增廣。DFS增廣的過程與最大匹配的Hungary算法基本相同，只是要注意兩點：一是只找可行邊，二是要把搜索過程中遍歷到的X方點全部記下來（可以用vst搞一下），以進行后面的修改；
（4）增廣的結果有兩種：若成功（找到了增廣軌），則該點增廣完成，進入下一個點的增廣。若失敗（沒有找到增廣軌），則需要改變一些點的標號，使得圖中可行邊的數量增加。方法為：將所有在增廣軌中（就是在增廣過程中遍歷到）的X方點的標號全部減去一個常數d，所有在增廣軌中的Y方點的標號全部加上一個常數d，則對于圖中的任意一條邊(i, j, W)（i為X方點，j為Y方點）：
<1>i和j都在增廣軌中：此時邊(i, j)的(lx[i]+ly[j])值不變，也就是這條邊的可行性不變（原來是可行邊則現在仍是，原來不是則現在仍不是）；
<2>i在增廣軌中而j不在：此時邊(i, j)的(lx[i]+ly[j])的值減少了d，也就是原來這條邊不是可行邊（否則j就會被遍歷到了），而現在可能是；
<3>j在增廣軌中而i不在：此時邊(i, j)的(lx[i]+ly[j])的值增加了d，也就是原來這條邊不是可行邊（若這條邊是可行邊，則在遍歷到j時會緊接著執行DFS(i)，此時i就會被遍歷到），現在仍不是；
<4>i和j都不在增廣軌中：此時邊(i, j)的(lx[i]+ly[j])值不變，也就是這條邊的可行性不變。
這樣，在進行了這一步修改操作后，圖中原來的可行邊仍可行，而原來不可行的邊現在則可能變為可行邊。那么d的值應取多少？顯然，整個點標不能失去可行性，也就是對于上述的第<2>類邊，其lx[i]+ly[j]>=W這一性質不能被改變，故取所有第<2>類邊的(lx[i]+ly[j]-W)的最小值作為d值即可。這樣一方面可以保證點標的可行性，另一方面，經過這一步后，圖中至少會增加一條可行邊。
（5）修改后，繼續對這個X方點DFS增廣，若還失敗則繼續修改，直到成功為止；

下面分析整個算法的時間復雜度：每次修改后，圖中至少會增加一條可行邊，故最多增廣M次、修改M次就可以找到僅由可行邊組成的完全匹配（除非圖中不存在完全匹配，這個可以通過預處理得到），故整個算法的時間復雜度為O(M * (N + 一次修改點標的時間))。而一次修改點標的時間取決于計算d值的時間，如果暴力枚舉計算，這一步的時間為O(M)，優化：可以對每個Y方點設立一個slk值，表示在DFS增廣過程中，所有搜到的與該Y方點關聯的邊的(lx+ly-W)的最小值（這樣的邊的X方點必然在增廣軌中）。每次DFS增廣前，將所有Y方點的slk值設為+∞，若增廣失敗，則取所有不在增廣軌中的Y方點的slk值的最小值為d值。這樣一次修改點標的時間降為O(N)，總時間復雜度降為O(NM)。

需要注意的一點是，在增廣過程中需要記下每個X、Y方點是否被遍歷到，即fx[i]、fy[j]。因此，在每次增廣前（不是對每個X方點增廣前）就要將所有fx和fy值清空。

代碼：

 

【1】IOI2009 hiring（這個在各大OJ上都找不到囧，只能看這里了囧，第11頁）
可以發現本題就是求一個比率rate，使得第i個人（如果用的話）工資為rate*Qi，并且還要滿足以下兩個限制條件：
（1）每人的最低工資限制：第i個人如果用的話，有rate*Qi>=Si，即rate>=Si/Qi；
（2）總開銷限制：rate*所有用的人的Q值之和<=W，即所有用的人的Q值之和<=W/rate。
這樣，可以先將所有人按照(S/Q)的值遞增排序，然后枚舉需要用的最后一個人（排序后的，也就是S/Q值最大的那個人），設為i，則總花費最省的做法顯然是取rate=Si/Qi。然后根據（2）式得出“所有用的人的Q值之和”的最大值W0=W/rate，其中，第i個人是必須要用的，故將W0值先減去Qi（若W0<Qi，則第i個人不可使用），剩下的問題就變成了在第0~(i-1)個人中（排序后的）選取一些人，使得他們的Q值之和不大于W0，并且選取的人盡可能多。顯然這可以用貪心來實現，即選取Q值最小的若干個人。接下來，由于題目中N<=500000，說明需要用數據結構來優化，可是Q的上限只有20000且Q為正整數，因此，線段樹是最好的選擇。建立一棵表示[1, 20000]的線段樹，每個結點存放兩個額外的值：sz和sum，分別表示Q值位于該結點代表的區間內的人的總數以及這些人的Q值總和。然后，需要解決上述子問題時，從根結點開始考察結點的sz值，不斷往下找即可（這有點像平衡樹的找第K小的操作）。
總時間復雜度：O(N * (log20000 + logN))（還有排序的時間）
代碼

【2】RQNOJ469
先按照任意一種屬性（這里為A）遞增排序，然后枚舉值i，排序后第1位~第i位的全部給A（看A屬性，它們中A屬性最大的一定是i），排序后第(i+1)位及以后的，看其B、C兩種屬性的大小，若B屬性更小就看B屬性，若C屬性更小就看C屬性，然后得出兩種屬性的最大值即可。因此可以得到下面的算法：先排序，然后將所有的毛的B或C屬性（哪種更小就看哪種）插入平衡樹（這里需要兩棵平衡樹，一棵存放B屬性的值，一棵存放C屬性的值），然后遞增枚舉i（注意i=0的情況不要漏掉），將第i位的B或C屬性在平衡樹中刪除，然后找出兩棵平衡樹中的最大值即可。
但是需要注意一種特殊情況：所有的毛都看同一個屬性，此時按照上面的算法可能求不出最優解，比如：
10 6 5
10 2 8
此時，第1個C屬性更小，第2個B屬性更小，若第1個看C屬性，第2個看B屬性，則總和為5+2=7，而如果兩個都看B屬性則總和為6。此時就需要特判（預先求出三種屬性中的最大值），然后再用上面的算法求解，就能保證求出最優解了。
代碼

【3】PKU2985
并查集+平衡樹基本操作，水題，不解釋。
代碼

【4】HNOI2011 括號匹配Brackets（目前可以看這個帖子）
Splay Tree維護序列問題。對于一段括號序列A[1..len]，定義優先級P[0..len]如下：
P[0]=0
P[i]=P[i-1]+1（i>0且A[i]為左括號）
P[i]=P[i-1]-1（i>0且A[i]為右括號）
然后，Splay Tree的每個結點需要記錄一個Z值和M值，分別表示該結點代表的括號序列中最后一個元素的優先級和優先級最小的元素的優先級。則可以證明：這段括號序列調整至平衡至少需要改變的括號數目為(-M+K+1) / 2，其中K=Z+((-M+1)/2)*2（注意這里的/是整除），此外由于有swap和invert兩個操作，因此需要記錄RM、TM、RTM值，分別表示將該括號序列執行swap操作后的序列的M值、執行invert操作后的序列的M值，以及同時執行swap和invert操作后序列的M值。
不過，本題需要嚴重注意的是：雖然replace操作的標記（代碼中的mk0）會覆蓋掉swap（代碼中的mk1）和invert（代碼中的mk2）操作的標記，但是在下放標記的時候，需要對三種標記逐一判斷，mk0和mk1、mk2并不是不能共存的！因為有可能先打上mk0標記后再打上mk1或mk2標記。
本題雖然是靜態的，但仍然不能使用線段樹，因為線段樹無法支持整體翻轉（rev）操作。
代碼

     摘要: 【原題見這里】很明顯的精確覆蓋的模型，12個零件，再加上它們經過旋轉、翻轉后的不同形狀，共60種，每種又可以放在不同的位置（只看最左上的那個珠子）一種零件的一種位置就是一行。列（限制）有兩種：每個格子只能放一個（55列），以及每個零件（注意是每個零件，不是每種零件）只能用一次（12列），共67列。預先放的那些零件可以看成預先選中的行。然后DLX精確覆蓋即可。下面是DLX精確覆蓋的幾個易疵點：（1）...  閱讀全文