2010年12月6日
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()貌似不是標準庫函數(shù)，囧
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，需考慮最后的進位的位數(shù)。
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
由于一直不肯寫個大整數(shù)的類，又不會用JAVA，遇到這種題目真是感到很難受。不過我今天用了一種比較耗時但確實思路簡單的方法過了這道題。首先，我們必須知道10000！到底有多少位，這樣才好定義合適的數(shù)組。
log10（2）+log(3)+...+log10（10000）=35659.9，所以定義一個36000的字符數(shù)組就夠了。整個實現(xiàn)比較簡單但是用了2312MS.....應(yīng)該分治之類的算法會好點，最快的100MS就過了。估計是重復(fù)的反轉(zhuǎn)和復(fù)制耗時了。
posted @
2010-12-06 18:22 cometrue 閱讀(313) |
評論 (0) |
編輯 收藏
2010年11月18日
#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)//…………………………注意這里循環(huán)上限是i-1，這樣可以排除三個連續(xù)相等的情況。就是把循環(huán)節(jié)為1的看成2.
{
if(res[j].x==res[i].x&&res[j].y==res[i].y)
{
flag=true;
break;
}
}
if(flag)break;
}//一個循環(huán)找出循環(huán)節(jié)大小
flag=false;//……………………注意把標志還原
if(n<=j)cout<<res[n].x<<endl;//未進入循環(huán)時
else
{
if((n-j)%(i-j)==0)k=i-1;
else k=(n-j)%(i-j)+j-1;//這個式子改了很長時間，總是會出現(xiàn)問題。這是最終的形式
cout<<res[k].x<<endl;
}
}
return 0;
}
提交了七次終于給過了。是道數(shù)論的簡單題，不過應(yīng)該用不到什么高深的知識，關(guān)鍵是找出循環(huán)節(jié)。因為對于1000000000的大小，如果不找規(guī)律的話無論如何也要超時的。分析一下，每個數(shù)僅取決于它前面的兩個，所以如果出現(xiàn)了相同的數(shù)對，則必出現(xiàn)循環(huán)。而且，每個數(shù)都是0~6之間的一個，可知不同的數(shù)對只有7*7=49個，那么只要計算出前50個數(shù)，則其中必有相同的兩對數(shù)出現(xiàn)。上代碼。AC之后我想知道循環(huán)是不是總是從最前面兩個數(shù)開始，于是簡單寫了一個程序，遍歷了所有的a,b(易知它們也只有49種組合)，下面是我得到的結(jié)果：
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的倍數(shù)時，循環(huán)從第三個數(shù)開始（以后都是0）；當a,b中只有一個是7的倍數(shù)時，循環(huán)從第二個數(shù)開始（1,0、0,1的情況比較特殊，因為跟開始的1,1重復(fù)了所以可以認為是從第一個數(shù)開始）；當a,b都不是7的倍數(shù)是，循環(huán)從第一個數(shù)開始。可見還是從第一個數(shù)開始循環(huán)的多。循環(huán)節(jié)也有長有短，比如當a=1,b=4時一直到第49個數(shù)才出現(xiàn)循環(huán)。
posted @
2010-11-18 17:00 cometrue 閱讀(1507) |
評論 (2) |
編輯 收藏
2010年10月21日
#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;
}
我還是習(xí)慣用C寫……所以把代碼貼上來的時候發(fā)現(xiàn)stdio是黑色的，而“base”是藍色的。
就這樣吧。
題目：
Palindromic Squares
Rob KolstadPalindromes 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)
10
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)
1 1
2 4
3 9
11 121
22 484
26 676
101 10201
111 12321
121 14641
202 40804
212 44944
264 69696
沒有什么復(fù)雜的算法，因為這一節(jié)講的就是“the brute force, straight-forward, try-them-all method of finding the answer.
”
posted @
2010-10-21 17:32 cometrue 閱讀(1251) |
評論 (0) |
編輯 收藏
#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,然后往兩邊數(shù)顏色相同的珠子。如果用一個大小為n的數(shù)組存字符串，一個很顯然的問題就是當left<0或者right>n-1時就要溢出。所以要用到一個取余的函數(shù)。
但是這樣確實太麻煩了，寫的代碼也容易出錯，我終于決定重寫了。新的想法是在字符串兩邊各復(fù)制一份相同的，這樣就是大小為3×n的字符串，而循環(huán)時只需要從n到2×n-1,解決了溢出的問題。（但是我覺得這并不是一個好方法，因為浪費了三倍的空間）。最終的代碼是這樣的，雖然AC了，但總不是那么完美。
posted @
2010-10-21 14:54 cometrue 閱讀(1274) |
評論 (0) |
編輯 收藏
題目不難，但是。。。
首先我的想法是從1到n,left=0,right=1,然后往兩邊數(shù)顏色相同的珠子。如果用一個大小為n的數(shù)組存字符串，一個很顯然的問題就是當left<0或者right>n-1時就要溢出。所以要用到一個取余的函數(shù)
int cycle(int a,int n)
{
return a<0?(a%n+n):(a%n);
}
但是這樣確實太麻煩了，寫的代碼也容易出錯，我終于決定重寫了。新的想法是在字符串兩邊各復(fù)制一份相同的，這樣就是大小為3×n的字符串，而循環(huán)時只需要從n到2×n-1,解決了溢出的問題。（但是我覺得這并不是一個好方法，因為浪費了三倍的空間）。最終的代碼是這樣的，雖然AC了，但總不是那么完美
#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;
}
posted @
2010-10-21 14:39 cometrue 閱讀(1174) |
評論 (0) |
編輯 收藏