郁金香编程俱乐部

It's a bundle of crazy programmers, we discuss topics like data structure, algorithm, STL, AI,
Graph Theory, C++, Java, anything you can think of while programming...    
The club was founded in the year 2005, Ningbo, China.
posts - 3, comments - 1, trackbacks - 0, articles - 0
  C++博客 :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理

2006年12月7日

     摘要: 题目链接:http://acm.uva.es/p/v1/109.html一道综合性的几何题,题目看上去比较难,因而提交量也较其它题目少.题目大意如下:在500×500大小的虚拟空间中,存在N个王国,每个王国由一个电站和M个居民组成.王国的范围是一个包含其全部居民和电站的最小凸多边形.然后给出至少一个导弹着陆的位置,凡是导弹着陆点位于某个王国的范围,则这个王国的电站被破坏,不杀伤居民.求最后剩下的电...  阅读全文

posted @ 2006-12-07 14:42 TPC2005 阅读(294) | 评论 (1)编辑 收藏

2006年12月6日

101:见:这里 
arsenal同学的算法注释已经写得很详细了,我是参考他的算法的。
这里要感叹一下,arsenal的代码以及变量命名,写得太规范了,自叹不如,大家多学学啊。
良好的代码书写风格要从小培养。

102:
比较简单,6种情况枚举即可,由于算法简单,时间上也拉不开差距。

103:
动态规划,arsenal同样给出了比较优秀的算法,可以参考他的代码。
必要的工作是对每个BOX进行排序,剩下的就是求最长上升子序列的问题,动态规划。
(PS:如果觉得冒泡效率太低,自己写快速排序又嫌麻烦,可以用C语言中的qsort函数)

104:
三角套汇,一不小心排到了12名,出乎意料啊,也不知道这个算法有没有BUG
首先建矩阵,把输入数据补充完整,arb[i][i]=1.0,即自己换自己的汇率1.0
然后是两个大的循环,外面的是兑换次数,里面的是起始兑换的币种X(1<=X<=N)。
针对某个起始币种X,计算X兑换成其它币种Y再兑换成X的汇率,取最大值记录Y,
再从Y开始,计算Y兑换成其它任意币种Z再兑换成X的汇率,取最大值记录Z。
重复以上,起点和终点均是X,在每次记录最大值时,比较目标汇率1.01,
如果满足,跳出循环,输出兑换记录,比如X->Y->Z->X

105:
简单题,建个10000的矩阵搞定,不过时间也不怎么理想,可以考虑更优化的算法。
细节上要注意,把矩阵理解为:H[i]=100代表i~i+1这一小段建筑的高度为100,比较好处理

106:
数学问题,需要在互联网上检索相关资料,否则无从下手,
这里有个公式:(2mn)^2+(m^2-n^2)^2=(m^2+n^2)^2,(m>n>0,m,n一奇一偶且互质)
枚举m,n即可向上无重复无遗漏的枚举勾股数组(a,b,c)【其最大公约数为1】,使得a^2+b^2=c^2,
但是(6,8,10)有公约数2,不属于勾股数组,无法通过公式枚举得到,需要在(3,4,5)的基础上再次翻倍枚举。

107:
先排除几种特殊情况,设开始那只猫的高度h,以及最后动手工作的猫的数目s
h=1,输出0,1
h=s+1,输出1,x+y
s=1,则N=1,每次变一个。
剩下的情况,从2开始穷举N,对x开N次根号,看结果是否为整数。只要找到N,结果就好计算了,程序涉及浮点数,精度运算,特别小心。

108:
常规能想到的算法应该是O(N^4),动态规划,这题是经典题,随便搜一下能找出很多
下面介绍一维的情况下,求最大连续子序列的O(N)算法。
s[10]={-1,2,3,5,-9,-7,16,-20,7,6},max=s[0],sum=0;
for(i=0;i<10;i++)
{
    sum=sum+s[i];
    if(sum>max) max=sum;
    if(sum<0) sum=0;

}

解释一下,对序列作累加,如果加到某个数时总和为负,与其加上负数,还不如清零,从下个数重新开始累加。应用这个原理,可以把O(N4)转换成为O(N3).
举例3×3的矩阵,子矩阵行上可取(1),(2),(3),(1,2),(2,3),(1,2,3),列上就用上述算法。
读取数据时,把每行值加到前一行上。q[i][j]表示第j列第1行至第i行的和。
这样任意连续行的和可通过两数相减得到,比如第j列(2,3)行的和等于q[3][j]-q[1][j]
第j列(1,2)行的和等于q[2][j]-q[0][j],这里q[0][j]初始化为0

Pro_101-Pro_108 打包下载源码

posted @ 2006-12-06 14:44 TPC2005 阅读(197) | 评论 (0)编辑 收藏

2006年12月5日

Pro_100 解题思想:
根据题意,输入22,得到的数列:22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1
这样我们在计算22的cycle length时,顺便得到了这一数列成员的所有cycle length
22的cycle length为16,11的cycle length为15,依次类推。
把所有计算过cycle length的数保存,以后就不必重复计算。
具体实现方法,建立长度为100000的数据数组,以及长度为500左右的临时数组。
通过他人的程序,事先可以知道的是:1-1000000的最长cycle length为525,
因而数据数组可定义为2字节的short int,临时数组500左右足矣。
例如计算22,可得到22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1的cycle length
然后再计算9,可得到9 28 14 7 22,同时写入临时数组,
当计算到22时查数组可得22的cycle length为16,
那么7的cycle length即为22的cycle length+1=17,依次逆向类推。
9 28 14的cycle length分别为20 19 18,保存到数据数组。

p.s.细节问题:
1.输入的i,j,可能存在i>j的情况,特殊处理。特别指出,先原样输出i,j,再交换。
2.在1-1000000中存在"最大飞行高度"超过2^32的数(若不清楚"最大飞行高度"请看附件介绍),但是题目保证中间过程没有超过2^32的数,所以­不必定义64位整型。
源代码下载
3N+1相关资料下载

 1 /* *********************************** */
 2 /*      Pro_100  The 3n + 1 problem    */
 3 /*   CPU Time 0:00.068 Memory Minimum  */
 4 /*  Ranklist 288  Programmed By Wingy  */
 5 /* *********************************** */
 6
 7 #define  MAX 1000000
 8 #include < stdio.h >
 9
10 int  main()
11 {
12      short  cir[MAX] = { 0 , 1 , 2 } ,len,j,tp,lst;
13     unsigned n,i,tm,stk[ 500 ] = { 0 } ,x,y;
14      while (scanf( " %u%u " , & x, & y) != EOF)
15      {
16         lst = 0 ;
17         printf( " %u %u  " ,x,y);
18          if (x > y) tm = x,x = y,y = tm;
19          for (i = x;i <= y;i ++ )
20          {
21              if (cir[i] == 0 )
22              {
23                 n = i;
24                 len = 0 ;
25                  while ( 1 )
26                  {
27                     stk[len ++ ] = n;
28                      if (n & 1 ) n = 1 + n + (n << 1 );
29                      else  n >>= 1 ;
30                      if (n < MAX  &&  cir[n])  break ;
31                 }

32                 tp = len + cir[n];
33                  for (j = 0 ;j < len;j ++ )
34                  {
35                     tm = stk[j];
36                      if (tm < MAX) cir[tm] = tp;
37                     tp -- ;
38                 }

39             }

40              if (cir[i] > lst) lst = cir[i];
41         }

42         printf( " %d\n " ,lst);
43     }

44      return   0 ;
45 }

posted @ 2006-12-05 22:30 TPC2005 阅读(145) | 评论 (0)编辑 收藏