May 7, 2008

一、ACM/ICPC竞赛的特点

ACM/ICPC(国际大学生程序设计竞赛)是以算法设计为主的程序设计竞赛,并不涉及具体的应用技术。

ACM/ICPC竞赛以组队形式参赛,每个参赛队由三名队员组成,共同使用一台计算机解题。通常每场比赛的试题为6至10题,根据各队的完成题数和罚时进行排名。题目提交通过称为完成,从比赛开始到提交成功所用的时间为题目的基础罚时,另外,一道题目每提交失败一次,将增加20分钟罚时。也就是说,参赛队要尽可能用最快的速度、最少的失败次数,解决最多的题目。

二、输入和输出处理
试题一般采用标准输入和输出方式读取输入和产生输出,在题目中会详细描述输入和输出的格式和值域范围,所写的程序一定要严格遵守题目指定的输入输出格式。

在比赛试题的输入和输出处理上,针对一些常见的情形,有一些常用的方法。

1、多测试用例的输入和输出

有些试题在一次输入中只包含一个测试用例,也就是说,程序每运行一次,只算一道题。也有些试题在一次输入中包含多个测试用例,也就是说,程序每运行一次,要计算多道题。

对多用例输入,通常会先输入要计算的用例的个数,然后依次输入每个测试用例的输入数据,但程序并不需要等到所有的测试用例都计算完后再输出所有测试用例的计算结果,而是可以读入一个测试用例,输出一个结果,再读入一个测试用例,再输出一个结果。因此对多用例输入的试题,可以用这样的输入模式:

以C++为例:

int n;

cin >> n;

for (int i=0; i

{

读入测试用例数据

计算

输出计算结果

}

2、单测试用例输入的结束判断
对单用例输入,最主要的问题是如何知道输入什么时候结束。

有些试题会指定某种特殊的输入值作为输入的结束标志,这种情况比较容易处理,只须在读入后,判断一下读入的内容是否为约定结束值即可。

有些试题并不指定特殊的输入值,而是以EOF(文件结束标志)作为结束标志。如果从文件流读入,当读到文件尾时,输入返回EOF。如果从键盘读入时,在Windows的终端中,是以Ctrl+Z表示EOF。对于这种情况,可以用这样的输入模式:

以C++为例:

int m, n; // 假设要连续输入一组整数对

while (cin>>m>>n)

{

处理整数对(m, n)

}

以C语言为例:

int m, n;

while (scanf(“%d%d”, &m, &n)==2)

{

处理整数对(m, n)

}

三、数据结构的设计
很多试题中已经给出了数据量的上限,因此可以很方便地以数组的方式定义数据结构。但也要注意到有些题目中没有明确指出数据上限时,切不可盲目定义数组大小。

例如在题1070(多项式求和)中,并未说明输入多项式的项数,对这种情况就不宜用数组方式来表示多项式了——除非你的运气足够好,所开辟的数组大小能够经受所有的测试用例的考验。

除了使用一般的数组或链表结构外,对使用C++的选手来说,STL也是一大利器,充分运用可以有效提高编程的效率和正确性。

四、测试用例的考虑
在试题中通常会给出测试用例的样例,这通常会被我们用来测试自己的程序,而且很多选手往往在正确计算出测试用例样例时,会认为自己的程序是正确的。

其实测试用例的样例只是测试用例的个例,实际用于测试的测试用例往往会涵盖各种极限情况和边界情况,而且有时测试用例的数量还会比较大,甚至会重复测试同一个测试用例。因此我们的程序能够通过样例测试,未必能够通过所有的测试用例的测试,一方面要全面考虑所有可能的极限情况和边界情况,一方面程序要有足够的效率。

April 5, 2008

有一根27厘米的细木杆,在第3厘米、7厘米、11厘米、17厘米、23厘米这五个位置上各有一只蚂蚁。 木杆很细,不能同时通过一只蚂蚁。开始 时,蚂蚁的头朝左还是朝右是任意的,它们只会朝前走或调头,但不会后退。当任意两只蚂蚁碰头时,两只蚂蚁会同时调头朝反方向走。假设蚂蚁们每秒钟可以走一厘米的距离。 编写程序,求所有蚂蚁都离开木杆的最小时间和最大时间。

—————————————————-


***  最笨的方法当然是把蚂蚁看成一个一个的去遍历左右; // 还真有人这么写

***  然后好一点的方法是递归:

类似这种:http://blog.csdn.net/andylin02/archive/2007/07/27/1711701.aspx
就不贴代码了

***  最简单的方法当时是“禅”啦

Python代码:
def f(x):return 27-x
a=[3,7,11,17,23] 
b=map(f,a)
print ‘max:’,max(max(a),max(b))
print ‘min:’,max(min(a[x],b[x]) for x in range(0,5))


那你看,万生在人海穿梭,相遇又回头:如果把这个过程想象成我继续走,他继续走;
我穿着他的躯壳,他穿着我的躯壳,那岂不等同于我们没有相识

所以
要算最长的的时间 就是初始状况下 蚂蚁离距离它最远的那个边的最大值。
要算最少的时间 就是所有蚂蚁中最后一只走出来的时间,就是每个蚂蚁都朝着离自己近的一个端点爬,然后这些时间中最大的一个。
上面是一段简单的草稿代码 就么的注释了。

缘分那。。缘分。。

March 26, 2008

November 16, 2006

 

Problem Description:We dont want to interview all the candidates in order to get the best one also do not wish ti hire and fire as we find better applicants.Instead we are willing to settle for a candidate who is close to the best.In this problem we must obey one company requirement:after each interview we must either immediately offer the position to the applicant or must tell them they will not get the job.what is the trade-off between minimizing the amount of interviewing and maximizing the quality of the candidate hired?

On-Line-Hiring-Max(k,n)
bestscore <– —inf
for i <–1 to  k
      do if score(i)>bestscore
                       then bestscore <—-score(i)
for i <–k+1 to n
      do if score(i)>bestscore 
                            then return i
return n

we wish to determine for each possible value of k, the probability that we hire the most qualified applicant.
Let Si be the event that we succeed in choosing the best-qualified applicant in the ith one interviewed.
Pr(s)=sigma(i=k+1,n){Si} PR(Si)=k/(n(i-1)) 
=k/n*sigma(i=k,n-1)1/i Pr(s)>=1/e           say lnk=lnn-1,Max.

This is a much easier way than Nju_Mcm_Training_Professor Yao’s method.

appended question.  How we can get the best expect applicant? The average expect rank?