竞赛生涯

[zz] 追女孩好比做 OJ

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

— 滑溜溜的分割线 —

开始的时候, 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的用法详解 (两年前的原创)

发信人: 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]

TCCC Round1B, 又是低级错误

受不了自己了, 一个简单的二叉树, 因为不习惯怎么在 TC 里用递归, 自己手动实现了个非递归版本的, 交上去做完 1000p 回头看看 500p 发现还是有个问题, 修改后交, 分巨低, 结果最后还是没过 System Test, 看了下就错了一组数据, 其实就是我发现的那个错误的加强版. 1000p 的贪心写的太弱了点, 最后过了的程序貌似也还是贪心. 还好过线了, 不过估计后面的比赛也不会有太多心情去做. 猪头啊!!! 果然好久没写程序能力下降太多.

Quick Challenge 2007

终于还是再回来 ACM/ICPC 队里玩, 陪大家一起玩, 继续去年的 KO Challenge, 只是改成了 Quick Challenge. 找题真是个很郁闷的事情, 现在有太多的人在 POJ 上做题了, 找一个合适的题真是麻烦, 要能在一个小时内过掉, 并且又不是所有人都能很轻松的过掉, 不能太复杂, 也不能完全弱智完全拼 APM, 最重要的是, 尽量没人做过.

前天下午开始找题吧, 随便翻了一下, Mid-Atlantic 2005 的套题里随便弄了一个出来, 看半天觉得是硬搞, 偏偏去看了下 Discuss 成了 DP, 很恶心的还不说是集合 DP, 并且给的那个递推式貌似有 bug, 错了一个小时后怒了去 POJ 上交官方标程居然都很慢, 果然全排列还是慢了. 改自己很恶心的喜欢敲的集合 DP, 顺利 AC, 0ms. 比较了一下觉得 POJ 上数据不全, 放 WOJ 上, 没人过, 然后在 POJ 上居然能卡过去, 还有在 WOJ 上 WA 而 POJ 上 AC 的, 比较了一下是最后一组数据, 有一个条件他们判错了. 无语了, 联系 POJ 的 admin, 把数据加全, 然后 rejudge, 放倒一片… 我不是故意的… 大家就当从我身上获取 rp 吧…

今天去找了个有点像计算几何的, 结果被一群人用模拟水掉… ft. 无语了. 到底是我的敏感程度不一样还是无知无谓? 异或还是数据太弱? 回头我去加强…

No Updated

Sorry for that I didn’t update this space in the last semester, maybe the reason is I’ve passed CET-6 with a poor score, and from March, I spend many times to communicate with others by English, practice to get ready for English interview. English, just a tool to get some target, not all of our lifes.
 
I’ve used this space as an English Blog, now, I use the blog offered by edu.cn to record some technology items, and the Q-zone offered by Tencent to record my life. Maybe I’m tired in English, as the ATC(sh) refused my intern application. Sorry to lympanda, I’m too poor to get that position.

百度之星初赛结果

据 SRbGa 说, 初赛的线是 18/22, 果然比我想的还要低, 看来我还是高估所有参赛的水平和对输入的判别能力了, 本来想的是第一天 30(第一题全部和第二题一半), 第二天是 40(第一题全部和第三题的暴力, 或者其他两个题).

自己的成绩有点失望, 两天都是 28. 第一天的并查集居然莫明其妙挂了一个点, 队里的其他人也有莫明其妙挂一两个点的, 奇怪, 最朴素的并查集加所有时间点查找, 怎么会出问题呢. 第一天去水的那个题还是如愿以偿的拿到了 10 分, 估计是个人就能拿到吧, 只要不犯常识性错误. 第二天的第一题居然挂了 2 个点, 真是没天理, 那么 easy 的题, 难道真的我哪个输入输出没弄好? 或者是 Error 没处理? 第三题的暴力过了 8 个点, 不过有人随机化居然过了 13 个点, 更加没天理, 果然随机化暴力才是王道…

本周六复赛, 好好加油吧, 希望能进决赛, 不过似乎按自己现在的状态和实力还是基本没戏.

百度之星 2007 初赛

两轮, 都只做了一个半小时的样子, 很久没写代码做不下去, 同时发现自己做模拟题的能力越来越弱了.

第一场, 事后想想觉得比较靠谱的理解是第一暴力并查集, 第二预处理后二分, 第三暴力记忆化搜索, 第四据说直接连起来就可以, 觉得可以做第一的全部, 第二的前五个点, 第三的暴力可以写, 估计能过一半以上的点, 第四写个挫点的也能过至少两个点, 编码速度太低了, APM 不及巅峰时刻的 1/3, 自己就写了第一和第二的前五个点, 然后在快 11 点的时候从机房撤退, 提前交卷, 第一题花在输入处理上的时间太多, 后面的时间没仔细看第四导致错过了这个简单题, 而第三的暴力也还是很要点时间的, 情况太多.

第二场, 算法都还比较清晰了, 第一模拟, 经典简单题, 估计要注意的是判输入错误, 第二直接模拟估计就可以了, 注意写好一点, 第三我觉得是 DP 流, 或者有很多条件的记忆化搜索, 第四, 字符串 Hash 加字符串匹配了. 自己写了第一和第三的暴力搜索, 第二和第四都嫌太麻烦了, 加上机房的网络, 连网页都打不开… 还剩半个小时的时候从机房撤回宿舍, 打开后直接提交了.

从去年的情况对比今年来看, 觉得第一天的线不会超过 30 分的, 个人比较倾向 25, 第一题 20 + 第二题前面点, 看第二题点的分值分布, 但是如果考虑上第四题的分, 或许 50+ 也说不定. 第二天估计会在 50 分左右, 就是第一题全分, 第三题全分或者二四的半分. 1w+ 进 400, 也不知道到底能做到多好.

Noah 的 web 美工基本完成啦

做了几乎一寒假的美工, 终于在昨天晚上最终搞定 admin 组件的页面美工, 修复了几个在页面文件上就可以修复的小 bug, 其他没改什么, 主要还是视觉效果

看看这个星期如果有空, 跟 KO 说的一样把去年个人赛的题挂上去, 4 场比赛还是可以做热身的, 顺带熟悉一下系统, 免得今年比赛时出问题