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