Chinaunix首页 | 论坛 | 博客
  • 博客访问: 13064
  • 博文数量: 13
  • 博客积分: 570
  • 博客等级: 中士
  • 技术积分: 150
  • 用 户 组: 普通用户
  • 注册时间: 2009-11-25 20:11
文章分类

全部博文(13)

文章存档

2010年(1)

2009年(12)

我的朋友
最近访客

分类: C/C++

2009-11-26 22:32:27

 

A:

这个题目非常简单,主要是输出格式问题。很多用户忽略了 0 的结果。还有一些对于负数有些问题。其实这个题目还可以加一个陷阱,就是如果结果为 a+i 形式的时候,不要输出 a+1i,但由于a+bi中a和b都是整数,所有不可能其平方的虚部为1了,这个陷阱就免了。这个题目考察的就是思维的缜密性和逻辑性。即使是作对的代码,也有很多看起来逻辑比较混乱的。

B:

这个考察的也是基本功。错误有各种情况,有的用sqrt(n)没考虑误差(这种情况比较多),有的没考虑到p*p形式的值,有的忽略了整数除法是直接舍入的。总之错误的程序有千万种。

C:

本题相对代码量较大,主要是如何编排数据结构,来反映旋转。实现的方式也很多,个人的一个建议是把每一圈绕出来存为一个数组,然后查找对应圈第一个数字的出现,之后旋转,看是否都相同。这样的代码会比较简洁。

D:

这就是一个典型的数学求极值问题。由于有两个角度可变,所以很多用户用两重循环遍历所有角度(以一个特地步长),寻找最大值。但这种方法不是步长过大不够精确,就是步长过小导致超时。所以一定要分析题目,看出它可以被转化为单变量的极值问题的。

就是说,当左边的夹角(a和b之间)取一个值之后,a边的左顶点和b的右顶点连线之后,旋转c边,最大值一定出现在这个连线与c边成90度的情况。这样就只考虑一个变量就可以了。

对于单变量求极值,数学上我们可以对函数求导,然后令导数为零,解出极值点。这个问题比较特别在于这样做的极值点方程是一个三次方程,求解比较麻烦。所以可以采用数值计算的方法,最简单就是一重循环,找出最大值。这样时间稍微有点长。

比较好的做法是使用黄金分割法求凸性函数极值。可以参见二分法求方程的根和黄金分割法求函数的极值,这个时间是最快的。

另外,从数学上可以证明,当四个顶点共圆时,面积最大,也就是两个对角线和另外一条边构成直角,第四条虚拟的边是直径,不过这对于本题似乎没有什么帮助。

E:

本题目是这次比赛最难的一个了。简单的方法肯定是不行的,首先内存就不可能都放下,时间上n^2也来不及。采用的方法就是二分查找。对输入排序之后,首先在可能的最大值和最小值之间进行二分,对于每一个分点,查找有多少个乘积大于它。后面这个查找步骤也需要二分来做,固定一个向量,对另外一个二分。总的复杂度为 N*logN。

总的来说,这次比赛没有深奥的算法,考察的就是基本功和代码的编写调试能力

转载于http://www.skywind.name/blog/?p=367

阅读(433) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~