【Day1】
vigenere：不說了；
game：
方法一（本沙茶在現場的做法，60分）：
設i的左右手為A[i]和B[i]。二分最大的金幣數D，則第i個人要滿足其前面所有人（包括國王）的A之積不超過S[i] = (D+1) * B[i] - 1。
考慮站在最后的那個人，顯然除了他以外的所有人（包括國王）的A之積不能超過他的S值，如果木有人滿足此條件則無解，否則取滿足此條件的A值最大的人，放最后（因為若某個合法方案最后不是滿足此條件的A值最大的人，則把那個A值最大的人與他交換，仍然是合法方案），然后刪掉這個人，轉化為子問題，直到所有人都刪掉為止，此時必然有解。
此方法時間復雜度為O(N
2 * log
2MAXW)，其中MAXW為D的上限，由于60%的數據D<=10
9，所以MAXW取10
9。
顯然這個方法是不能再加高精度了，否則必T，問題是計算所有人的A之積時會超過long long范圍，解決方法：由于A和B的上限是10
4，D的上限是10
9，所以有解時必然有所有人的A之積<=10
9 * 10
4 * 10
4 = 10
17，因此在過程中若超過這個值，必定無解，直接卡掉。
方法二（正解）：
把所有的人按照A*B遞增排序，就一定是最優解，剩下的就不解釋了（需要高精度乘除單精度）。
證明：
若某方案不是將所有人按照A*B遞增排序的，則必然存在i使得A[i]*B[i]>A[i+1]*B[i+1]（這里的i是排序后的編號，不是原來的編號），下證交換i和(i+1)之后解必然不會變差。
設i前面所有人（包括國王）的A值之積為S1。
交換前，i的金幣數為S1/B[i]，(i+1)的金幣數為S1*A[i]/B[i+1]；
交換后，i的金幣數為S1*A[i+1]/B[i]，(i+1)的金幣數為S1/B[i+1]；
注意這里S1*A[i]/B[i+1]顯然不小于S1/B[i+1]，而S1*A[i]/B[i+1]-S1*A[i+1]/B[i]=S1*(A[i]*B[i]-A[i+1]*B[i+1])/(B[i]*B[i+1])>0，因此交換前(i+1)的金幣數不小于交換后i和(i+1)的金幣數，而除了i和(i+1)外，其他人在交換前后金幣數都不變，因此總的金幣數的最大值不會變大，即解不會變差。證畢。
這兩種解法都是貪心，但它們是從不同的角度入手的——方法一是“分階段貪心”，證明需要分別證最優子結構性質和貪心選擇性質；方法二是“排序貪心”——在一類有關最優順序的問題中，一般解法不是貪心，就是二分圖或網絡流模型（當然小數據也可以狀壓），如果用貪心，只要找到一種排序方法（對某個值排序），使得若不這樣排序則把相鄰逆序的元素交換后能夠得到不更差的解，做法就是正確的。drive：（本沙茶想出正解了，可是實在寫不完，后來交暴力了囧——真真真真真真真真真真真真真真真真真真真真真真真真真真真真真真悲劇）
首先求出S1[i]和S2[i]分別表示i往右最近的和第二近的位置，這個用平衡樹可以解決；
然后，每個位置i拆成兩個點i.A和i.B，分別表示從這里出發，A先開和B先開。i.A往S2[i].B（如果有的話）連一條邊，邊權為兩位置距離，i.B往S1[i].A（如果有的話）連一條邊，邊權為兩位置距離。由于不會有環（S1[i]、S2[i]均>i），所以是森林。
然后，設F1[i]和F2[i]分別為從i走到根結點，A開的長度和B開的長度，這個BFS一下就可以了囧。
對于第一問，設W[i]為從i往上走，總長不超過X0時最遠能走到哪里，顯然只要從下到上求W，類似單調隊列亂搞即可；求出W后，枚舉每個點i，用記錄的F1和F2值可以求出i到W[i]路徑上A開的和B開的長度，找比值最小的即可；
對于第二問，可以在求出森林后用樹的路徑剖分搞，但更好的做法是倍增：設SUM[i][k]表示從i往上走2
k條邊的總長度，SUM可以在預處理中求出，做第二問時，只需要在SUM里調就行了，一次操作的時間復雜度O(log
22N)。
顯然這是個數據結構綜合題，巨繁瑣（估計代碼要超過10K），本沙茶當時花了1h+寫，后來發現腫么也不可能寫完了，就交暴力了囧（早知道一上來就寫暴力了，這樣或許能想出來game的正解啊啊啊啊啊啊啊啊啊……哭死……）
總之Day1跪得不成人形了……
【Day2】
mod: 不說了；
classroom：線段樹是可以AC的，只不過要把兩個操作（找最小值和區間減法）放一起；
當然，本題的正解是，二分M0，然后看前M0個操作是否能全部滿足：將每個操作(l, r, D)拆成(1, r, D)和(1, l-1, -D)（當l>1時），這樣所有操作的左端點都是1了，設S[i]為右端點為i的所有操作的D之和，這個顯然可以在線性時間內得到，則點i的變化量就是S[i..N]之和，這個在求出S[i]后從后到前掃描一下即可得出，也是線性，如果所有的變化量加上原來的值都不小于0，則前M0個操作都能滿足，否則就不是都能滿足。
這樣，時間復雜度仍是O(NlogM)的。更好的方法是，借鑒倍增的思想，如果前M0個可以滿足，就把前M0個都滿足（把所有點都加上變化量），接下來就不用考慮前M0個操作了，只在后面繼續二分。這樣，算法的時間復雜度就是線性的了。
blockade：
【首先每個軍隊往上走當然是最好的，但不能在根上停住。
因此，二分最長時間D（注意D<=5*10^13），然后先看不能走到根的軍隊，一直往上走直到時間到了。
然后看能走到根的，先讓他們全到根上，然后，對于那些“還有葉結點木有被控制的”根的子樹（防止斷句錯誤），用那些走到根上的來控制，用貪心解決……
本沙茶就這么寫的，寫了180+行，也查完了，可是在結束前5min時突然發現漏了一種情況——
某些能到根的軍隊可以不走到根，直接停在根的子結點處，控制這棵子樹。
可是已經來不及了，最后就木有考慮這種情況……而且這種情況還比較普遍……】
這種情況的解決辦法：
如果某個軍隊能走到根，但讓它再走一步，走回到它所在的那個根的子結點，就來不及了的話，就讓它停在根的子結點處，控制它自己的子樹。這是因為，如果它去幫別的子樹，必然就有第三個軍隊要來幫它。設它所在的那個根的子結點為B，它去幫的子結點為A，幫它的第三個軍隊所在的根的子結點為C，由于它自己走不回來，所以第一次走到根的子結點處的剩余時間T<2*W(root, B)，而它能去幫別的子結點，所以T>=W(root, A)+W(root, B_，可得出W(root, A)<W(root, B)。第三個軍隊能來幫它，所以第三個軍隊剩余的時間>=W(root, B)+W(root, C_，自然>W(root, A)+W(root, C)，所以這第三個軍隊也能去幫A，因此，讓原來的軍隊停在B，第三個軍隊去幫A，也是合法方案。
注：本題灰常麻煩，需要用到樹DFS、BFS、倍增（這個和drive腫么一樣啊囧……），本沙茶寫的時候還用上了線段樹囧……
總之Day2也跪了，但不像Day1那么慘囧……
總之Day2比Day1跪得更慘囧……