ACM

自吐 & 自勉

Posted on by snoopy

今天百度最高奖, 看了下, 最终入围的五个团队有三个自己呆过, 拿奖的仨也呆过俩, 好多认识的人, cong~ (附: 拿奖的新浪微博消息) 他们都做的很赞, 自己曾经在这么好的团队, 耐不住性子, 做不出东西, 因种种原因离开, 开花结果自然无份

现在么, 好好做事, 手头事情也很有搞头, 那就好好搞吧, 皇天不负有心人 :P

自吐部分开始, 曾经有一个帖再引用了以前的一个段子 (原文见: 被诅咒的 Snoopy)

Me 13:23:45
我从 b 家离职后不久, b 家的碳酸饮料就免费了
我从 g 家离职后不久, 餐补就直接发钱了, 等我开学, 上海也是自助餐了
小强 13:25:56
你快点离开武大
Me 13:26:16
why?
Me 13:26:23
这样师弟师妹的伙食就有希望了?
小强 13:26:57
恩
小强 13:27:18
你离开acm acm就拿到金牌了
Me 13:28:20
…

我一定要把这个段子续下去:

* 2007 年夏离开武大 ACM 队, 该年秋天武大第一次拿区域赛金牌, 第一次进入世界总决赛
* 2008 年初进微软俱乐部, 该年夏令营活动被取消
* 2009 年初离开微软俱乐部, 该年夏令营活动恢复, 并增加 UCLA 夏令营
* 2009 年秋天回归百度, 过了一个月从普天搬西二旗, 自助碳酸饮料机被取消了
* 2011 年秋天离开百度, 半年后自己做废了的俩项目重新上线
* 2011 年秋天离开百度, 次年原团队拿百度最高奖

[zz] 追女孩好比做 OJ

Posted on by snoopy

本文系转载, 居然还有这个, 怎么我原来都没见过…

— 滑溜溜的分割线 —

开始的时候, MM 对我们的话无动于衷, 总是说 Compile Error, 这时候我们就要多多甜言蜜语一些啦, 比如换个语言 (编译器, c++, c, g++, 我都搞不清用哪个了… 反正基本有一个就能过)

然后呢, 女生就会嫌我们慢吞吞胖乎乎 (Time Limit Exceeded, Memory Limit Exceeded), 那么就试着换个方法 (比如我虽然确实喜欢 O(n) 或更小的, 但是第一遍一般都会写出来一个很偷懒的 O(n^3)…), 或者减肥吧 (不要轻易尝试 long long int…)

再然后呢, 女生开始芳心萌动了, 但是总对你说的话挑三拣四的, 动不动就是 Wrong Answer 之类的, 不要灰心不要气馁哦, 仔细检查~

还有, 其间千万记得不要做危险动作, 比如不要偷看女生的日记本啦, 更不能乱写乱画之类的, 要不然会报 Runtime Error 哦~~ (例如调用 open 或者 read 函数…)

时机差不多的时候就表白吧 :) 但是记得一定要找一个正确的方法哦~~ 要不然 MM 会嫌弃你的 Presentation Error 的…

Yeah, 是不是大功告成了? MM 看到你的最终表白之后, 就 Compiling… Online Judging… 然后激动的提示蓝色的 Accept 了~~

然后… 该做什么呢??

揉揉眼睛摇摇手, 做下一道题…

快排qsort的用法详解 (两年前的原创)

Posted on by snoopy

发信人: snoopy (阿排/好好玩ICPC~), 信区: ACM_ICPC
标 题: 快排qsort的用法详解
发信站: 珞珈山水BBS站 (Sat Apr 29 21:02:35 2006), 转信

很多人问这个东西.我以前也看了好久,今天翻到以前学快排的时候写的练习code,基本上
能覆盖绝大部分用法了.

里面有很多地方没判断相等的情况,按道理来说相等情况下应该返回0的,这个请看代码的
时候注意.我尽量保证代码不出错了.

下面的这些说明和问题都是个人原创,没查什么资料,所以不保证其完全正确性,在此表示个
人不对出现的问题负任何责任,大家WA了或者干吗的不要怪我,不过至少目前来说我用起来
是没问题的 :)

/*—————————————————————————-*/

** 关于快排函数的一些说明 **

qsort,包含在stdlib.h头文件里,函数一共四个参数,没返回值.一个典型的qsort的写法如下

qsort(s,n,sizeof(s[0]),cmp);

其中第一个参数是参与排序的数组名(或者也可以理解成开始排序的地址,因为可以写&s[i]
这样的表达式,这个问题下面有说明); 第二个参数是参与排序的元素个数; 第三个三数是
单个元素的大小,推荐使用sizeof(s[0])这样的表达式,下面也有说明 :) ;第四个参数就是
很多人觉得非常困惑的比较函数啦,关于这个函数,还要说的比较麻烦…

我们来讨论cmp这个比较函数(写成cmp是我的个人喜好,你可以随便写成什么,比如qcmp什么
的).典型的cmp的定义是

int cmp(const void *a,const void *b);

返回值必须是int,两个参数的类型必须都是const void *,那个a,b是我随便写的,个人喜好.
假设是对int排序的话,如果是升序,那么就是如果a比b大返回一个正值,小则负值,相等返回
0,其他的依次类推,后面有例子来说明对不同的类型如何进行排序.

在函数体内要对a,b进行强制类型转换后才能得到正确的返回值,不同的类型有不同的处理
方法.具体情况请参考后面的例子.

/*—————————————————————————-*/

** 关于快排的一些小问题 **

1.快排是不稳定的,这个不稳定一个表现在其使用的时间是不确定的,最好情况(O(n))和最
坏情况(O(n^2))差距太大,我们一般说的O(nlog(n))都是指的是其平均时间.

2.快排是不稳定的,这个不稳定表现在如果相同的比较元素,可能顺序不一样,假设我们有
这样一个序列,3,3,3,但是这三个3是有区别的,我们标记为3a,3b,3c,快排后的结果不一定
就是3a,3b,3c这样的排列,所以在某些特定场合我们要用结构体来使其稳定(No.6的例子就
是说明这个问题的)

3.快排的比较函数的两个参数必须都是const void *的,这个要特别注意,写a和b只是我的
个人喜好,写成cmp也只是我的个人喜好.推荐在cmp里面重新定义两个指针来强制类型转换,
特别是在对结构体进行排序的时候

4.快排qsort的第三个参数,那个sizeof,推荐是使用sizeof(s[0])这样,特别是对结构体,
往往自己定义2*sizeof(int)这样的会出问题,用sizeof(s[0)既方便又保险

5.如果要对数组进行部分排序,比如对一个s[n]的数组排列其从s[i]开始的m个元素,只需要
在第一个和第二个参数上进行一些修改:qsort(&s[i],m,sizeof(s[i]),cmp);

/*—————————————————————————-*/

** 标程,举例说明 **

No.1.手工实现QuickSort

#include <stdio.h>

int a[100],n,temp;

void QuickSort(int h,int t)
{
     if(h>=t) return;
     int mid=(h+t)/2,i=h,j=t,x;
     x=a[mid];
     while(1)
     {
         while(a[i]<x) i++;
         while(a[j]>x) j--;
         if(i>=j) break;
         temp=a[i];
         a[i]=a[j];
         a[j]=temp;
     }
     a[mid]=a[j];
     a[j]=x;
     QuickSort(h,j-1);
     QuickSort(j+1,t);
     return;
}

int main()
{
     int i;
     scanf("%d",&n);
     for(i=0;i<n;i++) scanf("%d",&a[i]);
     QuickSort(0,n-1);
     for(i=0;i<n;i++) printf("%d ",a[i]);

     return(0);
}

No.2.最常见的,对int数组排序

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

int s[10000],n,i;

int cmp(const void *a, const void *b)
{
     return(*(int *)a-*(int *)b);
}

int main()
{
     scanf("%d",&n);
     for(i=0;i<n;i++) scanf("%d",&s[i]);
    
     qsort(s,n,sizeof(s[0]),cmp);
    
     for(i=0;i<n;i++) printf("%d ",s[i]);
    
     return(0);
}

No.3.对double型数组排序,原理同int

这里做个注释,本来是因为要判断如果a==b返回0的,但是严格来说,两个double数是不可能相等的,只能说fabs(a-b)<1e-20之类的这样来判断,所以这里只返回了1和-1 [code lang="c"]#include <stdio.h> #include <stdlib.h> double s[1000]; int i,n; int cmp(const void * a, const void * b) { return((*(double*)a-*(double*)b>0)?1:-1); } int main() { scanf("%d",&n); for(i=0;i<n;i++) scanf("%lf",&s[i]); qsort(s,n,sizeof(s[0]),cmp); for(i=0;i<n;i++) printf("%lf ",s[i]); return(0); } [/code] No.4.对一个字符数组排序.原理同int [code lang="c"]#include <stdio.h> #include <string.h> #include <stdlib.h> char s[10000],i,n; int cmp(const void *a,const void *b) { return(*(char *)a-*(char *)b); } int main() { scanf("%s",s); n=strlen(s); qsort(s,n,sizeof(s[0]),cmp); printf("%s",s); return(0); }[/code] No.5.对结构体排序 注释一下.很多时候我们都会对结构体排序,比如校赛预选赛的那个樱花,一般这个时候都在 cmp函数里面先强制转换了类型,不要在return里面转,我也说不清为什么,但是这样程序会 更清晰,并且绝对是没错的. 这里同样请注意double返回0的问题 [code lang="c"]#include <stdio.h> #include <stdlib.h> struct node { double date1; int no; } s[100]; int i,n; int cmp(const void *a,const void *b) { struct node *aa=(node *)a; struct node *bb=(node *)b; return(((aa->date1)>(bb->date1))?1:-1); } int main() { scanf("%d",&n); for(i=0;i<n;i++) { s[i].no=i+1; scanf("%lf",&s[i].date1); } qsort(s,n,sizeof(s[0]),cmp); for(i=0;i<n;i++) printf("%d %lfn",s[i].no,s[i].date1); return(0); }[/code] No.6.对结构体排序.加入no来使其稳定(即data值相等的情况下按原来的顺序排) [code lang="c"]#include <stdio.h> #include <stdlib.h> struct node { double date1; int no; } s[100]; int i,n; int cmp(const void *a,const void *b) { struct node *aa=(node *)a; struct node *bb=(node *)b; if(aa->date1!=bb->date1) return(((aa->date1)>(bb->date1))?1:-1); else return((aa->no)-(bb->no)); } int main() { scanf("%d",&n); for(i=0;i<n;i++) { s[i].no=i+1; scanf("%lf",&s[i].date1); } qsort(s,n,sizeof(s[0]),cmp); for(i=0;i<n;i++) printf("%d %lfn",s[i].no,s[i].date1); return(0); } [/code] No.7.对字符串数组的排序(char s[][]型) [code lang="c"]#include <stdio.h> #include <string.h> #include <stdlib.h> char s[100][100]; int i,n; int cmp(const void *a,const void *b) { return(strcmp((char*)a,(char*)b)); } int main() { scanf("%d",&n); for(i=0;i<n;i++) scanf("%s",s[i]); qsort(s,n,sizeof(s[0]),cmp); for(i=0;i<n;i++) printf("%sn",s[i]); return(0); }[/code] No.8.对字符串数组排序(char *s[]型) [code lang="c"]#include <stdio.h> #include <string.h> #include <stdlib.h> char *s[100]; int i,n; int cmp(const void *a,const void *b) { return(strcmp(*(char**)a,*(char**)b)); } int main() { scanf("%d",&n); for(i=0;i<n;i++) { s[i]=(char*)malloc(sizeof(char*)); scanf("%s",s[i]); } qsort(s,n,sizeof(s[0]),cmp); for(i=0;i<n;i++) printf("%sn",s[i]); return(0); }[/code]

内网服务器终于弄好了

Posted on by snoopy

跟董老师说让把后面另两台机器的还原卡给去了, 然后都装上了 RHEL AS4, 按计划, 一台给内网做服务器, 提供 http, ftp, 打印 等服务, 同时准备留给未来做 PC2 的服务器, 另一台做 OJ 的测试服务器.

今天弄内网服务器弄了半天终于搞定, 麻烦死了, 最后发现问题都在那个该死的防火墙上.

一开始配打印机, 一开始没插电, 系统没找到, 等找到后设置成共享, 其他机器却不能访问 查了一下 Google/Baidu, 启动 samba 服务后还是不能访问, 以为是 samba 配置的问题, 查询了无数的东西后突然想是不是防火墙有问题, 关闭后就 OK 了, 无语. 按照 linuxsir 上的介绍, netstat 查看了一下 smb 的端口, 然后在防火墙中打开这两个端口, 搞定.

然后启动 ftp, 跟在外面那个服务器一样的启动 vsftpd, 写配置, 发现又不能访问, 怒… 通过查看 FlashFXP 的记录发现最后调用了一个很奇怪的端口, 65xxx, 想了一下估计又是被服务器拦了, 一怒之下索性把防火墙关了, 懒得去管端口设置了.

最后启动 http 服务, 这个很容易, 乱搞就搞定了, 不过默认好像是不启动 httpd 的, 又要自己开了一次. 一切搞定 :P

那台准备用来做 OJ 测试服务器的机器还没开始配, 看看明天上午有空就把 OJ 在上面跑起来.

从一条贼船跳到另一条贼船

Posted on by snoopy

终于是从 ACM/ICPC 中退役了, 虽然有很多不舍和不尽人意, 但是终究也还是要离开的, 自己一直很想避免说一些东西, 等心情好起来了再说说自己退役的感觉吧, 还是有很多能说的.

现在做 ACM/ICPC 的助理教练, 不过好像也还是有非常多的事情要做, 包括利用协会做活动, 然后又反过来组织协会.

现在跳上的是另一条贼船, MCM, 美国数模. 上个星期杨竞找我说想一起组队, 然后说让我赶快确定, 咨询了一下去年参加过 MCM 的小强, 然后决定参赛, $45 (实际上是$75) 的参赛费, 三个人平摊下来也就是一个人 25 刀, 拿 TopCoder 的美元回馈美国社会好了. 今天去图书馆借了两本书回来, 用周末看吧, 现在生活还是很好安排的, 周一到周五学习, 周六看 MCM, 周日弄 ACM/ICPC 的事情.

加油, 好好努力, 不用去奢望很多模棱两可的事情, 好好做好自己才是王道.

btw: 最近更新这里的频率可能不是很高了, 随手写的东西可能更多的往 Q-zone 和 LiveSpace 上贴了.

剧终, 青春散场~

Posted on by snoopy

原文发布在珞珈山水 BBS 的 ACM/ICPC 版, 这里也是原文, 不想修改了, 估计很可能这也是自己这个分类的最后一篇文章了.

剧终, 青春散场
–告别赛记 by snoopy

晚上的时候在 2006WHUACM 群公告里写下 “Moonmist解散退役” 的时候, 才真的意识到 “剧终” 这两个早就想好的告别词的伤人. 又是一个组建一年即解散退役的队伍, 只是, 去年的 KMXS 到后来我更多的是一个看客, 今年的 Moonmist, 自始至终, 都是我们三个主演.

11月19号中午出发去上海, 20号到达, 搞定住宿. 21号大巴把我们拉到上大新校区, 开幕式. 完了是教练会议, 第一次参加, 应该也是最后一次参加吧, 看了看是怎么抽签的, 自己也参与了提问, 问了一些在北京让我们失误的影响因素. 上海奖项设置是 10 金 20 银 30 铜, 比北京多, 但是因为队伍都很强, 其实局势更恶劣, 至少是金牌几乎是没希望的, 而北京冲金是有很大空间的, 最后定位是银牌保本, 最好能靠前, 能拿金牌就赚翻了.
中午吃完饭后去看了看比赛场地, 在一个大体育馆里, 一共 116 个队, 赛场安排的非常有气氛, 我们在靠中间的位置, 能对场上局势有比较好的把握.

下午练习赛, 3题有2个是简单题, 结果都被我抢了, 剩下的那个太郁闷, 到最后也没出来, Tank还说键盘都没摸到, 要敲敲玩玩找一下手感. 练习赛后是 SUN 的活动, 算大学技术日了吧, 介绍了一下 Solaris 和 SUN Studio, 也算是为后来人做一点基础培训, 毕竟从今年的西安开始所有大陆赛区都要改用这两个东西了. 当时 Moonmist 的人都是笑笑, 对我们一点影响没有, 我们不会参加以后的比赛了, 除非是进 Final, 不过 Final 不是那么好进的, 进了 Final 也未必是 Solaris, 即使参赛, vim + gEdit 的使用跟系统一点关系都没, 特别是现在 Solaris 也是用的 GNOME.

21号晚上招待晚宴, 上大很奇怪的把招待晚宴放在练习赛后而不是正式比赛后. 没有比赛, 没有成绩, 吃饭的心情依然是沉重的, 没喝酒, 也不敢. 晚上早早睡下, 为第二天准备, 不知道是不是因为还是害怕是自己最后一场比赛的原因, 半夜无光无声的宾馆房间内醒了好几次看时间, 确认没到起床的时间又草草睡下.
22号正赛, 原定 9:30 的进场推迟到了几乎 9:50, 入场后以为要推迟比赛开始的也并没发生, 宣布比赛开始的也只是现场的一个 Volunteer. Moon 拆密码信封登陆系统开 PC^2, 我拆赛题信封并分发. 10题, 按老规矩我从前面开始, Moon 后面, Tank 中间.

我看完 A 后就立即判断是个简单题, 就是上海赛区的决赛选拔规则, 过 k 题可以进一个队, 参见过 Final 并且前 20 名加一个队, 举办了 Local Contest 的加一个队, 抉择一下决定后面题目不看了, 直接上去敲, 看题的任务交给 Moon 和 Tank. 很快敲完, 这个时候场上已经有队过这题了, 交了后 WA, 立马想起估计是我对题目一个细节理解有问题了, Sample 给的极具欺骗性, 同一个学校过 k 题的如果有多个队伍也只能是有一个队能以这种形式参加决赛, 完全遵循上海的规则, 加了个判断后提交 Yes, 第一个红色的气球送来, 我暗暗骂了自己一下干吗要怀疑规则, 既然都说是上海规则了那就是跟实际情况完全一致而不是有修改.

Moon 和 Tank 分别交流了一下题目意思, 看懂了 I 的题意但是不好写. Tank 看的 D 题意也简单, 平面上 n 个点, 画一个矩形使落在矩形边线上的点最多, 离散化后其实就是在一个 n*n 的棋盘上操作, 但是 n<=100 的数据量我只能想到 n^4 的算法, 怕超时也先放下, 看其他的题. 我看完 B, C 后 Tank 看完 E, Moon 看完 H, 但是交流后都没好想法, 而赛场上这个时候过 C, D, I 都有, 并且 C, D 居多. 我跟 Moon 说清楚 C 的题意后对题目数据理解产生分歧, 因为从题意来理解输入的应该是一个无根树, 只要 dfs 一次即可, 而数据输入说是 10 万的点 100 万的边. E 交流后 Moon 判断是一个第 k 短路径, 但是写起来很烦, 其他题都太长而暂时没看懂. 把 C 的题意重新读一遍并讨论后认定题目数据在唬人, 输入只可能是一个无根树, 最多是有自环, Moon 上去写的时候害怕堆栈溢出, 准备手工实现递归堆栈, 但是太烦还是放弃直接写的递归, 交上去没有 RE 而是 WA, 修改一个小细节后返回 Yes, 第二个白色的气球也来了. Moon 做 C 的同时 Tank 和我在推 I 的杨辉三角, Tank 给了一个 O(n) 的累加式, 考虑 n 是 10^9 的数量级的所以我们将其化简到了 p + n%p 级, 但是 Tank 上去写后调了几个自己的数据发现就有问题, 于是下来. Moon 开始上去写 E 的第 k 短路, 因为是写的很熟的算法, 所以 Tank 对 Moon 也很有信心, 我不熟悉图论但是觉得写起来可能会非常的占机器, 不过既然没题敲, 也只能这样了. 比赛的时候发现真的还是会紧张, 我在不停的上厕所, 回来看剩下的题, 都很长, 并且心里有些烦, 都没能看下去, 不过题目本身也很难, 所以还没造成太坏的影响. Tank 推 I 没想法, 我说具体数学上应该有, 于是翻了一整章最后在一个习题上发现一个公式, 感觉会有用, 给 Tank 后他再看了一些定义再开始化简, 把时间复杂度减低. 我实在没题做问了 D 类似一个问题 (矩阵里求小矩阵使矩阵内数值和最大) 的 n^3 的加速算法, 知道 n^3 做法后觉得无法套用, 并且看场上那么多人过决定写 n^4 的去水, 因为也只能想到这个算法了, 并且我是优化后的, 是系数远小于 1 的 n^4 记忆化搜索. Judge 在 PC^2 上有提示说 B 的 Sample 有问题, 不过看了后认定就算有问题我们也没法拿出好的算法, 只能是16! 级别的, 最多也只是 16!/8!. 我很快敲完 D 后提交, 居然直接返回的 WA, 没有 TLE, 这时 Moon 提醒我直接的扫描有没有多算点或者少算点, 略加思索有发现我考虑的只是枚举矩形左上角和右下角, 右下我有判重, 而坐上没有判重, 加了一个修正后就 Yes 了, 第三个土黄色的气球. 刷了一下 Rank, 大概在银牌和铜牌交界的地方, 很玄. Tank 推出 I 的公式, 上去写但是错了, 这时时间不是很多了, 我跟 Moon 说如果 E 不好写就准备放弃吧, 毕竟赛场上还没一个队过这题, 我没看 Rank, 但是猜应该也没太多队做, 不过这种图论题都是想到做法就很简单的, 何况 Moon 也是写的多了, 但是写太久了似乎也有问题了. Tank 跟我说了 I 的思路, 并给了我最新的打印出来的程序, 不过我看了看觉得很麻烦, 同时 Tank 说的做法似乎很简单, 于是准备自己写, 才写完一半 Tank 那边已经返回了 Yes. 第四个淡黄气球送来的时候已经是只剩下 40 分钟了, 看了看封 Board 时的 Rank, 当时过 4 题的有 18 个队, 最后估计加上后来也过 4 题的我们在大概 20 的样子, 银牌是一定的了. 这时分析了一下场上局势, 我们的 B 依然没想法, Moon 写的 E 最后说是数据有写反一列, 不过太迟了也调不出来, 我站起来看过的最多的也只是 J 了. 很快看完那个一直没人看完的 J 题的输入输出后觉得像是一个差分约束系统, 跟 Moon 和 Tank 说了后觉得也有理, 一起看完题我就在听讨论了, 因为知识面的问题, 图论我几乎为 0. 不过 J 还是有很多细节问题, 即使时间不多也还是要仔细讨论, 等 Moon 上去敲代码的时候 Tank 和我都在两边看着, 给 Moon 信心, 同时也注意看程序中的书写问题, 到最后的时候已经是无法在比赛终止之前写完了, 并且 Moon 和 Tank 发现做法中存在的问题而停了下来. 我坐在一边不停的在纸上随便乱写, 脑中想的只是还有不到 10 分钟我们就要退役了, 我们的第二场比赛也是告别赛就要这么完了. 最后还是没能发生奇迹, J 有太多的细节问题需要处理的, 最后还剩下不到一分钟的时候站起来看了看四周, 后面的 H-E-A-T 也过了 4 题, 并且罚时应该要比我们少, 和平时的练习差不多. 比赛完了马上就是颁奖, 等了很久, 等的非常急. Silence 是 3 题, 不过他们的罚时太多了, 估计也只能是铜牌了. 我们 4 题, 从我们最后看到的封 Board 的情况来看大概是 20 左右吧, 银牌是跑不掉的, 并且从最后场上气球情况来看, 金牌应该还是要 5 题或者还要求速度快的. 最后 wmzhou 宣布结果的时候从后面往前面念, 每念过去一个我们就要兴奋一把, 说明我们的名次会更靠前, 不过最后还是没能有不现实的事情发生, 我们 16, 这还是前面有带 * 参赛不参与排名队伍情况下的. 我们还是没能突破我心里一直期盼的那个槛, 没能在这个赛季拿到一块金牌或者是进 Final. 不过从学校的角度来看, 我们已经在书写历史了, 虽然 Silence 在我们前面过的三题, 但是我们是第一个在正赛中过 4 题的队伍, 并且是 03 北京 Nova 后的第二块银牌, 这块银牌拿的更加吃力. Moonmist 也将会是武大 ACM/ICPC 历史上的重要一页, 我们也是历史上最好的队伍之一. 只是, 我们没能像四年前的 Nova 一样能延续下来, 不能不说是一个遗憾. 同时, 我们也衷心的希望能尽快有后来的人继续超越我们, 往更高的目标冲刺, 而不是让我们成为一个和四年前那个两题/银牌的魔咒一样. 祝福 Moonmist 的三个人, We are the Moonmist, We are the future~. 祝福 Moon, 希望读研的日子里能变得更强, 有空的时候也过来带带 WHUACM 后面的小朋友们吧, 祝福 Tank, 希望明年你能如愿到达北方, 到你想到的地方, 和你想在一起的人在一起, 祝福自己, 希望明年此时我已经能拿到一个比较好的 Offer 去实习工作了吧, 并且最好不要丢集训队的脸, 能有一个比底线更好的 Offer. 对我而言, 保研已经是几乎不可能的事情了, 为了前途, 我需要更多的实践来让自己在找工作的时候有更好的竞争力. 所以, Snoopy 这个 id 在 ACM/ICPC 中应该也是要归隐了吧, 或者是永别. 从高一开始玩 NOIp, 到现在, 也快 6 年了吧, 可惜自己几乎是一事无成, 在大牛遍地的 OI 界和 ACM/ICPC 界, 不过是一个匆匆过客. 对 WHUACM 的一腔热血, 那么多的规划, 应该也是永远无法实现了吧, 不过希望能快点把自己一些希望能实现的东西留给后面的人吧, 毕竟我们走了太多弯路, 希望后面的人能更顺利的在更需要耗费精力的地方努力. 对 Snoopy, ACM/ICPC 已经剧终, 青春散场, 留下一地狼藉. 刚刚 MasT 还说我其实也创造了一个记录, 除了是目前武大 ACM/ICPC 队内呆的最久(虽然不是参赛最多)的一个外, 也是Honorable Mention 拿的最多的, sigh~, 希望这个记录不要有人去试图打破.

POJ 300题纪念

Posted on by snoopy
snoopy–=WHU.[Moonmist].Snoopy=

Last Loginned Time:2006-11-18 13:49:10.0

Rank: 232
Solved: 300
Submissions: 578
School: Wuhan University
Email: whusnoopy@gmail.com

Solved Problems List :
1000 1001 1002 1003 1004 1005 1006 1007 1008 1011
1012 1013 1014 1016 1017 1018 1019 1028 1035 1037
1046 1047 1050 1056 1064 1067 1068 1080 1088 1089
1102 1106 1111 1118 1142 1159 1163 1198 1207 1218
1247 1250 1258 1274 1298 1306 1316 1338 1363 1368
1369 1401 1404 1422 1423 1450 1454 1455 1458 1469
1477 1481 1486 1488 1491 1503 1504 1517 1519 1528
1543 1546 1547 1552 1562 1565 1573 1579 1595 1604
1607 1631 1632 1633 1634 1650 1656 1657 1658 1663
1664 1665 1666 1674 1684 1685 1719 1731 1740 1741
1769 1781 1799 1809 1844 1852 1858 1862 1914 1915
1922 1936 1942 1949 1950 1951 1952 1953 1958 1969
1979 2000 2013 2017 2027 2033 2039 2060 2062 2070
2105 2109 2136 2137 2138 2139 2140 2141 2143 2144
2145 2146 2159 2180 2181 2182 2183 2188 2189 2190
2193 2195 2196 2239 2242 2243 2247 2249 2262 2271
2273 2276 2282 2288 2301 2304 2350 2362 2386 2388
2389 2390 2403 2405 2406 2407 2413 2453 2478 2479
2484 2485 2487 2488 2495 2497 2498 2499 2503 2505
2506 2507 2508 2509 2514 2521 2524 2533 2535 2536
2537 2538 2539 2545 2551 2552 2555 2556 2558 2559
2560 2562 2565 2567 2568 2571 2572 2573 2575 2576
2578 2583 2590 2591 2593 2599 2602 2603 2606 2608
2610 2612 2623 2632 2635 2636 2639 2640 2649 2656
2661 2664 2665 2674 2675 2676 2680 2681 2696 2704
2705 2707 2708 2709 2710 2712 2719 2726 2739 2748
2751 2769 2771 2772 2773 2785 2799 2833 2894 2895
2896 2897 2898 2904 2906 2907 2908 2909 2924 2945
2948 2958 2959 2960 2961 2984 2985 3029 3030 3032
3034 3036 3039 3061 3062 3065 3077 3085 3086 3087

Do Not Want To Say Goodbye

Posted on by snoopy

Maybe there will be the last show of Moonmist, and we really not want to say goodbye, and Shanghai will be my second regional contest, I’m still in the dream that we can go to Tokyo the next March. It’s a crossroad in front of me, if we can’t continue, so I have to seek a job the next year, and say goodbye to ACM/ICPC, with only two regional in one year.

We had a meeting to find the problems why we got a serious result, and to do some plan to solve the different situations we will face on Shanghai. Good Luck, best wishes to our Moonmist, best wishes to our WHUACM.

北京比赛记录

Posted on by snoopy
原文发在 BBS 上了, 其实这不是总结, 因为没有解决任何问题, 只能说是比赛记录吧
北京 2006, Moonmist.Snoopy 总结

这一篇, 只谈比赛.

清华的比赛环境赛前有说, 练习赛前一天晚上还问了 Gardon 复活赛的情况来决定
比赛的时候怎么做, 在国内看来是很奇怪的分配. 比赛分 4 个机房, 每个机房 15 支
队伍左右, Ranklist 是可以直接在本机刷出来的, 没有投影.

练习赛的时候发现的确是这样的, 我们在 2 机房, DeathDecay 在 3 机房, 清华
在练习赛的时候依然没发笔和草稿纸, 还好我们自己有带, 不过问了 volunteer 确认
第二天正式比赛的时候有有放心了. 不过系统不是赛前说的 Fedora Core 4, 而是 1,
不过没影响, 我们要用的都够了.

Nov.11th 练习赛.

题目:
A. KMP 或者直接硬搞, 看是否一个字符串 s 里有分离包含单词组 w[1..n].
B. 一个经典题的变形, 问把一串 n 个数字(有正有负)分成 m 份, 使得和最大的
那份的和最小, 二分加奇妙的方法, 现在依然还没做出来似乎.
C. 公式题, n 个野人 m 个传教士, 最少要多少步能过河, 所有人都能划船, 船
最多能装 2 人.

练习赛看题顺序跟正式比赛一样, 看完 A 后我就去敲了, 数据很小, 但是想稳妥
一点, 就去找标程敲 KMP, 过了 Sample, 交后 WA 了. 然后是 tank 上去写 B, 他理解
的就是全部是正数的经典问题了, 想二分贪心, 写到一半觉得有问题就放了. Moon 把 C
的公式推出来, 写了还是 WA.

这个时候 Moon 帮我看 A, 我和 tank 一起在推 C, Moon 发现 KMP 有问题, 改了
后交还是 WA. 我和 tank 找到 Moon 公式的特例有不符合的地方, 讨论过后把 Moon 的
程序修正了一下就过了. Moon 发现我程序一个小 bug, 改了后也过了. 其实那个问题是
一开始就有想到的, 后来因为 KMP 有问题又改错了.

刷了一下 Rank, 我们在 1x 的样子吧, 这个时候 Moon 和 tank 写 B, 我在按计划
测 Judge, 像 gets() 什么的还有特殊情况导致 PE/WA 的情况, 有些直接就在 PC^2 上
问 Judge 了, 裁判都很好, 非常友善的回答了问题, 基本上我们担心可能会有问题的
地方都测过或者问过了.

最后还是没能过 B, 并且全场也只是最后几分钟的时候 PKU_RPWT 过了这个, 还剩
5 分钟左右的时候我跑去 RPWT 那边问怎么做, styc 把我推给 ACRush, 一群人围着听
完, 知道了大致思路, 前面部分说的很清楚, 不过似乎最关键的部分大家都没问清楚,
也没说如果在二分后判断上下界.

练习赛发挥还算正常, KMP 的标程有问题不是很应该, 并且我错的那一次也是可以
避免的, 还是心态和细心程度不够. 同时发现一个有点郁闷的情况, 那就是清华机房里
暖气开的特别足, 让人很晕, 甚至 DeathDecay 那个机房还开空调降温了, 当时就在开
玩笑说是不是明天带一条毛巾过来随时准备洗脸清醒.

Nov.12th 正赛

题目:
A. 贪心. 机器人响应命令, 合理安排命令顺序使得能有最多的响应.
B. 求平面图的最小割, 赛后点评说可以转换为求最短路径.
C. Manhattan 距离最小生成树, 题目中有给出一个很关键的 Hint, 赛后点评说要
用高级数据结构.
D. 计算几何. 问是否能在一定范围内找到一条折线连接两个方块的中心.
E. 简单题, 贪心.
F. 安排合适的指令操作特定计算机使结果是某个特殊排列, 有规律然后贪心.
G. 图论, 我没看题, 比赛中最难的那个题.
H. 搜索, 要求在一根直尺上使用最小数目的刻度来量出要求的 n 个长度, 刻度数
不超过 7(包括0), n<=50(可以证明去重后n<=21), 赛后问过了的队都说是暴力
通过的.
I. 博弈, 赛后点评说用 Nim 算法, 我推了一个递推关系, 不过不知道到底是我推
的关系错了还是只是输出的地方有问题.

比赛当天正点起床, 然后叫醒其他所有人, 按计划准时往比赛地出发, 在东主楼前
拍了很多集体的照片. 进去门口等入场, 清华说因为机器配置的问题推迟了 10 分钟
开始比赛.

进去后跟前一天 Volunteer 说的一样有发笔, 不过没草稿纸, 还好我们带练习赛
打印的一些了. 大家没 BT 到真的拿毛巾过来, Moonmist 的计划是 “保银争金”, 当时
预计是过 3 题就能稳拿银牌的.

宣布比赛开始后我开的试卷袋, 然后开始看题, 跟平时一样, 我 ABC, tank DEF,
Moon GHI. 题目都不长, 我看完 A 后觉得是个不难的贪心, 立马跟 moon 和 tank 说
了意思, 但是大家都想更稳妥一些, 并且觉得应该有更简单的题, 然后继续. 我看完
BC 后说题目意思, 然后 moon 说了 I 博弈的意思, 不过我没完全听明白, 至少是有
细节没说明白, moon 说了一下 H 的意思, 觉得是个经典题, 我想了一下搜, 不过觉得
数据规模太大, tank 说 E 是个简单题, 不过我没完全听明白他意思, 于是 tank 跟
moon 讨论了一下决定 tank 上去敲, 我继续看 tank 没看的 DF 的题意. moon 看完了
G 我也看完了 DF, 交流了一下题目意思后我觉得 I 那个博弈是可以写的, 就开始推.
tank 写完 E 后提交 WA, 打印出来看, 我上去写 I, 用一个很简单的结论, 交上去也
WA 了. 这时全场有不少队过了 E, 并且有人在试 HI, 不过都没过. 一起帮忙 tank 看
了一下 E, 觉得可能会是精度问题, 乱七八糟修正了一下提交就过了, 这个时候是大概
15 名左右吧. 觉得我们能可以出至少 3 题的, 这个时候我继续想了一下 I 无果, 转
去写 A 了, tank 去看我的 I.

moon 想了很久的 G 跟 H, 然后重新去看 D, 因为我们队只有 moon 一个人经常做
计算几何, 我的 A 敲完后提交 WA 了. 这个时候看 Ranklist, 有队过 I 了, 并且有
很多队过 H, 我的 A 打印出来后看了看没问题, moon 觉得 A 能出, 看我代码太长就
索性重新写了一遍. 我想了很久的 H, 推了个时间和空间都很复杂的算法, 不敢写, 跟
moon 说但是他说出不来, tank 说不会搜索也没参与讨论, tank 看我的 I 然后给了个
想法, 我觉得有道理, 就去重写 I. moon 的 A 交上去也还是 WA 了, 回头看 H 似乎
依然觉得没法做, 又埋头改 A. tank 闲着, 我们说赌一下 B, 用最大流的算法去求要
的最小割, 我的 I 改了后非常慢, 不过自信是对的, 于是想修正一下 BFS 来降时间.

tank 慢慢敲完 B 后提交超时了, 索性完全放弃了 B. 这个时候午餐过来, 我和
tank 都在吃东西想问题, moon 在改 A, 看的出来似乎是有些急躁了, moon 让我们快
点, 自己也在到处看 A.

吃饭的时候看了看时间, 还剩下一个半小时的样子, 而我们开的题似乎是太多了,
我跟 moon 提议说我们要不要重新考虑一下策略, 因为看 Ranklist 上 A 依然没一个
人过, 而 H 过了很多, B 和 I 都只有很少的队伍过. 我个人的倾向是全队合力暴力
搜 H, 但是 tank 以不会搜索为理由不参与讨论, 而 moon 觉得我的算法是绝对会超
并且不能实现的, 就在写 A, 我对 H 的信心也不是很足于是在继续看 I 的特殊情况.

最后的时间我把 I 的搜索顺序改了一下使得答案能瞬出, 交上去后是 WA, tank
手里没题跟我一起看 I, moon 依然在写 A. 封 Board 的时候我们是铜牌第一第二的
样子吧, 并且刚封 Board 我们旁边的国防科大就过了第二题, 当时觉得只要能出一
题我们就是铁定银牌了, 因为第一题过的还不是很慢. 当时我的想法是全队合力做出
H 来就好了, 因为 A 我和 moon 的思路都很简单, 没任何特殊情况, 没道理所有人
都做不出来的, 而 I 那种博弈是很靠运气的.

最后 20 分钟左右我改了一下 I 的一个判断条件, 交上去返回了 Output Fomart
Error. 大家都很兴奋, 让我在机器前改一切能改的, 同时在 PC^2 上问裁判有没有
题目描叙不清楚的问题. 改了很多都是 OFE, 裁判回答也是完全按题意, 我们的输出
跟标准输出不一样. 最后几次在 WA 和 OFE 之间徘徊, 到最后一次提交依然没过, 而
比赛终止的命令却已经到达.

忘记了我们是怎么出去的, 只记得出去后 KO 很面无表情的说还好啦, 收拾一下
按组委会安排去照相吧. 最后那张几百人的照片上, 估计我们是笑得最难看的.

赛后想了想我们的很多问题, 其实很多问题都是在练习赛的时候就留下的隐患.
比如我们不适合做我们不领先的比赛, 因为在学校里做比赛一直都是我们领跑, 什么
题能做什么题不能做几乎都是我们决定的, 而在北京的时候我们对 Ranklist 上那么
多人过 H, 并且没人过 A 没能及时调整策略. 比如平时很多时候都是两个人在讨论,
因为我们有足够的题都可以同时写, 剩下的人都是在准备过题的. 但是很遗憾, 我们
都没有及时调整.

赛后一直到现在, 我都在想为什么北京那么好的形势我们都做的这么差, 我一直
想等 Moonmist 能聚在一起坦诚的说明白我们有什么问题, 相互之间有什么猜忌, 要
如何解决. 但是一直没有这样的机会, 我也不想什么都没弄清楚就随便说, 还是希望
能在大家达成共识后说吧.

有一些问题是绝对要讨论的:
1. 我们为什么不做 H?
2. 我们在 H 的认识上有多少差距, 赛后我跟 moon 讨论才发现原来我跟他说 H
我的想法的时候他根本不知道我在说什么意思, 而我却以为他明白了我的想法
只是说不能实现.
3. 在比赛形势如此明朗的情况下还在对 A 进行无谓的乱猜?
4. 比赛还剩下一个半小时的时候我们为什么不及时调整策略?

问题的解答晚上回来再说吧, 我不想在队内都没达成共识的情况下说我们有什么
问题, 然后这些问题需要如何解决.

我在自己的日记里写到: 回来的火车上我看相机里拍的照片, 看见最后一张是定格
在我们才过 1 题时的 Ranklist 上, 难过填满心的每一个缝隙.

现在, 依然难过, 但是希望我们能在找到问题后找好解决问题的方法, 上海回来后
我们能昂头挺胸凯旋而归.