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


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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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


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

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


2。開關(guān)問題

3。求期望

     摘要:   閱讀全文

     摘要: topcoder 577  閱讀全文

     摘要:   閱讀全文

     摘要: 。。。  閱讀全文

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

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

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

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

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

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

缺點是后期收斂速度很慢。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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