几道算法题

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

上题目

这个是无意在matrix67的blog上看到的。

开始想用最笨的方法，结果WA。就是根据有几个不同的解来处理。

但是要分情况讨论，弄的晕投转向，还是wa了。

在hall of fame里面，看到很多速度很快的。

只好动脑子想tricks。然后果然想到一个，x+y+z+t=N

可以分为x+y跟z+t两部分，分别对两遍能取到的值的次数统计出来，其实两边是一样的。

然后取两遍和为N的值的次数相乘，就可以了。O（1000000）的预处理，剩下的每次

计算的复杂度是O(n)。

代码：

#include <stdio.h>
#include
const int N=1000010;
unsigned short cnt[N];
int n,i,j,ans,anss;


int main()
{
   memset(cnt,0,sizeof(unsigned shot)*N);
   for( i=0;i<=1000;++i)
  {
    for( j=0;j<=1000;++j)
    {
      ans = i*i+j*j;
      if(ans>1000010)
    break;
      cnt[ans]++;
    }
  }
  while(scanf("%d",&n)!=EOF)
  {
    int mid = n/2;
    anss =0;
    for( i=0;i<=mid;++i)
      anss+=cnt[i]*cnt[n-i];
    anss *= 2;
    if(n%2==0)
      anss -= cnt[mid]*cnt[mid];
    printf("%d\n",anss);

  }
  return 0;
}

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

今天又看到一个题，说这样的，求1+2+…+n，要求不能使用乘除法、for、while、if、else、switch、case等关键字以及条件判断语句（A?B:C）。

这个跟我之前说的那个不用for打印的那个类似，就写了一个测试代码，其他的大家可以根据上篇文章写。

#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);}

Open link in current tab