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()貌似不是標準庫函數，囧
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就過了。估計是重復的反轉和復制耗時了。
posted @
2010-12-06 18:22 cometrue 閱讀(325) |
評論 (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)//…………………………注意這里循環上限是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個數才出現循環。
posted @
2010-11-18 17:00 cometrue 閱讀(1515) |
評論 (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;
}
我還是習慣用C寫……所以把代碼貼上來的時候發現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
沒有什么復雜的算法，因為這一節講的就是“the brute force, straight-forward, try-them-all method of finding the answer.
”
posted @
2010-10-21 17:32 cometrue 閱讀(1256) |
評論 (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,然后往兩邊數顏色相同的珠子。如果用一個大小為n的數組存字符串，一個很顯然的問題就是當left<0或者right>n-1時就要溢出。所以要用到一個取余的函數。
但是這樣確實太麻煩了，寫的代碼也容易出錯，我終于決定重寫了。新的想法是在字符串兩邊各復制一份相同的，這樣就是大小為3×n的字符串，而循環時只需要從n到2×n-1,解決了溢出的問題。（但是我覺得這并不是一個好方法，因為浪費了三倍的空間）。最終的代碼是這樣的，雖然AC了，但總不是那么完美。
posted @
2010-10-21 14:54 cometrue 閱讀(1280) |
評論 (0) |
編輯 收藏
題目不難，但是。。。
首先我的想法是從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 <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 閱讀(1179) |
評論 (0) |
編輯 收藏