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