Mato is No.1

@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)，因此問題有解當(dāng)且僅當(dāng)A*A^T不是全1。
隨機1*N的向量v，看(v*A)*A^T是否等于v*(N*N的全1矩陣)，如果A*A^T不是全1那么期望試兩次就可以得到不等的結(jié)果。（如果試了10次都是相等，就視為無解）
如果兩邊的乘積不等，則找到那個不等的列，設(shè)為第i列，則必然存在一個解包含向量i，枚舉另一個即可。時間復(fù)雜度O(Nd)
k=3：計算(A*A^T)&e1;i&e3;&e1;j&e3;²(mod 3)，即(Σ(x_ik*x_jk))²，即Σ(x_ik1*x_ik2*x_jk1*x_jk2)(mod 3)，對每個向量構(gòu)造一個d²維向量，為之前的每個向量各維兩兩相乘的結(jié)果，則轉(zhuǎn)化為k=2的情況（只不過將mod 2改為mod 3），時間復(fù)雜度O(Nd²)，常數(shù)小一點（比如少算mod）可以卡過去。

count：
（正解需要某些很奇怪的性質(zhì)，本沙茶看不出來，只會85分的）
遞推，設(shè)F&e1;i&e3;&e1;j&e3;和G&e1;i&e3;&e1;j&e3;表示某層是BFS序列的&e1;i..j&e3;這一段，樹的總高度和樹的棵數(shù)（所求平均值即為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;這一段的各個結(jié)點在DFS序列中的位置遞增（這個很顯然）。
第一，BFS&e1;j+1..k&e3;這一段的各個結(jié)點在DFS序列中的位置之前都必須有在BFS&e1;i..j&e3;范圍內(nèi)的結(jié)點，作為它的父結(jié)點（這個也很顯然）；
第二，DFS序列中，所有在BFS&e1;i..j&e3;范圍內(nèi)的結(jié)點的下一個位置如果不是在BFS&e1;0..i-1&e3;范圍內(nèi)的，就必須是BFS&e1;j+1..k&e3;范圍內(nèi)的，因為這表示它的第一個子結(jié)點（這個灰常難想到！！！！！！！！！！！！！！！本沙茶就掛在這里了囧……）
對于第零和第一，實際上是給出了k的上限，枚舉k時不符合這個條件則退出，而第二則是給出了k的下限（所有的“下一個位置”要填滿才能算）；
此外，F(xiàn)和G要用long double（double也會爆，不用擔(dān)心精度，本沙茶當(dāng)時還在如何維護平均值的問題上糾結(jié)了很久……）
這個做法是O(N³)的，但加上那些優(yōu)化就可以85分了囧……
（本沙茶當(dāng)時想到這個做法了，也想到了第零和第一，但木有想到第二，結(jié)果掛了……要是真得到85分，總分254，穩(wěn)的rank1了……真悲劇，真悲劇，真悲劇，真悲劇，真悲劇，真悲劇，真悲劇，真悲劇，真悲劇，真悲劇，真悲劇，真悲劇，真悲劇，真悲劇，真悲劇，真悲劇……）

train：
史上最水的提交答案……整個就是個NOIP普及組難度的題……
首先分析數(shù)據(jù)就不難發(fā)現(xiàn)這10個點其實是一種模型：
一開始有若干元錢（用變量v 2表示）。
有若干個大塊，每個大塊可以選擇進或者不進，如果進，就要付出一些錢，如果不進，就自動跳轉(zhuǎn)到后面的某個大塊。
在每個大塊里有若干個（不超過25個）小塊，有1或10個變量，每個小塊也可以選擇要或者不要，如果要，就對所有的變量各加上一個效果值（可正可負(fù)）。
目標(biāo)是所有變量的絕對值之和最大（每個大塊末尾會結(jié)算一次，然后將所有變量的值清零）
首先每個大塊內(nèi)選哪些小塊可以暴力枚舉，然后得到最大的總絕對值，設(shè)為val&e1;i&e3;（i為大塊編號），設(shè)如果不進第i個大塊，跳到的大塊編號為B&e1;i&e3;，第i個大塊付出的錢為V&e1;i&e3;。
而大塊之間就是一個類似于01背包的模型，設(shè)F&e1;i&e3;&e1;j&e3;表示到達(dá)第i個大塊（尚未作出選擇）時，用掉了j元錢的最大總效果值，用F&e1;i&e3;&e1;j&e3;更新F&e1;B&e1;i&e3;&e3;&e1;j&e3;，若不超過一開始的總錢數(shù)則用F&e1;i&e3;&e1;j&e3;+val&e1;i&e3;更新F&e1;i+1&e3;&e1;j+V&e1;i&e3;&e3;，要實時保存最優(yōu)決策。
輸出的時候注意一下，那里面有幾個點，當(dāng)錢不夠時會自動選擇不進當(dāng)前大塊，木有必要作出選擇了。

至此Day1完掛。

【Day2】
matrix：
矩陣乘法，十進制快速冪。沒了。

penman：
比較猥瑣的DP題……
重點是這個：所有的圖形都可以拆成單列，一列一列地弄（本沙茶太弱了，這個都木有想起來），然后就是三維DP。
N：設(shè)F&e1;i&e3;&e1;j&e3;&e1;k&e3;&e1;st&e3;表示第i列，上下邊界分別為j、k行，狀態(tài)為第st個部分（第0部分為最左邊一豎，第1部分為中間若干塊，第2部分為最右邊一豎）的最優(yōu)解，計算好一列之后求出一大堆輔助值，就可以使下一列O(1)算出了。
I：設(shè)F&e1;i&e3;&e1;j&e3;&e1;k&e3;&e1;st&e3;表示第i列，上下邊界分別為j、k行，狀態(tài)為第st個部分（第0部分為那一豎的左邊，第1部分為那一豎，第2部分為那一豎的右邊）的最優(yōu)解，不需要輔助值，直接求即可；
O：可以DP，但更好的辦法是枚舉左、右、上邊界，然后掃描，說它更好是因為知道了左右邊界，可以直接引出左邊的N和右邊的I的最優(yōu)解。
具體實現(xiàn)的時候細(xì)節(jié)很多……真折磨人。還有要注意為節(jié)省空間，F(xiàn)數(shù)組要對i這一維滾動。

foodshop：
首先這是個無向環(huán)套樹（關(guān)于這方面的總結(jié)見這里）
枚舉開店的那條邊，如果是樹邊，求出該邊的較下結(jié)點往下的最大長度dist1，以及往其它結(jié)點的最遠(yuǎn)距離dist2，則結(jié)果即為min{dist1+x, dist2+L-x}，滿足0<=x<=L，L為該邊長度。dist1求法不說了，dist2分為兩部分，樹內(nèi)的，可以轉(zhuǎn)化為經(jīng)典DP模型“樹的中心點”；樹外的，先求出環(huán)上的每個結(jié)點往樹中走的最大長度，作為這個結(jié)點的權(quán)值，然后就轉(zhuǎn)化為一個帶邊權(quán)和點權(quán)的環(huán)，對于每個點i，求出max{i、j距離+j的權(quán)值}（j為環(huán)上的點）的值，這個值可以通過在環(huán)上掃描的方法求出：設(shè)G&e1;i&e3;為第i個點出發(fā)，逆時針走更優(yōu)的位置最遠(yuǎn)到哪里。逆時針掃描這個環(huán)，然后所有的G就可以在線性時間內(nèi)求出，求出G后，對每個點分別求出其逆時針更優(yōu)區(qū)與順時針更優(yōu)區(qū)內(nèi)的最大值（可以在掃描過程中用線段樹維護），即可解決這個問題。
如果開店的邊在環(huán)上，設(shè)其兩端點為i、j（i->j為逆時針方向）。很容易發(fā)現(xiàn)，如果在這條邊上開店，則j的逆時針更優(yōu)區(qū)內(nèi)的所有點一定是逆時針到這個店更近，i的順時針更優(yōu)區(qū)內(nèi)的所有點一定是順時針到這個店更近，而其它的點則需要額外判斷一下是順時針更近還是逆時針更近（總判斷次數(shù)為線性）。這樣也可以借助線段樹在掃描過程中求出每條環(huán)邊的順、逆時針更優(yōu)區(qū)，從而轉(zhuǎn)化為與樹邊的問題一樣的模型。時間復(fù)雜度O(NlogN)。
不過，對于環(huán)邊，還有一種更簡單的做法（Orz @hza）：
二分最遠(yuǎn)距離（即結(jié)果）D，然后對于環(huán)上的所有點，找到這個環(huán)上到這個點距離大于（D-這個點樹里的最大深度）的點集合（顯然是連續(xù)的一段弧），對所有點的這種弧求并，如果能覆蓋整個環(huán)，則最優(yōu)解<D，否則最優(yōu)解>=D。

本沙茶Day2全暴力，只拿了暴力分……對付繁瑣題的能力太弱了，代碼量一大就悲劇……
（后來發(fā)現(xiàn)，foodshop的暴力都寫疵了囧……枚舉開店的邊后應(yīng)該用SPFA求最短路，因為刪掉的可能是樹邊，剩下的不是樹……不過數(shù)據(jù)弱，木有出現(xiàn)這種情況囧……）

至此NOI2013完掛。
———————————————————————————————————————————————————
【總結(jié) && 一些感想】
從上面可以看出，本沙茶在NOI2013中使用的算法都是NOIP普及組以內(nèi)難度的囧（matrix的矩陣乘法可能略高級一些，但顯然也不能超過NOIP難度）……
這些算法都是本沙茶在2009年以前就搞懂的，也就是說，后4年掌握的所有算法，這次都木有用上……
最后一次NOI，竟如此富有戲劇性……居然只考普及組算法……
圖論、高級數(shù)據(jù)結(jié)構(gòu)、字符串、幾何、數(shù)論、組合……這次都木有考，這也是NOI歷史上的一個“創(chuàng)舉”了囧……
但盡管如此，本沙茶在此次NOI中仍然暴露出了諸多問題……并不是比賽技巧問題，而是平時埋下的禍根……
想題不夠靈活，找不出題目隱藏的特殊性質(zhì)，特殊情況考慮不清楚，寫代碼速度太慢……這些都是平時不好好做題，天天頹廢的結(jié)果……
因此，這次掛掉，也是理所應(yīng)當(dāng)?shù)氖?#8230;…