posts - 21, comments - 2, trackbacks - 0, articles - 0

apeng版的解题报告

Posted on 2011-05-01 01:25 acpeng 阅读(287) 评论(1)  编辑 收藏 引用 所属分类: ACM程序
貌似现在TLU的程序设计大赛举办的越来越勤了,像我这样一个codefans,怎么说也要来捧捧场,本人抛砖引玉,贴一个非官方的解题报告,仅供娱乐~~本人所贴代码都是在OJ里面通过的,所以请放心阅读~~

1:阶乘问题

对于一个任意位数的整数n,则n的位数digit=[log(10)(n)]+1;这里log(10)(x)表示以10为底的x的对数,[x]表示不超过实数x的最大整数,这个证明很容易,稍微算一下就知道了。

对于N!来说,取对数,得到log(10)(N!)=log(10)(N)+log(10)(N-1)+log(10)(N-2)+...+log(10)(2)因此,要知道N!的位数,只要求出上式右边的值,再取整加一就可。代码如下: 
 1#include<stdio.h>
 2#include<math.h>
 3int main()
 4{
 5    long int data;
 6    double cont;
 7    while(scanf("%ld",&data)!=EOF)
 8    {
 9        cont=0;
10        while(data>1)
11        {
12            cont=cont+log10(data);
13            data--;
14        }

15        cont=cont+1;
16        printf("%d\n",(int)cont);
17    }

18    return 0;
19}

20

  OJ地址:http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=1526

2:判断回文串,设置首尾指针,对值进行对比即可,简单
 1#include<stdio.h>
 2#include<string.h>
 3int main()
 4{
 5    int T,i,end,RetnBool;
 6    char str[1000]="\0";
 7    scanf("%d",&T);
 8    while(T--)
 9    {
10        scanf("%s",str);
11        end=(int)strlen(str);
12        end--;
13        i=0;
14        RetnBool=1;
15        while(i<=(end-i))
16        {
17            if(*(str+i)!=*(str+end-i))
18            {
19                RetnBool=0;
20                break;
21            }

22            i++;
23        }

24        if(RetnBool==1)
25            printf("yes\n");
26        else
27            printf("no\n");
28        memset(str,0,sizeof(str));
29    }

30    return 0;
31}

32


OJ地址:http://acm.hdu.edu.cn/showproblem.php?pid=2029

 

3:类似于二进制的转化,用 N 除以R,余数作为R进制的每一项,商作为新的N,反复循环即可。注意输出时要逆序。注意负数

 1#include<stdio.h>
 2int main()
 3{
 4    long int N;
 5    int R,i,j;
 6    int data[40];
 7    while(scanf("%ld%d",&N,&R)!=EOF)
 8    {
 9        i=0;
10        if(N<0)
11        {
12            N=-N;
13            printf("-");
14        }

15        while(N>R)
16        {
17            data[i]=N%R;
18            N=N/R;
19            i++;
20        }

21        data[i]=N;
22        for(j=i;j>=0;j--)
23        {
24            if(data[j]>=10)
25            {
26                printf("%c",'A'+data[j]-10);
27            }

28            else
29                printf("%d",data[j]);
30        }

31        printf("\n");
32    }

33    return 0;
34}

35


OJ地址:http://acm.hdu.edu.cn/showproblem.php?pid=2031
 

4:这是一个经典问题,常用的方法是建立链表,在网上搜一下,一大堆程序,也不乏好的算法。这里贴上我写的一个循环链表算法。因为m的范围较小,所以只要int型就行了,而且不需要太巧妙的算法,O(mn)内时间复杂度都可以满足1秒以内的运行时间。不过像下面这个OJ里面(http://acm.hdu.edu.cn/showproblem.php?pid=3089),m的范围太大(1<=m<=10^12),所以普通算法时间太长,无法AC。我也没想到更好的算法^^,如果哪位仁兄在这里AC了,请告诉我一下,共同学习哈

 1#include<stdio.h>
 2#include<malloc.h>
 3#include<stdlib.h>
 4int m;
 5int n;
 6struct node *h;
 7struct node          
 8{
 9  struct node *next;
10  int data;
11}
;
12struct node * create(struct node *h)
13{
14  struct node *p,*q; int i;
15  h=p=q=(struct node *)malloc(sizeof(struct node));
16  p->next=NULL; p->data=1;
17  for(i=2;i<=m;i++)
18   {
19     p=(struct node *)malloc(sizeof(struct node));
20     q->next=p; p->data=i; p->next=NULL;
21     q=p;
22   }
  
23  p->next=h;
24  return h;
25}

26int fun(struct node *h)
27{
28  struct node *p=h,*q; int i;
29  if(n>1)
30  {
31      while(p->next!=p)
32      {
33        i=1;
34        while(i<n-1{p=p->next; i++;}
35        q=p->next;
36        p->next=q->next;q->next=NULL;
37        free(q);
38        p=p->next; 
39      }

40  }

41  else if(n==1)
42  {
43      p->data=m;
44  }

45  return p->data;
46}

47int main()
48{
49  struct node *h;
50  while(scanf("%ld%ld",&m,&n)!=EOF)
51  {
52      
53      h=create(h);
54      printf("%d\n",fun(h));
55      h=NULL;
56  }

57  return 0;
58}

59

本题m<10000的OJ地址:http://acm.cugb.edu.cn/JudgeOnline/showproblem?problem_id=1056

Feedback

# re: apeng版的解题报告  回复  更多评论   

2011-05-01 09:35 by acpeng
好像代码不能复制哈,下次贴代码时不加行号了

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   博问   Chat2DB   管理