• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>
            我叫張小黑
            張小黑的掙扎生活
            posts - 66,  comments - 109,  trackbacks - 0
            都寫了三份了,實在不想加重以前隨筆的負擔
            所以只好另起爐灶。
            F:Face Formations
            這道題據說是組合數學的題,但是我是用動態規劃作的
            上windows實在聽不進課,就在草稿紙上胡寫亂畫,莫名其妙的模擬出來了
            主要我是要填表,狀態方程,我不知道該怎么寫,我模擬下過程好了:
            4
            1 2 4 7
            137 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: 這個表我的填表過程是從下至上,從右至左
            結果是在[1][1]的位置上,我代碼實現的時候只開了一個數組,因為并不需要把整個表都存下來
            以下是我的代碼:
            #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 閱讀(304) | 評論 (3)編輯 收藏

            2008年4月10日23:52:47
            第一個問題:
            由平面中的n條直線確定的最大區域數Ln
             L0=1;
            Ln=Ln-1+n(n>0);
            Ln=1+n*(n+1)/2;

            第二個問題:
            是平面直線的變形問題,用彎曲的線來代替直線,每一個彎曲線含有一個“鋸齒形的轉角”,同樣確定平面區域的最大個數Zn
            (我們把一條彎曲折線抽象為兩條,但是合并了某些區域)
            Zn=L2n-2*n=2*n*n-n+1;(n>=0);

            第三個問題:
            就是一下這個問題:
            count the regions

            若當前有n-1條邊,那么在往里面加一條邊,這條新加的邊最多和以前的邊有9*(n-1)個交點,
            那么會添加 9*(n-1)+1個面
            這條規律對于上面兩種也是用,加x個點,那么就會添加x+1個面

            那么總結下來 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 閱讀(302) | 評論 (2)編輯 收藏
                 摘要: 大家有好的代碼請發我郵箱:zhangjia888334@sohu.com 今天就作了廣搜三道題,做個小節。首先要糾正腦子里的一個錯誤觀念,以前的我的廣搜模式就是開個隊列,走過的點不能走,隊列的類型我還必定是用結構體來做結構體里放個x,y,n,x-->橫坐標,y-->縱坐標,n-->步數再來幾個標準的二維數組,map[Maxh][Maxw]-->描述地圖,visit...  閱讀全文
            posted @ 2008-04-10 00:57 zoyi 閱讀(345) | 評論 (0)編輯 收藏
            http://acm.pku.edu.cn/JudgeOnline/problem?id=2513
            這道題是直接拿前幾天寫得模版改的;做了幾個修改
            首先刪掉了search,這道題的確不需要,本來沒刪,代碼實在太長,逼得我沒辦法
            第二個,把trie中num[]的意思改掉了,num[]現在存的是字符串在一個數組的標記,
            相當于map的實現,通過這樣我把一個字符串和一個標號對應上了,方便了并查集的操作
            果然很久沒碰并查集了,一寫就出問題,
            主要是我union_set是居然忘了要先find_set一下,這樣寫針對下面這組數據就會出現問題:
            a b
            b a
            a a
            還有一個就是這道題的空輸入問題,要輸出possible,而不是Impossible
            一下是我的垃圾代碼,跑了500多,有誰有更好的發我郵箱哈: zhangjia888334@sohu.com
            #include<iostream>
            #include
            <cstring>
            #define keyNum 
            26
            #define MaxN 
            500005
            struct node{
                
            int parent;
                
            int rank;
                
            int num;//這個顏色出現的次數
                node()
                {
                    num
            =rank=0;
                    parent
            =-1;
                }
            };
            node colour[MaxN];
            int id=0;//數組標記
            struct trie{
                struct trieNode{
            //trie結點的結構
                trieNode 
            *link[keyNum];//下標為 'a' , 'b' , 'c' ,  , 'z' 的指針數組
                int num[keyNum];//插入這個單詞在數組中的位置
                trieNode(){
                    memset(num,
            -1,sizeof(num));//-1表示還未插入數組
                    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));//初始化時為root申請了空間
                    root
            ->init();
                }
                
            int Insert(char []);//返回數組中的位置
                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++;//出現的次數++
                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)//一個沒回路,一個是有回路
                    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));
                }
                
            //下面判斷有幾個parent,若有多個失敗
                solve();
                a.Delete(a.root);
                return 
            0
            }
            posted @ 2008-04-08 18:35 zoyi 閱讀(885) | 評論 (1)編輯 收藏


            寢室里很亂,明天我要收拾,收拾好它也收拾好自己

            還是很想把博客經營下去,以前不想寫,其實是害怕別人看,我貼的都是水題
            丟人吶,但是這是我成長的過程
            隱藏東西的感覺還真好玩

            我是棵小白菜,從來都是,也沒奢望過會成為參天大樹
            但是我會慢慢澆灌,小白菜總不至于被我澆成蔥了吧,哈哈

            呵呵,繼續隱藏
            就這樣,待續.........

            fighting~~!!!
            posted @ 2008-04-08 00:55 zoyi 閱讀(201) | 評論 (2)編輯 收藏
            我的青蛙終于過了
            完全忘了算法導論上說的理論了~~其實以前寫的就只有一個小錯誤
            ax+ny=b;
            當求解x時,我們先用擴展歐幾里德extended_eculid(a,n,&x',&y');
            通過計算的x'和y'來計算x
            x可能沒解,也可能有d個不同的解
            當求解某些問題的時候,我們要求得到最小正解,如果x'*(b/d)<0時,我們應該在此解的基礎上繼續加n/d
            青蛙問題我就是這里錯了,我是在最小解的基礎上加n,
            最好不要忘了對n取模。
            http://acm.pku.edu.cn/JudgeOnline/problem?id=1061
            //SA-SB=kL(k為整數)
            //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)(此時a'與b'互質)
            //若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的起始點,y為B的起始點
                
            //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;//這里錯了,最小的那個不是這么加的
                        p
            =p%l;
                        printf(
            "%I64d\n",p);
                    }
                }}
                return 
            0;
            }

            E Encrypted
            這道題就是簡單的應用擴展的歐幾里德,并不涉及模線性方程
            #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 閱讀(196) | 評論 (0)編輯 收藏
              A:Ambitious number
            http://202.120.80.191/problem.php?problemid=1868
            這道題想法其實不難,可是開始的方向就錯了,做的時候有種投機取巧的感覺,雖然知道是錯的,但是我也要去試,呵呵,一頭撞到底
            首先打質數表,然后找到小與N的每個質數的最大系數,開始一頭就扎進了用倆數的乘積去除公約數的方法做,這顯然不對啊,要去模的阿,哎
            下面是垃圾代碼:
            #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題等會兒再說,他是我的痛
            http://202.120.80.191/problem.php?problemid=1869

            C題Cards
            http://202.120.80.191/problem.php?problemid=1870
            這道題開始用o(n2)的做的,并沒有想到該怎么做,后面超時,才是是這用o(n)的做,開始想的一直都不清楚
            主要是在每次當前移除情況下又出現了present_numR>present_numB的情況,就要更新切牌點,并且也要同時更新切牌而移除的紅牌或黑牌
            一下是我的沒人品的代碼:(我這么說一點都不過分)
            #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
            這是按照解題報告寫得,是一道動態規劃題,動態規劃還是要堅持繼續做,每次都靠蒙著想到是不行的
            要用眼睛直接發現它。
            這道題首先用一compute函數把每次用size[]的篩子,擲numSize下的所得每種可能結果的概率保存在p中
            void compute(double p[],int size[],int numSize)
            在主函數中我們分別把A,B的結果的計算出來
            而后對B進行處理,這里同樣是利用動態規劃的思想,將pB[i]中,點數〈i的概率保存在tmp[i]中
            然后結合tmp[],pA[],計算結果輸出。
            容易出錯點:
            在compute函數中for(j=MaxS-1;j>=0;j--){
                                                  p[j]=0;//這里要先初始化為0,在下一格6個size中,每種size的概率都要加
                                              for(t=0;t<6;t++)
                                             if(j-size(t)>0)//這里也是容易出錯的,runtime error的起源
                                            p[j]+=p[j-size[t]]/6.0;//這里也是,6.0,而不是6,要養成習慣
            #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;
            }
            未完待續..............


            posted @ 2008-04-07 21:47 zoyi 閱讀(192) | 評論 (0)編輯 收藏
            好不容易寫的一個模版~本來是想按照我們數據結構教程的trie樹來寫,但是他的實現我實在覺得太難
            所以還是采用簡化版的trie樹

            這個應該算是比較標準的trie樹結構,但是他的插入實現起來不僅僅是插入本身的單詞,可能還需要修改原來的數結構
            比如說本身已經存在了bobwhite,現在添加bobwhq,就要在第二層的基礎上繼續擴展,bobwhite的位置也要重新定位,刪除操作也是這樣
            可能還要上移某些單詞,這個昨天試了很久,寫出來的都不行。
            而且對這種字典樹的結構本身我的理解就很混亂。
            簡化版的trie樹

            以下這種實現方法是根據別人改編的,昨天被逼得沒辦法還是覺得簡化版的,突然發現個牛人的寫法和我的很相似(這著實還讓我激動了下下),就邊學習邊改了,呵呵
            它是根據杭電的一道題來寫的,以下是我的代碼:
            http://acm.hdu.edu.cn/showproblem.php?pid=1247
            #include<iostream>
            #define keyNum 
            26
            #define MaxN 
            50
            struct trie{
                struct trieNode{
            //trie結點的結構
                trieNode 
            *link[keyNum];//下標為 'A' , 'B' , 'C' ,  , 'Z' 的指針數組
                int num[keyNum];//插入key的次數
                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));//初始化時為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&&current->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;
            }
            這個模版還不是很完善~用起來還是不大方便,比如刪除節點,我的刪除只是寫了刪所有的,用遞歸寫的。
            還有遍歷節點,都不是很方便的。
            以上代碼解釋幾點:
            首先我構造了一格trie的結構:在此結構中有root,和這棵樹的基本三個操作
            再次trie結構中的每個節點都是trieNode的結構,包括root也是
            這棵樹是動態生成的,所以對trieNode的init很重要,這點寫過的就知道,不Init會出現很多問題的,
            在trieNode結構中主要有26個link和26個num,剛開始我自己寫的時候就是這26個num搞不清,只寫了一個num,這是對樹結構的理解混亂造成的
            num在這里是標記這個單詞插入的次數,為0表示這個單詞還沒有被插入過
            trieNode還有個很重要的成員函數就是init了。
            posted @ 2008-04-06 13:09 zoyi 閱讀(3152) | 評論 (3)編輯 收藏
                 摘要:    1***********1934******************************** 2----------------------------------------------- 3#include<iostream> 4#define Max 30 5using name...  閱讀全文
            posted @ 2008-03-09 14:05 zoyi 閱讀(234) | 評論 (1)編輯 收藏
            本來都打定主意叫它幾十次,這道題考慮了很多細節,想了很多邊界條件,一次交過了還是沒想到的
            我也不知道這道題到底要不要考慮那些邊界條件,不過看交過的比例,要注意的肯定很多,也許還有應該要想到的
            這是第一次作實數的高精度,寫的很亂,很多都是發現問題后不上去的
              1#include<iostream>
              2using namespace std;
              3#define Max 200
              4#define Max_b 7
              5typedef struct bigint{
              6    int data[Max];//從0開始存儲
              7    int len;
              8    int i;//表示小數位
              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();//小數點在第i位上,后面有i個小數位
             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--;//這個已經消除了開頭的零
             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個或是一個也還沒輸出
             65        printf("%d",this->data[j]);
             66    if(j==-1){
             67        putchar('\n');
             68        return;}
             69    putchar('.');
             70    if(j<this->i)//小數點后要補零
             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]!='.'){//完全就是整數,沒有小數點
             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 閱讀(555) | 評論 (0)編輯 收藏
            僅列出標題
            共7頁: 1 2 3 4 5 6 7 
            歡迎光臨 我的白菜菜園

            <2008年9月>
            31123456
            78910111213
            14151617181920
            21222324252627
            2829301234
            567891011

            常用鏈接

            留言簿(8)

            隨筆分類

            隨筆檔案

            文章檔案

            相冊

            acmer

            online judge

            隊友

            技術

            朋友

            搜索

            •  

            最新評論

            閱讀排行榜

            評論排行榜

            国内精品久久久久久久亚洲| 久久亚洲AV无码精品色午夜| 九九久久精品国产| 久久精品国产欧美日韩99热| 97久久香蕉国产线看观看| 久久99精品国产麻豆蜜芽| 亚洲色大成网站www久久九| 青青国产成人久久91网| 无码八A片人妻少妇久久| 日韩一区二区久久久久久 | 国产精品久久久久无码av| 国内精品久久久久国产盗摄| 亚洲国产精品无码久久久不卡| 国产99久久久国产精免费| 亚洲AV无码久久寂寞少妇| 久久久久18| 久久国产V一级毛多内射| 国产精品美女久久久m| 97久久婷婷五月综合色d啪蜜芽 | 99久久这里只有精品| 久久狠狠爱亚洲综合影院| 久久综合九色综合久99| 亚洲午夜精品久久久久久人妖| 久久精品蜜芽亚洲国产AV| 久久精品国产亚洲AV香蕉| 久久精品国产精品亚洲| 99久久综合狠狠综合久久止| 久久精品中文闷骚内射| 亚洲AV成人无码久久精品老人| 久久人人爽人人爽人人片AV不| 久久无码国产| 国产精久久一区二区三区| 久久福利青草精品资源站| 久久国产免费观看精品| 精品久久久久久无码专区不卡| 久久人人爽人人爽人人片AV不| 国内精品人妻无码久久久影院导航| 亚洲七七久久精品中文国产| 欧美午夜精品久久久久久浪潮| 亚洲а∨天堂久久精品9966| 亚洲精品乱码久久久久久不卡|