C++博客-Cold Code

hdoj_1042_10000的阶乘

cometrue — Mon, 06 Dec 2010 10:22:00 GMT

1 #include <iostream>
2 #include <cstring>
3 using namespace std;
4 char a[36000];
5 void rev()
6 {
7     int len=strlen(a),i;
8     char t;
9     for(i=0;i<len/2;++i)
10     {
11         t=a[i];
12         a[i]=a[len-1-i];
13         a[len-1-i]=t;
14     }
15 }//strrev()貌似不是标准库函数，囧
16
17 void multi(int n)
18 {
19     int i,l=strlen(a),m=0,jw=0;
20     rev();
21     char t[36000];
22     for(i=0;i<l;++i)
23     {
24         t[i]=((a[i]-'0')*n+jw)%10+'0';
25         jw=((a[i]-'0')*n+jw)/10;
26     }
27     if(jw>=1000)
28     {
29         t[i]=jw%10+'0';
30         t[i+1]=(jw/10)%10+'0';
31         t[i+2]=(jw/100)%10+'0';
32         t[i+3]=jw/1000+'0';
33         t[i+4]='\0';
34     }
35     else if(jw>=100)
36     {
37         t[i]=jw%10+'0';
38         t[i+1]=(jw/10)%10+'0';
39         t[i+2]=jw/100+'0';
40         t[i+3]='\0';
41     }
42     else if(jw>=10)
43     {
44         t[i]=jw%10+'0';
45         t[i+1]=(jw/10)%10+'0';
46         t[i+2]='\0';
47     }
48     else if(jw)
49     {
50         t[i]=jw+'0';
51         t[i+1]='\0';
52     }
53     else t[i]='\0';
54     strcpy(a,t);
55     rev();
56 }//将字符串乘n，需考虑最后的进位的位数。
57
58 int main()
59 {
60     int n;
61     while(cin>>n)
62     {
63         memset(a,0,36000);
64         a[0]='1';
65         a[1]='\0';
66         for(int i=2;i<=n;++i)multi(i);
67         cout<<a<<endl;
68     }
69     return 0;
70 }
71

由于一直不肯写个大整数的类，又不会用JAVA，遇到这种题目真是感到很难受。不过我今天用了一种比较耗时但确实思路简单的方法过了这道题。首先，我们必须知道10000！到底有多少位，这样才好定义合适的数组。

log10（2）+log(3)+...+log10（10000）=35659.9，所以定义一个36000的字符数组就够了。整个实现比较简单但是用了2312MS.....应该分治之类的算法会好点，最快的100MS就过了。估计是重复的反转和复制耗时了。

cometrue 2010-12-06 18:22 发表评论

求N!的位数

cometrue — Wed, 24 Nov 2010 05:35:00 GMT

//求N!的位数

//N!=1*2*3**N，两边取常用对数，即可算出log10(N!),向上取整即为N!的位数
//hdoj    984MS    344K
/*
#include
#include
using namespace std;
int main()
{
    double sum=0.0;
    int n,i,times,res;
    if(cin>>times&×!=0)
    {
        while(times)
        {
            cin>>n;
            for(i=2;i<=n;++i)
                sum+=log10(i);
            res=ceil(sum);
            cout<            sum=0.0;
            --times;
        }
    }
    return 0;
}
*/
//String公式的方法，N!~sqrt(2*pi*N)*(N/e)^N
//hdoj    0MS        360K
#include <iostream>
#include <cmath>
using namespace std;
const double pi=3.1415926;
int main()
{
    int n,times;
    long double sum;
    if(cin>>times&&times)
    {
        while(times)
        {
            cin>>n;
            sum=(long double)0.5*log10(2*pi*n)+(long double)n*(log10(n)-log10(exp(1)));
            cout<<(long)ceil(sum)<<endl;
            --times;
        }
    }
    return 0;
}

cometrue 2010-11-24 13:35 发表评论

hdoj_1005_Number Sequence

cometrue — Thu, 18 Nov 2010 09:00:00 GMT

#include <iostream>
using namespace std;
int a,b,s[100];
struct Pair
{
    int x;
    int y;
}res[50];
int main()
{
    int n,i,j,k;
    bool flag=false;
    res[0].x=res[0].y=1;
    while(cin>>a>>b>>n)
    {
        if(!(a||b||n))return 0;
        for(i=1;i<50;++i)
        {
            res[i].x=res[i-1].y;
            res[i].y=(a*res[i-1].y+b*res[i-1].x)%7;
            for(j=0;j<i-1;++j)//…………………………注意这里循环上限是i-1，这样可以排除三个连续相等的情况。就是把循环节为1的看成2.
            {
                if(res[j].x==res[i].x&&res[j].y==res[i].y)
                {
                    flag=true;
                    break;
                }
            }
            if(flag)break;
        }//一个循环找出循环节大小
        flag=false;//……………………注意把标志还原
        if(n<=j)cout<<res[n].x<<endl;//未进入循环时
        else
        {
            if((n-j)%(i-j)==0)k=i-1;
            else k=(n-j)%(i-j)+j-1;//这个式子改了很长时间，总是会出现问题。这是最终的形式
            cout<<res[k].x<<endl;
        }
    }
    return 0;
}

提交了七次终于给过了。是道数论的简单题，不过应该用不到什么高深的知识，关键是找出循环节。因为对于1000000000的大小，如果不找规律的话无论如何也要超时的。分析一下，每个数仅取决于它前面的两个，所以如果出现了相同的数对，则必出现循环。而且，每个数都是0~6之间的一个，可知不同的数对只有7*7=49个，那么只要计算出前50个数，则其中必有相同的两对数出现。上代码。AC之后我想知道循环是不是总是从最前面两个数开始，于是简单写了一个程序，遍历了所有的a,b(易知它们也只有49种组合)，下面是我得到的结果：

a b j i i-j

0 0 2 4 2

0 1 0 2 2

0 2 0 6 6

0 3 0 12 12

0 4 0 6 6

0 5 0 12 12

0 6 0 4 4

1 0 0 2 2

1 1 0 16 16

1 2 0 6 6

1 3 0 24 24

1 4 0 48 48

1 5 0 21 21

1 6 0 6 6

2 0 1 4 3

2 1 0 6 6

2 2 0 48 48

2 3 0 6 6

2 4 0 48 48

2 5 0 24 24

2 6 0 2 2

3 0 1 7 6

3 1 0 16 16

3 2 0 48 48

3 3 0 42 42

3 4 0 6 6

3 5 0 2 2

3 6 0 8 8

4 0 1 4 3

4 1 0 16 16

4 2 0 48 48

4 3 0 21 21

4 4 0 2 2

4 5 0 6 6

4 6 0 8 8

5 0 1 7 6

5 1 0 6 6

5 2 0 48 48

5 3 0 2 2

5 4 0 48 48

5 5 0 24 24

5 6 0 14 14

6 0 1 3 2

6 1 0 16 16

6 2 0 2 2

6 3 0 24 24

6 4 0 48 48

6 5 0 42 42

6 6 0 3 3

可见当a,b都是7的倍数时，循环从第三个数开始（以后都是0）；当a,b中只有一个是7的倍数时，循环从第二个数开始（1,0、0,1的情况比较特殊，因为跟开始的1,1重复了所以可以认为是从第一个数开始）；当a,b都不是7的倍数是，循环从第一个数开始。可见还是从第一个数开始循环的多。循环节也有长有短，比如当a=1,b=4时一直到第49个数才出现循环。

cometrue 2010-11-18 17:00 发表评论

USACO_Section 1.2_palsquare

cometrue — Thu, 21 Oct 2010 09:32:00 GMT

#include <stdio.h>
#include <string.h>
void conv(char numb[],int n,int base)
{
    int num[18],len=0,j;
    while(n/base)
    {
        num[len]=n%base;
        ++len;
        n/=base;
    }
    num[len]=n;


    for(j=len;j>=0;--j)
    {
        if(num[j]>9)numb[len-j]=num[j]+55;
        else numb[len-j]=num[j]+'0';
    }
    numb[len+1]='\0';
    return ;
}

int main()
{
    FILE *fin,*fout;
    fin=fopen("palsquare.in","r");
    fout=fopen("palsquare.out","w");
    int base,i,len=0,j;
    fscanf(fin,"%d",&base);
    for(i=1;i<=300;++i)
    {
        char square[18]={'\0'},num[10]={'\0'};
        int flag=1;
        conv(num,i,base);
        conv(square,i*i,base);
        len=strlen(square);
        for(j=0;j<=len/2;++j)
        {
            if(square[j]!=square[len-j-1])
            {
                flag=0;
                break;
            }
        }
        if(flag)fprintf(fout,"%s %s\n",num,square);
    }
    return 0;
}

我还是习惯用C写……所以把代码贴上来的时候发现stdio是黑色的，而“base”是蓝色的。

就这样吧。

题目：

Palindromic Squares
Rob Kolstad

Palindromes are numbers that read the same forwards as backwards. The number 12321 is a typical palindrome.

Given a number base B (2 <= B <= 20 base 10), print all the integers N (1 <= N <= 300 base 10) such that the square of N is palindromic when expressed in base B; also print the value of that palindromic square. Use the letters 'A', 'B', and so on to represent the digits 10, 11, and so on.

Print both the number and its square in base B.

PROGRAM NAME: palsquare

INPUT FORMAT

A single line with B, the base (specified in base 10).

SAMPLE INPUT (file palsquare.in)

OUTPUT FORMAT

Lines with two integers represented in base B. The first integer is the number whose square is palindromic; the second integer is the square itself.

SAMPLE OUTPUT (file palsquare.out)

没有什么复杂的算法，因为这一节讲的就是“the brute force, straight-forward, try-them-all method of finding the answer.

”

cometrue 2010-10-21 17:32 发表评论

USACO_Section 1.1_beads

cometrue — Thu, 21 Oct 2010 06:54:00 GMT

#include <stdio.h>
#include <stdlib.h>
int main()
{
    FILE *fin,*fout;
    fin=fopen("beads.in","r");
    fout=fopen("beads.out","w");
    char *beads;
    int n;
    fscanf(fin,"%d",&n);
    beads=(char *)malloc(3*n*sizeof(char));
    fscanf(fin,"%s",beads);
    int i,a,b,left,right,sum=0;
    for(i=n;i<3*n;++i)
    {
        beads[i]=beads[i-n];
    }
    for(i=n;i<2*n;++i)
    {
        left=i;
        right=i+1;
        char ch;

        while(beads[left]=='w'&&left>=0)--left;
        ch=beads[left];
        while(left>0&&(beads[left-1]==ch||beads[left-1]=='w'))--left;
        a=i-left+1;

        while(beads[right]=='w'&&right<3*n)++right;
        ch=beads[right];
        while(right<(3*n-1)&&(beads[right+1]==ch||beads[right+1]=='w'))++right;
        b=right-i;

        if(a+b>sum)sum=a+b;
        if(a>=n||b>=n||a+b>n)sum=n;
    }
    fprintf(fout,"%d\n",sum);
    return 0;
}

首先我的想法是从1到n,left=0,right=1,然后往两边数颜色相同的珠子。如果用一个大小为n的数组存字符串，一个很显然的问题就是当left<0或者right>n-1时就要溢出。所以要用到一个取余的函数。

但是这样确实太麻烦了，写的代码也容易出错，我终于决定重写了。新的想法是在字符串两边各复制一份相同的，这样就是大小为3×n的字符串，而循环时只需要从n到2×n-1,解决了溢出的问题。（但是我觉得这并不是一个好方法，因为浪费了三倍的空间）。最终的代码是这样的，虽然AC了，但总不是那么完美。

cometrue 2010-10-21 14:54 发表评论

USACO_Section 1.1_beads

cometrue — Thu, 21 Oct 2010 06:39:00 GMT

题目不难，但是。。。

首先我的想法是从1到n,left=0,right=1,然后往两边数颜色相同的珠子。如果用一个大小为n的数组存字符串，一个很显然的问题就是当left<0或者right>n-1时就要溢出。所以要用到一个取余的函数

int cycle(int a,int n)

{

return a<0?(a%n+n):(a%n);

}

但是这样确实太麻烦了，写的代码也容易出错，我终于决定重写了。新的想法是在字符串两边各复制一份相同的，这样就是大小为3×n的字符串，而循环时只需要从n到2×n-1,解决了溢出的问题。（但是我觉得这并不是一个好方法，因为浪费了三倍的空间）。最终的代码是这样的，虽然AC了，但总不是那么完美

#include

int main()

{

FILE *fin,*fout;

fin=fopen("beads.in","r");

fout=fopen("beads.out","w");

char *beads;

int n;

fscanf(fin,"%d",&n);

beads=(char *)malloc(3*n*sizeof(char));

fscanf(fin,"%s",beads);

int i,a,b,left,right,sum=0;

for(i=n;i<3*n;++i)

{

beads[i]=beads[i-n];

}

for(i=n;i<2*n;++i)

{

left=i;

right=i+1;

char ch;

while(beads[left]=='w'&&left>=0)--left;

ch=beads[left];

while(left>0&&(beads[left-1]==ch||beads[left-1]=='w'))--left;

a=i-left+1;

while(beads[right]=='w'&&right<3*n)++right;

ch=beads[right];

while(right<(3*n-1)&&(beads[right+1]==ch||beads[right+1]=='w'))++right;

b=right-i;

if(a+b>sum)sum=a+b;

if(a>=n||b>=n||a+b>n)sum=n;

}

fprintf(fout,"%d\n",sum);

return 0;

}

cometrue 2010-10-21 14:39 发表评论