Chinaunix首页 | 论坛 | 博客
  • 博客访问: 462860
  • 博文数量: 137
  • 博客积分: 3874
  • 博客等级: 中校
  • 技术积分: 1475
  • 用 户 组: 普通用户
  • 注册时间: 2010-07-05 10:50
文章分类

全部博文(137)

文章存档

2011年(37)

2010年(100)

分类: C/C++

2011-02-25 15:49:19

这两天做了几个题,跟大家共享一下。
上题目

这个是无意在matrix67的blog上看到的。
开始想用最笨的方法,结果WA。就是根据有几个不同的解来处理。
但是要分情况讨论,弄的晕投转向,还是wa了。
在hall of fame里面,看到很多速度很快的。
只好动脑子想tricks。然后果然想到一个,x+y+z+t=N
可以分为x+y跟z+t两部分,分别对两遍能取到的值的次数统计出来,其实两边是一样的。
然后取两遍和为N的值的次数相乘,就可以了。O(1000000)的预处理,剩下的每次
计算的复杂度是O(n)。
代码:
  1. #include <stdio.h>
  2. #include
  3. const int N=1000010;
  4. unsigned short cnt[N];
  5. int n,i,j,ans,anss;


  6. int main()
  7. {
  8.    memset(cnt,0,sizeof(unsigned shot)*N);
  9.    for( i=0;i<=1000;++i)
  10.   {
  11.     for( j=0;j<=1000;++j)
  12.     {
  13.       ans = i*i+j*j;
  14.       if(ans>1000010)
  15.     break;
  16.       cnt[ans]++;
  17.     }
  18.   }
  19.   while(scanf("%d",&n)!=EOF)
  20.   {
  21.     int mid = n/2;
  22.     anss =0;
  23.     for( i=0;i<=mid;++i)
  24.       anss+=cnt[i]*cnt[n-i];
  25.     anss *= 2;
  26.     if(n%2==0)
  27.       anss -= cnt[mid]*cnt[mid];
  28.     printf("%d\n",anss);
  29.     
  30.   }
  31.   return 0;
  32. }

提交,AC,Alan就是我啦。呵呵

今天又看到一个题,说这样的,1+2+…+n,要求不能使用乘除法、forwhileifelseswitchcase等关键字以及条件判断语句(A?B:C)。
这个跟我之前说的那个不用for打印的那个类似,就写了一个测试代码,其他的大家可以根据上篇文章写。
  1. #include  
    #include  

    int i,sum=0; 

    void funz(int n) 
      printf("%d\n",sum); 
    }

    void funs(int n)
    {
      sum+=n;
      (funs+(i-n--)/i*(funz-funs))(n);
    }

    int main()
    {
      i=10;
      funs(i);
    }

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