我擦擦擦擦擦擦擦擦擦擦擦擦擦擦擦擦.....


最近真是忙成狗，要是這個(gè)節(jié)奏真是要跪啊。
真是對(duì)不起關(guān)注我博客的同學(xué)。
最近在忙什么呢？

1. 邢老師的項(xiàng)目
2. 選修課大作業(yè)
3. 同學(xué)的畢設(shè)
4. 找實(shí)習(xí)

真是牽扯精力。。。
其實(shí)說白了，還是時(shí)間分配有問題。。。

所以。。。 為了區(qū)域賽不坑隊(duì)友。。。
哥決定！

堅(jiān)持刷題寫博客，以后的博文前面都寫上【奮戰(zhàn)2013regional】

大家監(jiān)督！！！ 好像bzoj有些題是看不到 & 做不了的？
包括我以前做過的一些題。
聽說得捐款或者出題，有沒有知道詳情的。。。      摘要: 我的名字叫韓飛，是哈工程的一枚弱菜... 10級(jí)....   閱讀全文

距離去年狂刷題的日子已經(jīng)過去一年了，一年來發(fā)生了很多，改變了很多。
是成熟了，還是老了呢。我不知道，不知不覺已經(jīng)很少再刷題，不過還會(huì)堅(jiān)持做定期的在線比賽。
可惜rating遲遲也上不去，雄心壯志也漸漸褪去。

額，還是來說這個(gè)比賽吧。。。去南京的途中沒什么好說的，除了再一次做火車?yán)鄣靡溃拖氲綉?yīng)該是最后一次做長(zhǎng)途火車了，也沒什么特別的感覺了。

比賽前一天晚上很緊張，兩點(diǎn)多才睡著。。。 偷偷告訴自己，只要保持注意力集中，就能給力！

比賽開始，xy從頭往后看題，孟神從后往前看題，我輸入密碼登錄pc^2。這時(shí)xy已經(jīng)告訴我A題是個(gè)水題了。。。
xy上去敲A，我再確認(rèn)了一下A題的條件，然后提醒了xy一些細(xì)節(jié)。12min 1Y

這時(shí)發(fā)現(xiàn)J題已經(jīng)有隊(duì)伍提交了。孟神給我解釋了一下題意，我想了一個(gè)貪心的做法。然后上去敲。
這時(shí)候直播的鏡頭ms拍到我了，當(dāng)時(shí)我很緊張，表情比較糾結(jié)。。。 生怕交錯(cuò)了增加罰時(shí)。。。不過好在A了 = = 27min 1Y
然后，孟神給我講了I題的做法，我感覺靠譜，然后就自己敲了。。。。 結(jié)果調(diào)樣例各種不過，然后就把代碼帶出來扔給孟神了。

然后發(fā)現(xiàn)C是tiling問題，怒搞之。。。 然后樣例也沒過，各種調(diào)。。。。
后來孟神終于發(fā)現(xiàn)了I題的傻逼錯(cuò)誤，74min 1Y.
緊接著我也發(fā)現(xiàn)了C題的bug，84min 1Y.

然后此時(shí)排名是第五，感覺很不錯(cuò)。
發(fā)現(xiàn)B有人A，和xy討論了一個(gè)算法，上去敲，怒寫二分，期間因?yàn)樘o張（智商低）衍生出來各種疑問，被xy拉下來了 = =...

然后xy 1WA = =... 我接著我那個(gè)敲，但是我也不能保證Yes。。。 但是ms可以避免一些精度問題，敲完了之后，測(cè)了一些數(shù)據(jù)，發(fā)現(xiàn)和xy的一樣。。。更沒底了

不過還是交了，出乎意料的yes ...152min 2Y

然后就是2個(gè)半小時(shí)，你看看我，我看看你，然后就結(jié)束了 = =... 最后銀獎(jiǎng)第四。。。

0。Guass消元的方法
Guass消元可以求矩陣的秩，行列式，逆元，解方程組等等。
矩陣的值可以是整數(shù) or 浮點(diǎn)數(shù)。
對(duì)于解方程組來說，x1 + x2 + ... mod m = b 用主列消元法，需要求逆元。
如果是浮點(diǎn)數(shù)，可以用迭代法（spfa），在姜碧野的論文里有講。


1。利用Guass消元解決計(jì)數(shù)問題

這一類我掌握的不好，一般來講是求方程組的解的個(gè)數(shù)。
當(dāng)然應(yīng)該只對(duì) x1 + x2 + ... + xn mod m = b 這樣的整數(shù)方程組有效了。
srm 590 div1 500就是典型的例子，在n個(gè)數(shù)中挑選一些數(shù)，讓其xor值小于等于limit。
這個(gè)問題和等于是等價(jià)的。至于等于怎么求，就是方程組的解數(shù)了。和自由元的個(gè)數(shù)相關(guān)。


2。開關(guān)問題

3。求期望

     摘要:   閱讀全文

     摘要: topcoder 577  閱讀全文

     摘要:   閱讀全文

     摘要: 。。。  閱讀全文

我們知道，求解方程組的一般方法是高斯消元，時(shí)間復(fù)雜度為 O(n^3)。

如果求得解是實(shí)數(shù)的話，我們可以通過犧牲精度的方法來迭代求解。具體見2009年姜碧野的論文。

原理是這樣的：
a11 * x1 + a12 * x2 + ... + a1n * xn = b1 可以變化成

x1 = 1/a11 * (b1 - a12 * x2 - a13 * x3 - .. a1n * xn);

如果x1 ... xn已經(jīng)估計(jì)了一個(gè)值，那么通過上式進(jìn)行進(jìn)一步迭代就會(huì)得到更精確的解。
如果有解的話，最后一定是收斂的。
但是如果無解，或者有多個(gè)解，結(jié)果怎么樣我就不知道了。。。。

這種方法叫做 jacobi 迭代法，復(fù)雜度O(k * n^2)。

缺點(diǎn)是后期收斂速度很慢。

有一種改進(jìn)方法，叫做代數(shù)多重網(wǎng)格法（Algebraic Multi-Grid）。迭代過程中可以逐漸縮小大型矩陣的規(guī)模，使網(wǎng)格由細(xì)變粗。

具體細(xì)節(jié)有待鉆研。      摘要: 這場(chǎng)比賽發(fā)揮的不錯(cuò)，rank 33，但是unrated。。。。 題目都很有意思，這里回憶一下  閱讀全文 總之，這場(chǎng)練習(xí)賽是有史以來做的最不好的。做了四個(gè)小時(shí)大家就草草收?qǐng)隹偨Y(jié)了。

說實(shí)話確實(shí)是受心情影響了，而且還是學(xué)弟噴我。。。。 不過算了，清者自清，想踩我先努力到位再說！

比賽開始，xy看A題，孟神看最后一題，我看題目描述短的一題。
其實(shí)這樣做不是很妥，因?yàn)锳題和J題未必就很水，所以以后應(yīng)該一個(gè)人負(fù)責(zé)一個(gè)區(qū)間，然后挑短的看！

A題是構(gòu)造題，不難寫10多分鐘就1A了。

接下來G題也有若干人過，題意是求[0，n]中K進(jìn)制和-K進(jìn)制表示一樣的數(shù)的個(gè)數(shù)。
孟神確認(rèn)這樣的數(shù)用K進(jìn)制表示后，奇數(shù)位一定是0，數(shù)位DP可搞。

但是隱隱覺得數(shù)位DP有點(diǎn)大材小用，而且一開始這么多隊(duì)過應(yīng)該不難。
不過沒細(xì)想，就敲了，交上去后WA。孟神上去對(duì)拍，xy給我講H題。

H題是給你一個(gè)字符串，求所有可以經(jīng)過重排列構(gòu)成回文串的子串的個(gè)數(shù)，N是3e5。
隱隱覺得是不是CF某場(chǎng)出過。。。。 當(dāng)時(shí)很沖動(dòng)的想了一個(gè)DP，后來發(fā)現(xiàn)是錯(cuò)的，當(dāng)時(shí)應(yīng)該和xy確認(rèn)一下就好了。。。。

G題對(duì)拍了寫了很長(zhǎng)時(shí)間，當(dāng)時(shí)隱隱覺得節(jié)奏不對(duì)，可是也沒別的題可敲（暴露出隊(duì)內(nèi)DPS不足的致命缺點(diǎn)，而且對(duì)拍應(yīng)該是最后手段）。發(fā)現(xiàn)數(shù)位dp想錯(cuò)了一個(gè)很重要的地方，改了依然wa。這是隱隱覺得是long long的問題，但是暫時(shí)沒有想到是哪里long long 用的不對(duì)，其實(shí)之間已經(jīng)想出了sqrt(n)的構(gòu)造算法，不過總覺得源程序改改就能過。。。。

期間H題我想到可以將52個(gè)字母的前綴和的奇偶hash成二進(jìn)制，然后存到map中。多虧了省賽的H。。。。 不久敲完，wa了一發(fā)，發(fā)現(xiàn)了long long的問題，然后再交，TLE。
10^7次map操作已經(jīng)超過了兩秒，我之前一直沒有意識(shí)到。。。。 這樣一直卡著兩題，xy確認(rèn)了E的題意，覺的是貪心，和我確認(rèn)了一發(fā)，我覺得靠譜，于是讓他搞，我調(diào)兩道題的錯(cuò)。

終于發(fā)現(xiàn)G題輸入沒用long long的sb錯(cuò)誤，于是上去改之，AC。。。當(dāng)時(shí)我還大吼了一下。。。。
H題改用hash代替map，wa了兩發(fā)不明原因，后來發(fā)現(xiàn)是hash的插入過程寫錯(cuò)了一點(diǎn)點(diǎn)。。。。

這暴露了另一個(gè)問題，隊(duì)內(nèi)的其他人看不懂我代碼。。。 隊(duì)內(nèi)沒有統(tǒng)一模板的習(xí)慣。。。。
E題xy說有反例，我說改成背包不是問題。但是要輸出DP路徑，狀態(tài)是三維的，十分惡心。。。最后沒有心情敲了。。。。

還是做題量偏少。。。。C題一開始覺得是二分答案，但是分?jǐn)?shù)精度很難控制，后來發(fā)現(xiàn)可以貪心，隨手交一發(fā)，wa，于是我敲E了。

讓xy和孟神查錯(cuò)，不久他們舉出了一個(gè)反例，于是我馬上確認(rèn)了這是斜率DP。。。。然后我當(dāng)時(shí)很累了。。。于是就開會(huì)總結(jié)了。。。

目前主要有這么幾個(gè)問題：
1. 卡題的時(shí)候查錯(cuò)效率太低。。。。隊(duì)友不熟悉我代碼，隊(duì)內(nèi)沒有統(tǒng)一模板，盲目對(duì)拍。。。
2. 開題草率，依然是這個(gè)問題。 G題一開始用了麻煩做法，H沒有正確估計(jì)時(shí)間，C題E題用了錯(cuò)誤的貪心，沒有去證明正確性。
3. 組隊(duì)模式有缺陷，卡題逆風(fēng)乏力，后期乏力。目前隊(duì)內(nèi)還是過于依賴我主敲代碼，但是當(dāng)我接連卡題的時(shí)候，節(jié)奏就全沒有了，也缺乏足夠的冷靜。后期攻難題也依賴平均水平和隊(duì)友的綜合實(shí)力，這個(gè)需要慢慢磨合。

由于昨天我的不冷靜言行，無意傷害了很多人。現(xiàn)在我將一些不妥的言論刪除，大家寬宏大量，不要在意！

我誠懇的向黑龍江所有ACMer致歉，無心之言，多加包涵！

也十分感謝"無"和“退役很久了”兩位朋友對(duì)我的規(guī)勸，也感謝為我說話，替我著想的一些朋友，這些情誼鄙人有生難忘！

至于匿名惡意攻擊我的人，咱們兩不相欠！

最后祝愿所有ACMer都能實(shí)現(xiàn)自己的夢(mèng)想！