@import url(http://www.shnenglu.com/CuteSoft_Client/CuteEditor/Load.ashx?type=style&file=SyntaxHighlighter.css);@import url(/css/cuteeditor.css);
@import url(http://www.shnenglu.com/CuteSoft_Client/CuteEditor/Load.ashx?type=style&file=SyntaxHighlighter.css);@import url(/css/cuteeditor.css);
【Day0】
不說了囧……
【Day1】
meow：
k=2：先將這N個d維向量組成一個N*d的矩陣A，則A*A
T&e1;i&e3;&e1;j&e3;(mod 2)就是向量i•向量j(mod 2)，因此問題有解當且僅當A*A
T不是全1。
隨機1*N的向量v，看(v*A)*A
T是否等于v*(N*N的全1矩陣)，如果A*A
T不是全1那么期望試兩次就可以得到不等的結果。（如果試了10次都是相等，就視為無解）
如果兩邊的乘積不等，則找到那個不等的列，設為第i列，則必然存在一個解包含向量i，枚舉另一個即可。時間復雜度O(Nd)
k=3：計算(A*A
T)&e1;i&e3;&e1;j&e3;
2(mod 3)，即(Σ(x
ik*x
jk))
2，即Σ(x
ik1*x
ik2*x
jk1*x
jk2)(mod 3)，對每個向量構造一個d
2維向量，為之前的每個向量各維兩兩相乘的結果，則轉化為k=2的情況（只不過將mod 2改為mod 3），時間復雜度O(Nd
2)，常數小一點（比如少算mod）可以卡過去。
count：
（正解需要某些很奇怪的性質，本沙茶看不出來，只會85分的）
遞推，設F&e1;i&e3;&e1;j&e3;和G&e1;i&e3;&e1;j&e3;表示某層是BFS序列的&e1;i..j&e3;這一段，樹的總高度和樹的棵數（所求平均值即為F&e1;i&e3;&e1;j&e3; / G&e1;i&e3;&e1;j&e3;）。
則枚舉k，若k
滿足一定條件，則F&e1;j+1&e3;&e1;k&e3;+=F&e1;i&e3;&e1;j&e3;+G&e1;i&e3;&e1;j&e3;，G&e1;j+1&e3;&e1;k&e3;+=G&e1;i&e3;&e1;j&e3;。
問題是這個“一定條件”是什么（最難搞的地方囧）
第零，BFS&e1;j+1..k&e3;這一段的各個結點在DFS序列中的位置遞增（這個很顯然）。
第一，BFS&e1;j+1..k&e3;這一段的各個結點在DFS序列中的位置之前都必須有在BFS&e1;i..j&e3;范圍內的結點，作為它的父結點（這個也很顯然）；
第二，DFS序列中，所有在BFS&e1;i..j&e3;范圍內的結點的下一個位置如果不是在BFS&e1;0..i-1&e3;范圍內的，就必須是BFS&e1;j+1..k&e3;范圍內的，因為這表示它的第一個子結點（這個灰常難想到！！！！！！！！！！！！！！！本沙茶就掛在這里了囧……）
對于第零和第一，實際上是給出了k的上限，枚舉k時不符合這個條件則退出，而第二則是給出了k的下限（所有的“下一個位置”要填滿才能算）；
此外，F和G要用long double（double也會爆，不用擔心精度，本沙茶當時還在如何維護平均值的問題上糾結了很久……）
這個做法是O(N
3)的，但加上那些優化就可以85分了囧……
（本沙茶當時想到這個做法了，也想到了第零和第一，但木有想到第二，結果掛了……要是真得到85分，總分254，穩的rank1了……真悲劇，真悲劇，真悲劇，真悲劇，真悲劇，真悲劇，真悲劇，真悲劇，真悲劇，真悲劇，真悲劇，真悲劇，真悲劇，真悲劇，真悲劇，真悲劇……）
train：
史上最水的提交答案……整個就是個NOIP普及組難度的題……
首先分析數據就不難發現這10個點其實是一種模型：
一開始有若干元錢（用變量v 2表示）。
有若干個大塊，每個大塊可以選擇進或者不進，如果進，就要付出一些錢，如果不進，就自動跳轉到后面的某個大塊。
在每個大塊里有若干個（不超過25個）小塊，有1或10個變量，每個小塊也可以選擇要或者不要，如果要，就對所有的變量各加上一個效果值（可正可負）。
目標是所有變量的絕對值之和最大（每個大塊末尾會結算一次，然后將所有變量的值清零）
首先每個大塊內選哪些小塊可以暴力枚舉，然后得到最大的總絕對值，設為val&e1;i&e3;（i為大塊編號），設如果不進第i個大塊，跳到的大塊編號為B&e1;i&e3;，第i個大塊付出的錢為V&e1;i&e3;。
而大塊之間就是一個類似于01背包的模型，設F&e1;i&e3;&e1;j&e3;表示到達第i個大塊（尚未作出選擇）時，用掉了j元錢的最大總效果值，用F&e1;i&e3;&e1;j&e3;更新F&e1;B&e1;i&e3;&e3;&e1;j&e3;，若不超過一開始的總錢數則用F&e1;i&e3;&e1;j&e3;+val&e1;i&e3;更新F&e1;i+1&e3;&e1;j+V&e1;i&e3;&e3;，要實時保存最優決策。
輸出的時候注意一下，那里面有幾個點，當錢不夠時會自動選擇不進當前大塊，木有必要作出選擇了。
至此Day1完掛。
【Day2】
matrix：
矩陣乘法，十進制快速冪。沒了。
penman：
比較猥瑣的DP題……
重點是這個：所有的圖形都可以拆成單列，一列一列地弄（本沙茶太弱了，這個都木有想起來），然后就是三維DP。
N：設F&e1;i&e3;&e1;j&e3;&e1;k&e3;&e1;st&e3;表示第i列，上下邊界分別為j、k行，狀態為第st個部分（第0部分為最左邊一豎，第1部分為中間若干塊，第2部分為最右邊一豎）的最優解，計算好一列之后求出一大堆輔助值，就可以使下一列O(1)算出了。
I：設F&e1;i&e3;&e1;j&e3;&e1;k&e3;&e1;st&e3;表示第i列，上下邊界分別為j、k行，狀態為第st個部分（第0部分為那一豎的左邊，第1部分為那一豎，第2部分為那一豎的右邊）的最優解，不需要輔助值，直接求即可；
O：可以DP，但更好的辦法是枚舉左、右、上邊界，然后掃描，說它更好是因為知道了左右邊界，可以直接引出左邊的N和右邊的I的最優解。
具體實現的時候細節很多……真折磨人。還有要注意為節省空間，F數組要對i這一維滾動。
foodshop：
首先這是個無向環套樹（關于這方面的總結見
這里）
枚舉開店的那條邊，如果是樹邊，求出該邊的較下結點往下的最大長度dist1，以及往其它結點的最遠距離dist2，則結果即為min{dist1+x, dist2+L-x}，滿足0<=x<=L，L為該邊長度。dist1求法不說了，dist2分為兩部分，樹內的，可以轉化為經典DP模型“樹的中心點”；樹外的，先求出環上的每個結點往樹中走的最大長度，作為這個結點的權值，然后就轉化為一個帶邊權和點權的環，對于每個點i，求出max{i、j距離+j的權值}（j為環上的點）的值，這個值可以通過在環上掃描的方法求出：設G&e1;i&e3;為第i個點出發，逆時針走更優的位置最遠到哪里。逆時針掃描這個環，然后所有的G就可以在線性時間內求出，求出G后，對每個點分別求出其逆時針更優區與順時針更優區內的最大值（可以在掃描過程中用線段樹維護），即可解決這個問題。
如果開店的邊在環上，設其兩端點為i、j（i->j為逆時針方向）。很容易發現，如果在這條邊上開店，則j的逆時針更優區內的所有點一定是逆時針到這個店更近，i的順時針更優區內的所有點一定是順時針到這個店更近，而其它的點則需要額外判斷一下是順時針更近還是逆時針更近（總判斷次數為線性）。這樣也可以借助線段樹在掃描過程中求出每條環邊的順、逆時針更優區，從而轉化為與樹邊的問題一樣的模型。時間復雜度O(NlogN)。
不過，對于環邊，還有一種更簡單的做法（Orz @hza）：
二分最遠距離（即結果）D，然后對于環上的所有點，找到這個環上到這個點距離大于（D-這個點樹里的最大深度）的點集合（顯然是連續的一段弧），對所有點的這種弧求并，如果能覆蓋整個環，則最優解<D，否則最優解>=D。
本沙茶Day2全暴力，只拿了暴力分……對付繁瑣題的能力太弱了，代碼量一大就悲劇……
（后來發現，foodshop的暴力都寫疵了囧……枚舉開店的邊后應該用SPFA求最短路，因為刪掉的可能是樹邊，剩下的不是樹……不過數據弱，木有出現這種情況囧……）
至此NOI2013完掛。
———————————————————————————————————————————————————
【總結 && 一些感想】
從上面可以看出，本沙茶在NOI2013中使用的算法都是NOIP普及組以內難度的囧（matrix的矩陣乘法可能略高級一些，但顯然也不能超過NOIP難度）……
這些算法都是本沙茶在2009年以前就搞懂的，也就是說，后4年掌握的所有算法，這次都木有用上……
最后一次NOI，竟如此富有戲劇性……居然只考普及組算法……
圖論、高級數據結構、字符串、幾何、數論、組合……這次都木有考，這也是NOI歷史上的一個“創舉”了囧……
但盡管如此，本沙茶在此次NOI中仍然暴露出了諸多問題……并不是比賽技巧問題，而是平時埋下的禍根……
想題不夠靈活，找不出題目隱藏的特殊性質，特殊情況考慮不清楚，寫代碼速度太慢……這些都是平時不好好做題，天天頹廢的結果……
因此，這次掛掉，也是理所應當的事……
遺失了過去，因此，現在后悔了…………………………………………………………………
不過，不管腫么講，還是混進了集訓隊……集訓隊是一個新的開始，每天都面臨巨大的挑戰，同時每天都能得到巨大的提高……
雖然本沙茶現在很弱，應付難題的能力還遠遠不夠，但經過這一年的訓練，相信可以改變這一切，盡快脫菜……
希望這能是一個轉折點。
50，12，6，4，1。
———————————————————————————————————————————————————
膜拜本次虐場神犇
@鼎爺
@xudyh
@xyz111
@hzaskywalker(FFT)
@hzhwcmhf
@zhj
@魚丸
@sunzhouyi
以及眾多虐掉count、penman、foodshop的神犇……