算法学社
記錄難忘的征途
posts - 141,comments - 220,trackbacks - 0
大大小小的现场赛我一共经历过14场了,不论什么挫折,于我只是过眼云烟,正如本次这场惨败。

之前组队联系赛做过N场,都是三人一机,各种练习几乎从未出过前十,于是信心爆棚。。。 这次比赛可以说完全暴露了我们队的弱点。

比赛流水账:
比赛开始xy从前往后看,孟神从后往前看。我听到xiaodao在后面说H,我就看了一下H,乍一看觉得是水题,于是上去敲,敲完了没过样例,发现题目读错了。于是下来在想,也奠定了整场比赛的基调。
xy看A花了一些时间,6分钟有队伍1A,xy给我讲了一下,两个和坐标轴平行的矩形求交,一看很简单我就敲了,13min 1A。
然后就是噩梦的开始。
B题是1000个与坐标轴平行的线段,相交即连通,询问1和n是否连通。我觉得有一定代码量。
C题是定义形如([A-Z])的字母,然后做多串匹配。当时xy给我讲完题后,题意没有确定清楚,认为是去掉括号裸AC自动机。
于是开始敲之,敲完之后,开始测。这时xy提醒([A-Z])代表一个字母,我当时很蛋疼,这时xy和孟神确定F是水题,于是换xy敲F。
不久之后F过掉,46min 1A。这时已经失去了领先优势。我认为C改一下就OK了,于是上去改C。这时我又读错题了,智商不能再低。
我认为the number of word的意思是the kinds of word。实际上是一个模式串有30个word。我以为字母表最多30,当然就暴栈。我怒交了5次,都暴栈。。。。
期间孟神确定了H,G可做,G是模板题,缩点之后spfa,有些麻烦,而且这类题应该是我写,于是让孟神敲H。孟神的H花了很长时间才过样例,我给他做了一个数据,cha掉了。。。
H题就是第二个大坑,一个前期很多队过的题目,孟神卡了N久。。。期间我交C多次不过,这时孟神终于调通了样例,交了一次,TLE。。。。 我震惊了,于是让孟神帮我看C。。。
这时已经卡住两题了,xy上去搞B,我想再tm卡一题就不用玩了。这时通知了加了一个K题。但是我们已经上头了,谁也不愿意去看K...
赛后xy和我说他不知道B题的线段和坐标轴平行。。。队内的交流实在是不够,大家都太自信,而忘了做之前和别人交流题意和做法。
不久之后,xy交B,wa了,当时我万念俱灰。。。。 xy发现"No"被打成"NO"。改之,再交。我实在是心提到嗓子眼,幸亏最后返回yes,138分钟2A。
中间C和H卡了一个小时以上。。。。
孟神告诉我C题的真实题意,我觉得暂时不可做。(赛后知道,可以用O(n)的空间和O(m*lgn^2)的时间用SA进行多串匹配。。。锤桌。。。劳资写SA很稳。。)
K题很水,140min 1A。
于是开I题,I题是在一个有根树里面DP。我一开始理解对了,敲了一阵,后来以为是拓扑图。
不久之后拓扑图版本的I题敲完,确认了若干遍,交之,wa,我了个大艹。。。实在想不出哪里wa,上趟厕所冷静一下,回来之后知道一个skill需要若干个skill同时学会才行
(其实根本不是这里错。。。),改之再交,WA,弃之,敲H。这时已经压了3题,有点急躁。
H是判断一个串,是否满足A和数量和B相等,C和D相等,E和F相等,并且子串都不满足这样的性质。我换了一个栈的做法,有些难写,不过还算顺利,198min 2A。不过在I上浪费了一段时间。此时排名已经惨不忍睹,手上还压着两题,但是没办法,怒开新题。
xy看J题,找第N大的 (x,y)满足(x^2 mod y == 1) and (y^2 mod x == 1)。打表找规律,交之,wa。。。。 发现表打小了,再交,223min2A。。。
期间我不知道I题是否有环,认为题意描述不清,询问,得到“no response.”,习惯了,哈工程的裁判都这样。。。问“skill tree”是否是"a real tree",回答"what is a real tree?"。
我了个大艹。。。消遣我,我差点就回了一个"you son of a bitch"。忍住了情绪,重新读题,发现还真tm是个有根树。CF一般都把数据规格写到input部分,做了近百场CF还真不习惯。。。
不过那还能错哪,拓扑图包括了有根树的情况。怀疑数据有问题。。。 拓扑图DP我是不可能写错的。。。因为从来没错过。。。。
这时封榜了,怒敲G题,有点慌,不过还好263min 1A。然后重写有根树版本I,278min 3A,当时我就震惊了,速度交了一个以前版本的。。。返回WA,十分不解。
然后重搞C,奇葩的用vector存字母表,时间不够,没调出来。。。。(调出来也超时,除非用balanced tree存 岛君说用map。。。 很有道理Orz!)

8题金奖倒数第二,xiaodao 10题夺冠Orz....
dshawn 9题第二,安可9题第三

I题莫名其妙的WA。。。
H题孟神被坑
C题坑我一整场,最后xiaodao裸AC自动机卡过,我艹。。。

通化再战,不拿金誓不为人!
posted @ 2013-05-21 01:52 西月弦 阅读(1429) | 评论 (37)编辑 收藏
     摘要: 给出一个“一笔画”轨迹,没有线段重叠。求这个轨迹将平面分成了几部分。  阅读全文
posted @ 2013-05-06 14:07 西月弦 阅读(267) | 评论 (0)编辑 收藏
我擦擦擦擦擦擦擦擦擦擦擦擦擦擦擦擦.....


最近真是忙成狗,要是这个节奏真是要跪啊。
真是对不起关注我博客的同学。
最近在忙什么呢?

1. 邢老师的项目
2. 选修课大作业
3. 同学的毕设
4. 找实习

真是牵扯精力。。。
其实说白了,还是时间分配有问题。。。

所以。。。 为了区域赛不坑队友。。。
哥决定!

坚持刷题写博客,以后的博文前面都写上【奋战2013regional】

大家监督!!!
posted @ 2013-05-05 14:14 西月弦 阅读(353) | 评论 (2)编辑 收藏
好像bzoj有些题是看不到 & 做不了的?
包括我以前做过的一些题。
听说得捐款或者出题,有没有知道详情的。。。
posted @ 2013-03-26 15:44 西月弦 阅读(409) | 评论 (1)编辑 收藏

题目描述:

   1...n的排列 p1 ... pn ,位置 i 是good,当且仅当 abs(pi - i) = 1。 问大小为N ,恰好有K个位置是good的排列是多少?

算法分析:

   非常好的一道题,O(n^2) DP搞之。
   
   dp[n][k][p][q] 代表 大小为n,有k个good位置,p = 1代表 倒数第二个位置是n - 1 ,p = 2代表倒数第二个位置是 n, p = 0代表其他,q代表最后一个位置。

    然后转移不难想。。。。

 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 西月弦 阅读(297) | 评论 (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 西月弦 阅读(1516) | 评论 (1)编辑 收藏
ACM方面还真是进步不少。刷了一年CF和TC都到了黄的水平,看了明年变红不是问题呀,哈哈。。。

大二下学期各种努力各种刷题,什么线段树,Splay,可持久化数据结构。。。 暑假也是体验了一把真正的集训,天天宅在实验室刷regional题,各种单挑多校,其中一半以上守住了第一页~~实力达到了巅峰。。

开了这个博客,暑假和大二下的时候孜孜不倦的写博客。到大三就没怎么认真写了 -.-,主要就是以AK codeforces为主业,没怎么刷OJ。。。

除了学习各种高级算法以外还了解了其他的编程语言。什么Java,python也会用来写简单的题目了,可惜还不是很熟练,更别提精通了。
其他Ruby,Javascrit,Scheme,TeX,Haskell也有简单的认识了。

Linux呢也用了一年,10月份折腾了gentoo一直用到现在,感觉还好。XFCE什么的有好有坏,好的方面是轻量级而且稳定,从来没有遇到过crash,配置什么的相当清楚和方便,不用折腾。。。坏处就是基于XFCE的各种gui软件不是难看就是难用,唯一满意的就是屏幕保护了。其他什么Orage,Screen Shooter,用户体验简直烂得。。。 我擦。。

这个糟烂笔记本的集显断了我玩游戏的念想。。。。

还收获女友一枚。。。。

还有ACM regional silver prize 两枚。。。和各种好朋友~~
posted @ 2012-12-31 13:52 西月弦 阅读(648) | 评论 (2)编辑 收藏
     摘要: zju 3666  阅读全文
posted @ 2012-12-23 14:04 西月弦 阅读(392) | 评论 (0)编辑 收藏
嘛,所谓“用户体验”这种东西是不是在Gentoo里面根本没有啊!!!! 坑爹啊!!!!(捶桌!!!)

经常就是。。。 手足无措的不知道自己电脑的哪个硬件该装哪个驱动!!!!
尼玛该上网啦,为毛上不了啊!! dhcpcd的一行配置有冲突你就得查半天啊!!!!
经常就是中文乱码啊。。。。。。。 游戏玩不了啊。。。。。。。 截图软件太坑爹啊。。。。。。 时间改不了啊。。。。。。


每一项都要花费大量时间去修复它。。。。 何必呢。。。。 Linux DE真是。。。。sigh。。

其实Linux DE好的地方就是些代码比较爽(命令行用起来方便),而且Gnome和KDE有一些华而不实的3D效果嘛...

其实Windows也可以配置成这样,只是我没有用心去开发。。。。

假期折腾个双系统,就这么定了。。。
posted @ 2012-12-16 16:26 西月弦 阅读(400) | 评论 (0)编辑 收藏
     摘要: topcoder SRM 563  阅读全文
posted @ 2012-12-09 03:17 西月弦 阅读(585) | 评论 (0)编辑 收藏
仅列出标题
共15页: 1 2 3 4 5 6 7 8 9 Last