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