大大小小的現(xiàn)場賽我一共經(jīng)歷過14場了，不論什么挫折，于我只是過眼云煙，正如本次這場慘敗。
之前組隊(duì)聯(lián)系賽做過N場，都是三人一機(jī)，各種練習(xí)幾乎從未出過前十，于是信心爆棚。。。 這次比賽可以說完全暴露了我們隊(duì)的弱點(diǎn)。
比賽流水賬：
比賽開始xy從前往后看，孟神從后往前看。我聽到xiaodao在后面說H，我就看了一下H，乍一看覺得是水題，于是上去敲，敲完了沒過樣例，發(fā)現(xiàn)題目讀錯(cuò)了。于是下來在想，也奠定了整場比賽的基調(diào)。
xy看A花了一些時(shí)間，6分鐘有隊(duì)伍1A，xy給我講了一下，兩個(gè)和坐標(biāo)軸平行的矩形求交，一看很簡單我就敲了，13min 1A。
然后就是噩夢的開始。
B題是1000個(gè)與坐標(biāo)軸平行的線段，相交即連通，詢問1和n是否連通。我覺得有一定代碼量。
C題是定義形如([A-Z])的字母，然后做多串匹配。當(dāng)時(shí)xy給我講完題后，題意沒有確定清楚，認(rèn)為是去掉括號(hào)裸AC自動(dòng)機(jī)。
于是開始敲之，敲完之后，開始測。這時(shí)xy提醒([A-Z])代表一個(gè)字母，我當(dāng)時(shí)很蛋疼，這時(shí)xy和孟神確定F是水題，于是換xy敲F。
不久之后F過掉，46min 1A。這時(shí)已經(jīng)失去了領(lǐng)先優(yōu)勢。我認(rèn)為C改一下就OK了，于是上去改C。這時(shí)我又讀錯(cuò)題了，智商不能再低。
我認(rèn)為the number of word的意思是the kinds of word。實(shí)際上是一個(gè)模式串有30個(gè)word。我以為字母表最多30，當(dāng)然就暴棧。我怒交了5次，都暴棧。。。。
期間孟神確定了H，G可做，G是模板題，縮點(diǎn)之后spfa，有些麻煩，而且這類題應(yīng)該是我寫，于是讓孟神敲H。孟神的H花了很長時(shí)間才過樣例，我給他做了一個(gè)數(shù)據(jù)，cha掉了。。。
H題就是第二個(gè)大坑，一個(gè)前期很多隊(duì)過的題目，孟神卡了N久。。。期間我交C多次不過，這時(shí)孟神終于調(diào)通了樣例，交了一次，TLE。。。。 我震驚了，于是讓孟神幫我看C。。。
這時(shí)已經(jīng)卡住兩題了，xy上去搞B，我想再tm卡一題就不用玩了。這時(shí)通知了加了一個(gè)K題。但是我們已經(jīng)上頭了，誰也不愿意去看K...
賽后xy和我說他不知道B題的線段和坐標(biāo)軸平行。。。隊(duì)內(nèi)的交流實(shí)在是不夠，大家都太自信，而忘了做之前和別人交流題意和做法。
不久之后，xy交B，wa了，當(dāng)時(shí)我萬念俱灰。。。。 xy發(fā)現(xiàn)"No"被打成"NO"。改之，再交。我實(shí)在是心提到嗓子眼，幸虧最后返回yes，138分鐘2A。
中間C和H卡了一個(gè)小時(shí)以上。。。。
孟神告訴我C題的真實(shí)題意，我覺得暫時(shí)不可做。（賽后知道，可以用O(n)的空間和O(m*lgn^2)的時(shí)間用SA進(jìn)行多串匹配。。。錘桌。。。勞資寫SA很穩(wěn)。。）
K題很水，140min 1A。
于是開I題，I題是在一個(gè)有根樹里面DP。我一開始理解對了，敲了一陣，后來以為是拓?fù)鋱D。
不久之后拓?fù)鋱D版本的I題敲完，確認(rèn)了若干遍，交之，wa，我了個(gè)大艸。。。實(shí)在想不出哪里wa，上趟廁所冷靜一下，回來之后知道一個(gè)skill需要若干個(gè)skill同時(shí)學(xué)會(huì)才行
（其實(shí)根本不是這里錯(cuò)。。。），改之再交，WA，棄之，敲H。這時(shí)已經(jīng)壓了3題，有點(diǎn)急躁。
H是判斷一個(gè)串，是否滿足A和數(shù)量和B相等，C和D相等，E和F相等，并且子串都不滿足這樣的性質(zhì)。我換了一個(gè)棧的做法，有些難寫，不過還算順利，198min 2A。不過在I上浪費(fèi)了一段時(shí)間。此時(shí)排名已經(jīng)慘不忍睹，手上還壓著兩題，但是沒辦法，怒開新題。
xy看J題，找第N大的 (x,y)滿足(x^2 mod y == 1) and (y^2 mod x == 1)。打表找規(guī)律，交之，wa。。。。 發(fā)現(xiàn)表打小了，再交，223min2A。。。
期間我不知道I題是否有環(huán)，認(rèn)為題意描述不清，詢問，得到“no response.”，習(xí)慣了，哈工程的裁判都這樣。。。問“skill tree”是否是"a real tree"，回答"what is a real tree?"。
我了個(gè)大艸。。。消遣我，我差點(diǎn)就回了一個(gè)"you son of a bitch"。忍住了情緒，重新讀題，發(fā)現(xiàn)還真tm是個(gè)有根樹。CF一般都把數(shù)據(jù)規(guī)格寫到input部分，做了近百場CF還真不習(xí)慣。。。
不過那還能錯(cuò)哪，拓?fù)鋱D包括了有根樹的情況。懷疑數(shù)據(jù)有問題。。。 拓?fù)鋱DDP我是不可能寫錯(cuò)的。。。因?yàn)閺膩頉]錯(cuò)過。。。。
這時(shí)封榜了，怒敲G題，有點(diǎn)慌，不過還好263min 1A。然后重寫有根樹版本I，278min 3A，當(dāng)時(shí)我就震驚了，速度交了一個(gè)以前版本的。。。返回WA，十分不解。
然后重搞C，奇葩的用vector存字母表，時(shí)間不夠，沒調(diào)出來。。。。（
調(diào)出來也超時(shí)，除非用balanced tree存 島君說用map。。。 很有道理Orz?。?br />
8題金獎(jiǎng)倒數(shù)第二，xiaodao 10題奪冠Orz....
dshawn 9題第二，安可9題第三
I題莫名其妙的WA。。。
H題孟神被坑
C題坑我一整場，最后xiaodao裸AC自動(dòng)機(jī)卡過，我艸。。。
通化再戰(zhàn)，不拿金誓不為人！
摘要: 給出一個(gè)“一筆畫”軌跡，沒有線段重疊。求這個(gè)軌跡將平面分成了幾部分。
閱讀全文
我擦擦擦擦擦擦擦擦擦擦擦擦擦擦擦擦.....
最近真是忙成狗，要是這個(gè)節(jié)奏真是要跪啊。
真是對不起關(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有些題是看不到 & 做不了的？
包括我以前做過的一些題。
聽說得捐款或者出題，有沒有知道詳情的。。。
題目描述：
1...n的排列 p1 ... pn ，位置 i 是good，當(dāng)且僅當(dāng) abs(pi - i) = 1。 問大小為N ，恰好有K個(gè)位置是good的排列是多少？
算法分析：
非常好的一道題，O(n^2) DP搞之。
dp[n][k][p][q] 代表 大小為n，有k個(gè)good位置，p ＝ 1代表 倒數(shù)第二個(gè)位置是n - 1 ，p = 2代表倒數(shù)第二個(gè)位置是 n， p = 0代表其他，q代表最后一個(gè)位置。
然后轉(zhuǎn)移不難想。。。。
1 #include<iostream>
2 #include<cstdio>
3 using namespace std;
4 #define re(i,n) for(int i = 0; i < n; i++)
5 typedef long long ll;
6 const int N = 1005;
7 const int mod = (int)1e9+7;
8 ll dp[N][N][3][3];
9 int main(){
10 int n,k;
11 cin >> n >> k;
12 dp[1][0][0][1] = 1;
13 dp[2][0][1][2] = 1;
14 dp[2][2][2][1] = 1;
15 for(int i = 3; i <= n; i++){
16 for(int k = 0; k <= i; k++) {
17 // * 2
18 re(p,2) re(q,3) dp[i][k][p][2] += dp[i-1][k][q][p+1];
19 re(q,3) dp[i][k][0][2] += dp[i-1][k][q][0];
20 // 2 1
21 if(k >= 2) re(q,2) dp[i][k][2][1] += dp[i-1][k-2][q][2];
22 // 2 0
23 re(q,3) dp[i][k][2][0] += dp[i-1][k][q][1];
24 if(k >= 1) re(q,3) dp[i][k][2][0] += dp[i-1][k-1][q][0];
25 // 0 1
26 dp[i][k][0][1] += dp[i-1][k][2][1] + dp[i-1][k][2][0];
27 if(k >= 1) dp[i][k][0][1] += dp[i-1][k-1][0][0] + dp[i-1][k-1][0][1] + dp[i-1][k-1][1][0];
28 // 1 0
29 re(q,2) dp[i][k][1][0] += dp[i-1][k+1][q][2] * (k + 1);
30 if(i - 2 - k >= 0) re(q,2) dp[i][k][1][0] += dp[i-1][k][q][2] * (i - 2 - k);
31 // 0 0 vs 2 1
32 ll &ans = dp[i][k][0][0];
33 if(k - 1 >= 0) ans += dp[i-1][k+1][2][1] * (k - 1) ;
34 if(i - 1 - k >= 0) ans += dp[i-1][k][2][1] * (i - 1 - k);
35 // cout<<"vs 2 1: "<<i<<" "<<k<<" "<<ans<<endl;
36 // 0 0 vs 2 0
37 ans += dp[i-1][k + 1][2][0] * k;
38 if( i - 2 - k >= 0) ans += dp[i-1][k][2][0] * (i - 2 - k);
39 // cout<<"vs 2 0: "<<i<<" "<<k<<" "<<ans<<endl;
40 // 0 0 vs * 2
41 // re(q,2) ans += dp[i-1][k+1][q][2] * (k + 1);
42 // re(q,2) if(i - 2 - k >= 0)ans += dp[i-1][k][q][2] * (i - 2 - k);
43 // 0 0 vs * 0
44 re(q,2) ans += dp[i-1][k+1][q][0] * (k + 1);
45 if(i - 3 - k >= 0) re(q,2) ans += dp[i-1][k][q][0] * (i - 3 - k);
46 // cout<<"vs * 0: "<<i<<" "<<k<<" "<<ans<<endl;
47 // 0 0 vs 0 1
48 ans += dp[i-1][k+1][0][1] * k;
49 if(i - 2- k >= 0) ans += dp[i-1][k][0][1] * (i - 2 - k);
50 // cout<<"vs 0 1: "<<i<<" "<<k<<" "<<ans<<endl;
51 re(p,3) re(q,3) dp[i][k][p][q] %= mod;
52 }
53 }
54 ll ans = 0;
55 re(q,3) re(p,3){
56 ans += dp[n][k][p][q];
57 // cout<<p<<" "<<q<<" "<<dp[n][k][p][q]<<endl;
58 }
59 // int a,b,c,d; while(cin >> a >> b >> c >> d) cout<<dp[a][b][c][d]<<endl;
60 cout << ans % mod << endl;
61 }
62
摘要: 對一個(gè)字符串S(初始為空)，有Q次操作(Q<=50,000)，操作分三種：
1. 在某個(gè)位置p后面插入一個(gè)長度不大于100的字符串。
2. 刪除一段字符[l,r]
3. 輸出在第k次操作時(shí)，字符串(S_l ... S_r) 插入的字符不超過1,000,000個(gè)。
閱讀全文
ACM方面還真是進(jìn)步不少。刷了一年CF和TC都到了黃的水平，看了明年變紅不是問題呀，哈哈。。。
大二下學(xué)期各種努力各種刷題，什么線段樹，Splay，可持久化數(shù)據(jù)結(jié)構(gòu)。。。 暑假也是體驗(yàn)了一把真正的集訓(xùn)，天天宅在實(shí)驗(yàn)室刷regional題，各種單挑多校，其中一半以上守住了第一頁~~實(shí)力達(dá)到了巔峰。。
開了這個(gè)博客，暑假和大二下的時(shí)候孜孜不倦的寫博客。到大三就沒怎么認(rèn)真寫了 -.-，主要就是以AK codeforces為主業(yè)，沒怎么刷OJ。。。
除了學(xué)習(xí)各種高級(jí)算法以外還了解了其他的編程語言。什么Java，python也會(huì)用來寫簡單的題目了，可惜還不是很熟練，更別提精通了。
其他Ruby，Javascrit，Scheme，TeX，Haskell也有簡單的認(rèn)識(shí)了。
Linux呢也用了一年，10月份折騰了gentoo一直用到現(xiàn)在，感覺還好。XFCE什么的有好有壞，好的方面是輕量級(jí)而且穩(wěn)定，從來沒有遇到過crash，配置什么的相當(dāng)清楚和方便，不用折騰。。。壞處就是基于XFCE的各種gui軟件不是難看就是難用，唯一滿意的就是屏幕保護(hù)了。其他什么Orage，Screen Shooter，用戶體驗(yàn)簡直爛得。。。 我擦。。
這個(gè)糟爛筆記本的集顯斷了我玩游戲的念想。。。。
還收獲女友一枚。。。。
還有ACM regional silver prize 兩枚。。。和各種好朋友~~
摘要: zju 3666
閱讀全文
嘛，所謂“用戶體驗(yàn)”這種東西是不是在Gentoo里面根本沒有啊！?。。?坑爹啊?。。。。ù纷溃。。。?br />
經(jīng)常就是。。。 手足無措的不知道自己電腦的哪個(gè)硬件該裝哪個(gè)驅(qū)動(dòng)?。。?！
尼瑪該上網(wǎng)啦，為毛上不了?。?！ dhcpcd的一行配置有沖突你就得查半天?。。。?！
經(jīng)常就是中文亂碼啊。。。。。。。 游戲玩不了啊。。。。。。。 截圖軟件太坑爹啊。。。。。。 時(shí)間改不了啊。。。。。。
每一項(xiàng)都要花費(fèi)大量時(shí)間去修復(fù)它。。。。 何必呢。。。。 Linux DE真是。。。。sigh。。
其實(shí)Linux DE好的地方就是些代碼比較爽(命令行用起來方便)，而且Gnome和KDE有一些華而不實(shí)的3D效果嘛...
其實(shí)Windows也可以配置成這樣，只是我沒有用心去開發(fā)。。。。
假期折騰個(gè)雙系統(tǒng)，就這么定了。。。
摘要: topcoder SRM 563
閱讀全文