都寫了三份了，實(shí)在不想加重以前隨筆的負(fù)擔(dān)
所以只好另起爐灶。
F：Face Formations這道題據(jù)說是組合數(shù)學(xué)的題，但是我是用動(dòng)態(tài)規(guī)劃作的
上windows實(shí)在聽不進(jìn)課，就在草稿紙上胡寫亂畫，莫名其妙的模擬出來了
主要我是要填表，狀態(tài)方程，我不知道該怎么寫，我模擬下過程好了：
4
1 2 4 7
1
37 37 22 7
2 0 15 15 6
3 0 0 9 5
4 0 0 4 4
5 0 0 0 3
6 0 0 0 2
7 0 0 0 1
ps: 這個(gè)表我的填表過程是從下至上，從右至左
結(jié)果是在[1][1]的位置上，我代碼實(shí)現(xiàn)的時(shí)候只開了一個(gè)數(shù)組，因?yàn)椴⒉恍枰颜麄€(gè)表都存下來
以下是我的代碼：
#include<iostream>
#include<algorithm>
using namespace std;
#define Max 35
__int64 num[Max],dice[Max];
bool cmp(__int64 a,__int64 b)
{
return a<b;
}
void solve(int n)
{
__int64 i,j;
for(i=1;i<=dice[n];i++)
num[i]=1;
for(i=n;i>=1;i--)
for(j=dice[i]-1;j>=0;j--)
num[j]+=num[j+1];
}
int main()
{
int n,i;
while(scanf("%d",&n)!=EOF&&n){
memset(dice,0,sizeof(dice));
memset(num,0,sizeof(num));
for(i=1;i<=n;i++)
scanf("%I64d",&dice[i]);
sort(dice+1,dice+n+1,cmp);
solve(n);
printf("%I64d\n",num[1]);
}
return 0;
}
ps:這道題要Long long
posted @
2008-04-11 00:06 zoyi 閱讀(316) |
評論 (3) |
編輯 收藏2008年4月10日23:52:47
第一個(gè)問題：
由平面中的n條直線確定的最大區(qū)域數(shù)Ln
L0=1；
Ln=Ln-1+n(n>0);
Ln=1+n*(n+1)/2;
第二個(gè)問題：
是平面直線的變形問題，用彎曲的線來代替直線，每一個(gè)彎曲線含有一個(gè)“鋸齒形的轉(zhuǎn)角”，同樣確定平面區(qū)域的最大個(gè)數(shù)Zn
（我們把一條彎曲折線抽象為兩條，但是合并了某些區(qū)域）
Zn=L2n-2*n=2*n*n-n+1;(n>=0);
第三個(gè)問題：
就是一下這個(gè)問題：
count the regions
若當(dāng)前有n-1條邊，那么在往里面加一條邊，這條新加的邊最多和以前的邊有9*(n-1)個(gè)交點(diǎn)，
那么會(huì)添加 9*（n-1）+1個(gè)面
這條規(guī)律對于上面兩種也是用，加x個(gè)點(diǎn)，那么就會(huì)添加x+1個(gè)面
那么總結(jié)下來 Xn=Xn-1+9*(n-1)+1
即Xn=(9/2)*n*n-(7/2)*n+1;
以下是我的代碼：
#include<stdio.h>
int main()
{
long long n;
long long ans;
while(scanf("%lld",&n)!=EOF){
ans=9*n*n-7*n+2;
ans/=2;
printf("%lld\n",ans);
}
return 0;
}
posted @
2008-04-10 23:36 zoyi 閱讀(318) |
評論 (2) |
編輯 收藏
摘要: 大家有好的代碼請發(fā)我郵箱：zhangjia888334@sohu.com 今天就作了廣搜三道題，做個(gè)小節(jié)。首先要糾正腦子里的一個(gè)錯(cuò)誤觀念，以前的我的廣搜模式就是開個(gè)隊(duì)列，走過的點(diǎn)不能走，隊(duì)列的類型我還必定是用結(jié)構(gòu)體來做結(jié)構(gòu)體里放個(gè)x,y,n，x-->橫坐標(biāo)，y-->縱坐標(biāo)，n-->步數(shù)再來幾個(gè)標(biāo)準(zhǔn)的二維數(shù)組，map[Maxh][Maxw]-->描述地圖,visit...
閱讀全文
posted @
2008-04-10 00:57 zoyi 閱讀(357) |
評論 (0) |
編輯 收藏這道題是直接拿前幾天寫得模版改的；做了幾個(gè)修改
首先刪掉了search，這道題的確不需要，本來沒刪，代碼實(shí)在太長,逼得我沒辦法
第二個(gè)，把trie中num[]的意思改掉了，num[]現(xiàn)在存的是字符串在一個(gè)數(shù)組的標(biāo)記，
相當(dāng)于map的實(shí)現(xiàn)，通過這樣我把一個(gè)字符串和一個(gè)標(biāo)號對應(yīng)上了，方便了并查集的操作
果然很久沒碰并查集了，一寫就出問題，
主要是我union_set是居然忘了要先find_set一下，這樣寫針對下面這組數(shù)據(jù)就會(huì)出現(xiàn)問題：
a b
b a
a a
還有一個(gè)就是這道題的空輸入問題，要輸出possible，而不是Impossible
一下是我的垃圾代碼，跑了500多，有誰有更好的發(fā)我郵箱哈: zhangjia888334@sohu.com
#include<iostream>
#include<cstring>
#define keyNum 26
#define MaxN 500005
struct node{
int parent;
int rank;
int num;//這個(gè)顏色出現(xiàn)的次數(shù)
node()
{
num=rank=0;
parent=-1;
}
};
node colour[MaxN];
int id=0;//數(shù)組標(biāo)記
struct trie{
struct trieNode{//trie結(jié)點(diǎn)的結(jié)構(gòu)
trieNode *link[keyNum];//下標(biāo)為 'a' , 'b' , 'c' , , 'z' 的指針數(shù)組
int num[keyNum];//插入這個(gè)單詞在數(shù)組中的位置
trieNode(){
memset(num,-1,sizeof(num));//-1表示還未插入數(shù)組
memset(link,NULL,sizeof(link));
}
void init(){
memset(link,NULL,sizeof(link));
memset(num,-1,sizeof(num));
}
};
trieNode* root;
trie()
{
root=(trieNode*)malloc(sizeof(trieNode));//初始化時(shí)為root申請了空間
root->init();
}
int Insert(char []);//返回?cái)?shù)組中的位置
void Delete(trieNode*);//釋放空間
};
void trie::Delete(trieNode* t)
{
int i;
for(i=0;i<keyNum;i++)
if(t->link[i])Delete(t->link[i]);
memset(t->num,0,sizeof(t->num));
delete(t);
}
int trie::Insert(char x[])
{
trieNode *current=root;
int i=1;
while(x[i]){
if(current->link[x[i-1]-'a']==NULL){
current->link[x[i-1]-'a']=(trieNode*)malloc(sizeof(trieNode));
(current->link[x[i-1]-'a'])->init();
}
current=current->link[x[i-1]-'a'];
i++;
}
if(current->num[x[i-1]-'a']==-1)
current->num[x[i-1]-'a']=id++;
colour[current->num[x[i-1]-'a']].num++;//出現(xiàn)的次數(shù)++
return current->num[x[i-1]-'a'];
}
void init()
{
int i;
for(i=0;i<MaxN;i++)
colour[i].parent=i;
}
void union_set(int x,int y)
{
if(colour[x].rank>colour[y].rank)
colour[y].parent=x;
else {
colour[x].parent=y;
if(colour[x].rank==colour[y].rank)
colour[y].rank++;
}
}
int find_set(int x)
{
if(x!=colour[x].parent)
colour[x].parent=find_set(colour[x].parent);
return colour[x].parent;
}
bool comman_father()
{
int i,p=0;
p=find_set(0);
for(i=1;i<id;i++)
if(find_set(i)!=p)return false;
return true;
}
void solve()
{
if(comman_father()==false){
printf("Impossible\n");
return;
}
int i,head_end=0;
for(i=0;i<id;i++)
if(colour[i].num%2==1)//判斷頭和尾
head_end++;
if(head_end==2||!head_end)//一個(gè)沒回路，一個(gè)是有回路
printf("Possible\n");
else printf("Impossible\n");
}
int main()
{
char colr1[12],colr2[12];
trie a;
int ncolr1,ncolr2;
init();
while(scanf("%s%s",colr1,colr2)!=EOF){
ncolr1=a.Insert(colr1);
ncolr2=a.Insert(colr2);
union_set(find_set(ncolr1),find_set(ncolr2));
}
//下面判斷有幾個(gè)parent，若有多個(gè)失敗
solve();
a.Delete(a.root);
return 0
}
posted @
2008-04-08 18:35 zoyi 閱讀(897) |
評論 (1) |
編輯 收藏寢室里很亂，明天我要收拾，收拾好它也收拾好自己
還是很想把博客經(jīng)營下去，以前不想寫，其實(shí)是害怕別人看，我貼的都是水題
丟人吶，但是這是我成長的過程
隱藏東西的感覺還真好玩我是棵小白菜，從來都是，也沒奢望過會(huì)成為參天大樹
但是我會(huì)慢慢澆灌，小白菜總不至于被我澆成蔥了吧，哈哈
呵呵，繼續(xù)隱藏就這樣，待續(xù).........
fighting~~!!!
posted @
2008-04-08 00:55 zoyi 閱讀(212) |
評論 (2) |
編輯 收藏
我的青蛙終于過了
完全忘了算法導(dǎo)論上說的理論了~~其實(shí)以前寫的就只有一個(gè)小錯(cuò)誤
ax+ny=b;
當(dāng)求解x時(shí)，我們先用擴(kuò)展歐幾里德extended_eculid(a,n,&x',&y');
通過計(jì)算的x'和y'來計(jì)算x
x可能沒解，也可能有d個(gè)不同的解
當(dāng)求解某些問題的時(shí)候，我們要求得到最小正解，如果x'*(b/d)<0時(shí)，我們應(yīng)該在此解的基礎(chǔ)上繼續(xù)加n/d
青蛙問題我就是這里錯(cuò)了，我是在最小解的基礎(chǔ)上加n,
最好不要忘了對n取模。
http://acm.pku.edu.cn/JudgeOnline/problem?id=1061
//SA-SB=kL(k為整數(shù))
//SA=x+pm SB=y+pn
//(x-y)+p(m-n)=kL
//p(n-m)+kL=x-y
//ax+by=n<=>a'x+b'y=n/gcd(a,b)(此時(shí)a'與b'互質(zhì))
//若x0,y0為歐幾里得所得解
//x=x0+b't y=y0-a't
#include<iostream>
__int64 Ext_Euclid(__int64 a,__int64 b,__int64* x,__int64* y)
{
__int64 p,q,d;
if(a==0){*x=0;*y=1;return b;}
if(b==0){*x=1;*y=0;return a;}
d=Ext_Euclid(b,a%b,&p,&q);
*x=q;
*y=p-(a/b)*q;
return d;
}
int main()
{
/*freopen("1.IN","r",stdin);
freopen("my.OUT","w",stdout);*/
__int64 x,y,m,n,l;//x為A的起始點(diǎn),y為B的起始點(diǎn)
//m為x的步長，n為y的步長，l為緯度長
__int64 c,a,d;
__int64 p,q;
while(scanf("%I64d%I64d%I64d%I64d%I64d",&x,&y,&m,&n,&l)!=EOF){
if(n==m)printf("Impossible\n");
else {
if(m>n){a=m-n;c=y-x;}
else {a=n-m;c=x-y;}
d=Ext_Euclid(a,l,&p,&q);
if((x>y?(x-y):(y-x))%d)printf("Impossible\n");
else {
p*=c/d;
while(p<0)p+=l/d;//這里錯(cuò)了，最小的那個(gè)不是這么加的
p=p%l;
printf("%I64d\n",p);
}
}}
return 0;
}
E
Encrypted
這道題就是簡單的應(yīng)用擴(kuò)展的歐幾里德，并不涉及模線性方程
#include<iostream>
#define MaxN 100005
char word[MaxN];
int data[MaxN],keys[MaxN];
typedef struct node{
int d;
int x;
int y;
void operator=(node b)
{
d=b.d;
x=b.x;
y=b.y;
}}NODE;
NODE EXTENDED_EUCLID(int a,int b)
{
NODE first,sec;
if(b==0){
sec.d=a;
sec.x=1;
sec.y=0;
return sec;
}
first=EXTENDED_EUCLID(b,(a%b+b)%b);
sec.d=first.d;
sec.x=first.y;
sec.y=first.x-(a/b)*first.y;
return sec;
}
int main()
{
int n,i;
node tmp;
while(scanf("%s",word)!=EOF){
memset(data,0,sizeof(data));
memset(keys,0,sizeof(keys));
int len=strlen(word);
scanf("%d",&n);
for(i=0;i<n;i++)
scanf("%d",&data[i]);
for(i=0;i<n;i++)
scanf("%d",&keys[i]);
for(i=0;i<n;i++){
tmp=EXTENDED_EUCLID(data[i],keys[i]);
while(tmp.x<0)
tmp.x+=keys[i]/tmp.d;
printf("%c",word[tmp.x%len]);
}
printf("\n");
}
return 0;
}
posted @
2008-04-08 00:42 zoyi 閱讀(207) |
評論 (0) |
編輯 收藏
http://202.120.80.191/problem.php?problemid=1868
這道題想法其實(shí)不難，可是開始的方向就錯(cuò)了，做的時(shí)候有種投機(jī)取巧的感覺，雖然知道是錯(cuò)的，但是我也要去試，呵呵，一頭撞到底
首先打質(zhì)數(shù)表，然后找到小與N的每個(gè)質(zhì)數(shù)的最大系數(shù)，開始一頭就扎進(jìn)了用倆數(shù)的乘積去除公約數(shù)的方法做，這顯然不對啊，要去模的阿，哎
下面是垃圾代碼：
#include<iostream>
#include<math.h>
#define MaxN 500005
#define M 987654321
int notP[MaxN];
using namespace std;
void init()
{
int i,j;
memset(notP,0,sizeof(notP));
notP[1]=1;
for(i=2;i<sqrt((double)MaxN);i++)
if(notP[i]==0){
for(j=2;j*i<MaxN;j++)
notP[j*i]=1;
}
}
int solve(int n)
{
int i,ans=1,t;
for(i=2;i<=n;i++){
if(notP[i])continue;
t=n;
while(t>=i){
ans=(((__int64)ans)*i)%M;
t/=i;
}
}
return ans;
}
int main()
{
int N,ans;
init();
while(scanf("%d",&N)!=EOF){
ans=solve(N);
printf("%d\n",ans);
}
return 0;
}
B題等會(huì)兒再說，他是我的痛
http://202.120.80.191/problem.php?problemid=1869
C題Cards
http://202.120.80.191/problem.php?problemid=1870
這道題開始用o(n2)的做的，并沒有想到該怎么做，后面超時(shí)，才是是這用o(n)的做，開始想的一直都不清楚
主要是在每次當(dāng)前移除情況下又出現(xiàn)了present_numR>present_numB的情況，就要更新切牌點(diǎn)，并且也要同時(shí)更新切牌而移除的紅牌或黑牌
一下是我的沒人品的代碼：（我這么說一點(diǎn)都不過分）
#include<iostream>
#include<cstring>
#define MaxN 100005
char deck[MaxN];
int main()
{
int numR,numS,i,k,remR,remS,len;
while(scanf("%s",deck)!=EOF){
remR=remS=numR=numS=k=0;
len=(int)strlen(deck);
for(i=0;i<len;i++){
if(deck[i]=='R')numR++;
else numS++;
if(numR-remR>numS-remS){
remR=numR;
remS=numS;
k=i+1;}
}
printf("%d\n",k);
}
return 0;
}
D題 DICE
這是按照解題報(bào)告寫得，是一道動(dòng)態(tài)規(guī)劃題，動(dòng)態(tài)規(guī)劃還是要堅(jiān)持繼續(xù)做，每次都靠蒙著想到是不行的
要用眼睛直接發(fā)現(xiàn)它。
這道題首先用一compute函數(shù)把每次用size[]的篩子，擲numSize下的所得每種可能結(jié)果的概率保存在p中
void compute(double p[],int size[],int numSize)
在主函數(shù)中我們分別把A,B的結(jié)果的計(jì)算出來
而后對B進(jìn)行處理，這里同樣是利用動(dòng)態(tài)規(guī)劃的思想，將pB[i]中，點(diǎn)數(shù)〈i的概率保存在tmp[i]中
然后結(jié)合tmp[],pA[]，計(jì)算結(jié)果輸出。
容易出錯(cuò)點(diǎn)：
在compute函數(shù)中for(j=MaxS-1;j>=0;j--){
p[j]=0;//這里要先初始化為0，在下一格6個(gè)size中，每種size的概率都要加
for(t=0;t<6;t++)
if(j-size(t)>0)//這里也是容易出錯(cuò)的，runtime error的起源
p[j]+=p[j-size[t]]/6.0;//這里也是，6.0，而不是6，要養(yǎng)成習(xí)慣
#include<iostream>
#define MaxS 23*100//每次最多丟到100
int sizeA[6],sizeB[6];
double pA[MaxS],pB[MaxS];
int numDiceA,numDiceB;
void compute(double p[],int size[],int numSize)
{
int i,j,t;
for(i=1;i<numSize;i++)
for(j=MaxS-1;j>=0;j--){
p[j]=0;//important
for(t=0;t<6;t++)
if(j-size[t]>0)
p[j]+=p[j-size[t]]/6.0;
}
}
int main()
{
int i;
double ans,tmp[MaxS];
while(scanf("%d%d",&numDiceA,&numDiceB)!=EOF){
ans=0.0;
memset(tmp,0,sizeof(tmp));
memset(pA,0,sizeof(pA));
memset(pB,0,sizeof(pB));
for(i=0;i<6;i++){
scanf("%d",&sizeA[i]);
pA[sizeA[i]]+=1/6.0;}
for(i=0;i<6;i++){
scanf("%d",&sizeB[i]);
pB[sizeB[i]]+=1/6.0;}
compute(pA,sizeA,numDiceA);
compute(pB,sizeB,numDiceB);
for(i=1;i<MaxS;i++)
tmp[i]=tmp[i-1]+pB[i-1];
for(i=1;i<MaxS;i++)
ans+=pA[i]*tmp[i];
printf("%.9lf\n",ans);
}
return 0;
}
未完待續(xù)..............
posted @
2008-04-07 21:47 zoyi 閱讀(204) |
評論 (0) |
編輯 收藏
好不容易寫的一個(gè)模版~本來是想按照我們數(shù)據(jù)結(jié)構(gòu)教程的trie樹來寫，但是他的實(shí)現(xiàn)我實(shí)在覺得太難
所以還是采用簡化版的trie樹
這個(gè)應(yīng)該算是比較標(biāo)準(zhǔn)的trie樹結(jié)構(gòu)，但是他的插入實(shí)現(xiàn)起來不僅僅是插入本身的單詞，可能還需要修改原來的數(shù)結(jié)構(gòu)
比如說本身已經(jīng)存在了bobwhite，現(xiàn)在添加bobwhq，就要在第二層的基礎(chǔ)上繼續(xù)擴(kuò)展，bobwhite的位置也要重新定位，刪除操作也是這樣
可能還要上移某些單詞，這個(gè)昨天試了很久，寫出來的都不行。
而且對這種字典樹的結(jié)構(gòu)本身我的理解就很混亂。
簡化版的trie樹
以下這種實(shí)現(xiàn)方法是根據(jù)別人改編的，昨天被逼得沒辦法還是覺得簡化版的，突然發(fā)現(xiàn)個(gè)牛人的寫法和我的很相似（這著實(shí)還讓我激動(dòng)了下下），就邊學(xué)習(xí)邊改了，呵呵
它是根據(jù)杭電的一道題來寫的，以下是我的代碼：
http://acm.hdu.edu.cn/showproblem.php?pid=1247
#include<iostream>
#define keyNum 26
#define MaxN 50
struct trie{
struct trieNode{//trie結(jié)點(diǎn)的結(jié)構(gòu)
trieNode *link[keyNum];//下標(biāo)為 'A' , 'B' , 'C' , 
, 'Z' 的指針數(shù)組
int num[keyNum];//插入key的次數(shù)
trieNode(){
memset(num,0,sizeof(num));
memset(link,NULL,sizeof(link));
}
void init(){
memset(link,NULL,sizeof(link));
memset(num,0,sizeof(num));
}
};
trieNode* root;
trie()
{
root=(trieNode*)malloc(sizeof(trieNode));//初始化時(shí)為root申請了空間
root->init();
}
bool Search(char *);
void Insert(char []);
void Delete(trieNode*);
};
bool trie::Search(char * x)
{
if(*x==0)return false;
trieNode* current=root;
x++;
while(*x){
if(current->link[*(x-1)-'a'])
current=current->link[*(x-1)-'a'];
else break;
x++;
}
if(*x==0&¤t->num[*(x-1)-'a'])
return true;
else return false;
}
void trie::Delete(trieNode* t)
{
int i;
for(i=0;i<keyNum;i++)
if(t->link[i])Delete(t->link[i]);
memset(t->num,0,sizeof(t->num));
delete(t);
}
void trie::Insert(char x[])
{
trieNode *current=root;
int i=1;
while(x[i]){
if(current->link[x[i-1]-'a']==NULL){
current->link[x[i-1]-'a']=(trieNode*)malloc(sizeof(trieNode));
(current->link[x[i-1]-'a'])->init();
}
current=current->link[x[i-1]-'a'];
i++;
}
(current->num[x[i-1]-'a'])++;
}
char c[ 50000 ][MaxN],tmp;
int main()
{
trie a;
int i=0,j,num;
while(scanf("%s",c[i])!=EOF)
a.Insert(c[i++]);
num=i;
for(i=0;i<num;i++)
for(j=1;c[i][j];j++){
tmp=c[i][j];
c[i][j]=0;
if(a.Search(c[i])){
c[i][j]=tmp;
if(a.Search(&c[i][j])){
printf("%s\n",c[i]);
break;}
}
else c[i][j]=tmp;
}
a.Delete(a.root);
return 0;
}
這個(gè)模版還不是很完善~用起來還是不大方便，比如刪除節(jié)點(diǎn)，我的刪除只是寫了刪所有的，用遞歸寫的。
還有遍歷節(jié)點(diǎn)，都不是很方便的。
以上代碼解釋幾點(diǎn)：
首先我構(gòu)造了一格trie的結(jié)構(gòu)：在此結(jié)構(gòu)中有root，和這棵樹的基本三個(gè)操作
再次trie結(jié)構(gòu)中的每個(gè)節(jié)點(diǎn)都是trieNode的結(jié)構(gòu)，包括root也是
這棵樹是動(dòng)態(tài)生成的，所以對trieNode的init很重要，這點(diǎn)寫過的就知道，不Init會(huì)出現(xiàn)很多問題的,
在trieNode結(jié)構(gòu)中主要有26個(gè)link和26個(gè)num，剛開始我自己寫的時(shí)候就是這26個(gè)num搞不清，只寫了一個(gè)num，這是對樹結(jié)構(gòu)的理解混亂造成的
num在這里是標(biāo)記這個(gè)單詞插入的次數(shù)，為0表示這個(gè)單詞還沒有被插入過
trieNode還有個(gè)很重要的成員函數(shù)就是init了。
posted @
2008-04-06 13:09 zoyi 閱讀(3166) |
評論 (3) |
編輯 收藏
摘要:
1***********1934******************************** 2----------------------------------------------- 3#include<iostream> 4#define Max 30 5using name...
閱讀全文
posted @
2008-03-09 14:05 zoyi 閱讀(246) |
評論 (1) |
編輯 收藏
本來都打定主意叫它幾十次，這道題考慮了很多細(xì)節(jié)，想了很多邊界條件，一次交過了還是沒想到的
我也不知道這道題到底要不要考慮那些邊界條件，不過看交過的比例，要注意的肯定很多，也許還有應(yīng)該要想到的
這是第一次作實(shí)數(shù)的高精度，寫的很亂，很多都是發(fā)現(xiàn)問題后不上去的
1#include<iostream>
2using namespace std;
3#define Max 200
4#define Max_b 7
5typedef struct bigint{
6 int data[Max];//從0開始存儲(chǔ)
7 int len;
8 int i;//表示小數(shù)位
9 bigint()
10 {
11 memset(data,0,sizeof(data));
12 len=1;
13 i=0;
14 }
15 friend bigint operator+(bigint,bigint);
16 friend bigint operator*(bigint,bigint);
17 void print();//小數(shù)點(diǎn)在第i位上，后面有i個(gè)小數(shù)位
18 void operator=(const bigint&y){
19 len=y.len;
20 for(int j=0;j<y.len;j++)
21 data[j]=y.data[j];
22 i=y.i;
23 }
24}BIGINT;
25BIGINT operator+(BIGINT x,BIGINT y)
26{
27 BIGINT r;
28 int rlen=x.len>y.len?x.len:y.len;
29 int tmp,i,jinwei=0;
30 for(i=0;i<rlen;i++){
31 tmp=x.data[i]+y.data[i]+jinwei;
32 r.data[i]=tmp%10;
33 jinwei=tmp/10;}
34 if(jinwei)r.data[rlen++]=jinwei;
35 r.len=rlen;
36 return r;
37}
38BIGINT operator*(BIGINT x,BIGINT y)
39{
40 BIGINT r;
41 int i,j;
42 memset(r.data,0,sizeof(r.data));
43 r.len=x.len+y.len;
44 for(i=0;i<x.len;i++)
45 for(j=0;j<y.len;j++)
46 r.data[i+j]+=x.data[i]*y.data[j];
47 for(i=0;i<r.len;i++){
48 r.data[i+1]+=r.data[i]/10;
49 r.data[i]%=10;}
50 while(r.data[i]){
51 r.data[i+1]+=r.data[i];
52 r.data[i]%=10;
53 i++;}
54 while(i>=0&&!r.data[i])i--;//這個(gè)已經(jīng)消除了開頭的零
55 //末尾不存在零，不用考慮
56 if(i!=-1)r.len=i+1;
57 else r.len=1;//r為0的情況
58 r.i=x.i+y.i;
59 return r;
60}
61void BIGINT::print()
62{
63 int j,k;
64 for(j=this->len-1;j>=this->i;j--)//輸出了len-i個(gè)或是一個(gè)也還沒輸出
65 printf("%d",this->data[j]);
66 if(j==-1){
67 putchar('\n');
68 return;}
69 putchar('.');
70 if(j<this->i)//小數(shù)點(diǎn)后要補(bǔ)零
71 for(k=this->i-1;k>j;k--)
72 putchar('0');
73 for(;j>=0;j--)
74 printf("%d",this->data[j]);
75 putchar('\n');
76}
77BIGINT cToBigint(char c[])
78{
79 int clen=(int)strlen(c),i=0,j=clen-1,k;
80 BIGINT result;
81 memset(result.data,0,sizeof(result.data));
82 while(c[i]=='0'&&i<clen-1)i++;
83 while(c[j]=='0'&&j>=0)j--;
84 if(j>i){
85 result.len=j-i;
86 for(j=result.len-1;c[i]!='.';j--,i++)
87 result.data[j]=c[i]-'0';
88 result.i=j+1;
89 for(i++;j>=0;j--,i++)
90 result.data[j]=c[i]-'0';}
91 else if(j<i){//
92 result.len=1;
93 result.i=0;}
94 else if(i==j&&c[i]!='.'){//完全就是整數(shù)，沒有小數(shù)點(diǎn)
95 for(j=clen-1,k=0;j>=i;j--,k++)
96 result.data[k]=c[j]-'0';
97 result.len=k;
98 result.i=0;
99 }
100 return result;
101}
102int main()
103{
104 BIGINT R,result;
105 int n,i;
106 char c[Max_b];
107 while(scanf("%s %d",c,&n)!=EOF){
108 memset(result.data,0,sizeof(result.data));
109 result.i=0;
110 result.len=1;
111 R=cToBigint(c);
112 result.data[0]=1;
113 for(i=1;i<=n;i++)
114 result=result*R;
115 result.print();
116 }
117 return 0;
118}
posted @
2008-03-09 14:00 zoyi 閱讀(566) |
評論 (0) |
編輯 收藏