今天從家里出來(lái)的時(shí)候帶了一塊巧克力放在包里，結(jié)果競(jìng)賽的時(shí)候忘記吃了~~

昨晚得到通知說(shuō)：“市選總共五道題，至少有兩道送分題。”
結(jié)果第一題果然是一道送分題：兩數(shù)相減，從數(shù)據(jù)規(guī)模來(lái)看不需要高精度。預(yù)計(jì)分?jǐn)?shù)：100
第二題數(shù)據(jù)規(guī)模是n<=maxlongint，而且不注意的話很容易中間結(jié)果溢出，可以通過(guò)不停地求余運(yùn)算避免。盡管避免了溢出，但是復(fù)雜度是O(n)，如果數(shù)據(jù)不是很弱的話肯定會(huì)超時(shí)。預(yù)計(jì)分?jǐn)?shù)：(50,100)
第三題是動(dòng)態(tài)規(guī)劃，剛看完題目就寫(xiě)出狀態(tài)轉(zhuǎn)移方程了，復(fù)雜度O(1/2n^2)，數(shù)據(jù)規(guī)模n<=5000，應(yīng)該不會(huì)超時(shí)。預(yù)計(jì)分?jǐn)?shù)：100
第三題比較郁悶的是，因?yàn)榭臻g復(fù)雜度是O(n^2)，想通過(guò)滾動(dòng)數(shù)組優(yōu)化一下，但是一直沒(méi)有弄好，拐回頭一看：內(nèi)存限制128M，打開(kāi)計(jì)算器算了一下，不會(huì)超空間，又想改回來(lái)，結(jié)果怎么改改不對(duì)了，連樣例都通不過(guò)！猶豫了一會(huì)，急忙不停地點(diǎn)“撤銷(xiāo)”，終于該回來(lái)了！浪費(fèi)了十幾分鐘……
第四題，一開(kāi)始感覺(jué)像是BFS，但是又舉出了反例；動(dòng)態(tài)規(guī)劃吧，第三題已經(jīng)出了，而且如果DP的話，需要做四次；DFS，規(guī)模太大；騙分，給出的數(shù)據(jù)有很多內(nèi)容，不好猜測(cè)……最后選擇了輸出樣例。
第五題，給出一個(gè)長(zhǎng)度為n的序列，對(duì)最小值、最大值之間的數(shù)（不包括最大值）增加一個(gè)定值，執(zhí)行此操作m次，每次輸出最小值、最大值的編號(hào)和數(shù)值，數(shù)據(jù)規(guī)模很大：n,m<=1000000。最先考慮某種樹(shù)結(jié)構(gòu)，往O(mlogn)的方向思考：二叉排序樹(shù)，不支持增加某個(gè)值的操作；線段樹(shù)，RMQ問(wèn)題編程復(fù)雜度太高，而且100萬(wàn)的規(guī)模O(mlogn)都有可能超時(shí)啊！難道有O(m)的算法嗎？心想，不太可能。最后的做法是：模擬。

唉……市選的結(jié)果不令人滿意。

后記：
今天下午成績(jī)出來(lái)了，全市第一，但是分?jǐn)?shù)卻不理想，沒(méi)達(dá)到我的目標(biāo)。
想到我的高中OI生涯即將結(jié)束，不免有些感傷。單憑這一點(diǎn)，AOI2010我也要拼盡全力！只剩下一個(gè)月，我不知道還能夠進(jìn)步多少，總之會(huì)盡力而為！