Uriel's Corner

Research Associate @ Harvard University / Research Interests: Computer Vision, Biomedical Image Analysis, Machine Learning
posts - 0, comments - 50, trackbacks - 0, articles - 594

POJ 1202---DFS+高精度

Posted on 2010-04-13 21:03 Uriel 阅读(720) 评论(0)  编辑 收藏 引用 所属分类: POJ搜索
        某周六想跟ZYY练习一下JAVA高精度,于是搜POJ分类,发现POJ1202就去做了。。然后就发现远不止高精度水题这么简单。。然后胡思乱想,想到了图论,想到了数据结构的树的知识,最后还是决定跟ZYY合作暴力之。。。
        由于我的DFS如此之差,DFS函数部分ZYY写~
        题意比较纠结,开始理解错了,WA数次之后搜数据才发现问题,当询问某两个结点的时候,先从第一个结点开始往上搜,直到搜到记录过的结点,右边也要这样做,每个结点的值是其父母的值相加除2,要用记忆化,如果右边搜搜到的结果比左边大的话要更新那些两个结点关系的值,否则不更新。
        这题恶心的地方不在DFS部分,而在于。。。高精度,用到了浮点数高精度加法,高精度比较函数,高精度除法,本来想用JAVA水过去,无奈我们的JAVA能力实在没办法做。。于是C++硬来。。贴上了高精度模板,浮点数除法函数不对,ZYY手写了一遍,然后又发现减法函数也不对,直接手写了高精度浮点数比较,然后昨天总算搞出了那一堆数据。。一交,TLE。。想着这么暴力肯定是过不了了。。后来ZYY说那个模板加法也很慢。。于是我开始手写。。昨天离开311的时候还是没能出sample,于是今天继续,ZYY帮忙改了main函数来配合那个不太正常的浮点数高精度加法。。之后总算出sample了。。一交,刷了N次,以为挂了,结果竟然一行蓝字,顿时开心无比啊~~
自己太水了。。搞了4天。。这题是我目前为止在POJ上过的题中AC人数最少的了。。
贴下WS的代码以示纪念(浮点数高精度加法那个函数只在这题适用,有问题的)
/*
Problem: 1202  User: Uriel 
Memory: 41488K  Time: 1782MS 
Language: G++  Result: Accepted 
*/

#include
<stdio.h>
#include
<stdlib.h>
#include
<string.h>
#define MAX 450
struct node
{
    
int p1,p2;
    
bool s1;
}
ss[305];
char map[305][305][450];

int Compare(const char *a, const char *b);
void IntAddition(char *augend, char *addend, char *sum);
//int  Radix(char *toStr, char *fromStr);
void FloatAddition(char *augend, char *addend, char *sum);
void FloatDivision(char *dividend, char *divisor, char *quotient, int precision);

int subcompare(char *str1,char *str2)
{
    
int len1=strlen(str1);
    
int len2=strlen(str2);
    
int tmp1=0;
    
int tmp2=0;
    
int pos1=0;
    
int pos2=0;
    
int i,j;
    
for(i=0;i<len1;i++)
    
{
        
if(str1[i]=='.')break;
        tmp1
=tmp1*10+str1[i]-'0';
    }

    pos1
=i;
    
for(i=0;i<len2;i++)
    
{
        
if(str2[i]=='.')break;
        tmp2
=tmp2*10+str2[i]-'0';
    }

    pos2
=i;
    
if(tmp1>tmp2)return 1;
    
else if(tmp2>tmp1)return -1;
    
else
    
{
        
for(i=pos1+1,j=pos2+1;i<len1,j<len2;i++,j++)
        
{
            
if(str1[i]<str2[j])return -1;
            
else if(str1[i]>str2[j])return 1;
        }

        
if(i==len1)return -1;
        
else 
            
return 1;
    }

}


void dfs(int n,int p,int q)
{
    
int i;
    
if(p==q)
        map[p][q][
0]='1',map[p][q][1]='0',map[p][q][2]='0',map[p][q][3]='.',map[p][q][4]='0',map[p][q][5]='\0';
    
else if(ss[p].s1==false && ss[q].s1==false)
        map[p][q][
0]='0',map[p][q][1]='.',map[p][q][2]='0',map[p][q][3]='\0';
    
if(map[p][q][0]!='\0')
        
return;
    
    
char two[5];
    memset(two,
'\0',sizeof(two));
    two[
0]='2';two[1]='\0';
    
char ans1[450]={0};
    
char ans2[450]={0};
    
if(ss[p].s1)
    
{
        
int p_1=ss[p].p1;
        
int p_2=ss[p].p2;
        
if(map[p_1][q][0]=='\0')
            dfs(n,p_1,q);
        
if(map[p_2][q][0]=='\0')
            dfs(n,p_2,q);
//        printf("ori:%s %s\n",map[p_1][q],map[p_2][q]);
        FloatAddition(map[p_1][q],map[p_2][q],ans1);
//        printf("add:%s\n",ans1);
        FloatDivision(ans1,two,ans2,300);
//        printf("div:%s\n",ans2);
        int n_1=strlen(ans2);
        
//for(i=0;i<n_1;i++)
        strcpy(map[p][q],ans2);
        
//return;
    }

    
if(ss[q].s1)
    
{
        
int q_1=ss[q].p1;
        
int q_2=ss[q].p2;
        
if(map[p][q_1][0]=='\0')
            dfs(n,p,q_1);
        
if(map[p][q_2][0]=='\0')
            dfs(n,p,q_2);
//        printf("ori:%s %s\n",map[p][q_1],map[p][q_2]);
        FloatAddition(map[p][q_1],map[p][q_2],ans1);
//        printf("add:%s\n",ans1);
        FloatDivision(ans1,two,ans2,300);
//        printf("div:%s\n",ans2);
        int n_1=strlen(ans2);
//        FloatSubtration(ans2,map[p][q],ans1);
//        if(ans1[0]!='-')
        
//for(i=0;i<=n_1;i++)
        if(subcompare(ans2,map[p][q])>0)
        
{
            strcpy(map[p][q],ans2);
        }

        
//return;
    }

    
return;
    
}

int main()
{
    freopen(
"out.txt","w",stdout);
    
int n,k;
    
int i,j,a,b,c,p,q;
    
char sss[450];
    scanf(
"%d %d",&n,&k);
    
        
for(i=0;i<=n;i++)
            ss[i].s1
=false;
        
for(i=1;i<=k;i++)
        
{
            scanf(
"%d %d %d",&a,&b,&c);
            ss[a].p1
=b;
            ss[a].p2
=c;
            ss[a].s1
=true;
        }

        
//memset(map,'\0',sizeof(map));
        for(i=0;i<305;i++)
            
for(j=0;j<305;j++)
                map[i][j][
0]='\0';
        scanf(
"%d",&k);
        
while(k--)
        
{
            scanf(
"%d %d",&p,&q);
            dfs(n,p,q);
            
int n1=strlen(map[p][q]);
            strcpy(sss,map[p][q]);
            
bool f1=0;
            
for(i=0;i<n1;i++)
            
{
                 
if(map[p][q][i]=='.')
                 
{
                      f1
=1;
                      
break;                     
                 }
                 
            }

            
if(f1)
            
{
                
for(i=n1-1;i>=0;i--)
                
{
                     
if(map[p][q][i]!='0')
                     
{
                          
if(map[p][q][i]=='.')
                          map[p][q][i]
='\0';
                          
else
                          map[p][q][i
+1]='\0';
                          
break;
                     }
                    
                }

            }

            
if(strlen(map[p][q])==0)printf("0%%\n",map[p][q]);
            
else
                printf(
"%s%%\n",map[p][q]);
            strcpy(map[p][q],sss);
        }

    system(
"PAUSE");
    
return 0;
}



void FloatDivision(char *dividend, char *divisor, char *quotient, int precision)
{
    
char ans[MAX];
    
int n1=strlen(dividend);
    
int i,j;
    
bool f1=false;
    
for(i=0;i<n1;i++)
    
{
        
if(dividend[i]=='.')
        
{
            ans[i]
='.';
            
continue;
        }

        j
=dividend[i]-'0';
        
if(f1)
            j
+=10;
        ans[i]
=j/2+'0';
        
if((dividend[i]-'0')%2==1)
            f1
=true;
        
else
        f1
=false;
    }

    
if(f1)
        ans[i
++]='5';
    ans[i]
='\0';
    n1
=strlen(ans);
    j
=0;
    
for(i=0;i<n1;i++)
    
{
        
if(ans[i]!='0')
        
{
            
if(ans[i]=='.')
                i
--;
            
break;
        }

    }

    
for(;i<=n1;i++)
    
{
        quotient[j
++]=ans[i];
    }

}


void FloatAddition(char *augend, char *addend, char *sum)
{
    
int len1=strlen(augend);
    
int len2=strlen(addend);
    
int i,j,cf;
    
int tpos1,tpos2;
    
int respos;
    
int pos1,pos2;
    
for(i=0;i<450;i++)
    
{
        sum[i]
='0';
    }

    
for(i=0;i<len1;i++)
    
{
        
if(augend[i]=='.')break;
    }

    
if(i==len1-1)
    
{
        augend[i
+1]='0';
        len1
++;
//        i++;
    }

    
if(i==len1)
    
{
        augend[i]
='.';
        i
++;
        len1
++;
        len1
++;
        augend[i
+1]='0';
    }

    pos1
=i;
    
for(i=0;i<len2;i++)
    
{
        
if(addend[i]=='.')break;
    }

    
if(i==len2-1)
    
{
        addend[i
+1]='0';
        len2
++;
//        i++;
    }

    
if(i==len2)
    
{
        addend[i]
='.';
        i
++;
        addend[i
+1]='0';
        len2
++;
        len2
++;
    }

    pos2
=i;
    respos
=449;
    
if(len1-pos1<len2-pos2)
    
{
//        printf("*\n");
        tpos2=len2-1;
        tpos1
=len1-1;
//        printf("pos1=%d pos2=%d\n",len1-pos1,pos2);
        while(len1-pos1<=tpos2-pos2)
        
{
            sum[respos
--]=addend[tpos2];
            tpos2
--;
        }

        
if(addend[tpos2]=='.')tpos2--;
//        printf("sum=%s\n",sum);
//        printf("tpos1=%d\n",tpos1);
        cf=0;
        
while(tpos1>pos1)
        
{
            sum[respos
--]=(addend[tpos2]+augend[tpos1]+cf-'0'-'0')%10+'0';
            cf
=(addend[tpos2]+augend[tpos1]+cf-'0'-'0')/10;
            tpos2
--;
            tpos1
--;
        }

//        printf("*\n");
        tpos1--;
        tpos2
--;
        sum[respos
--]='.';
        
while(tpos1>=0 && tpos2>=0)
        
{
            sum[respos
--]=(addend[tpos2]+augend[tpos1]+cf-'0'-'0')%10+'0';
            cf
=(addend[tpos2]+augend[tpos1]+cf-'0'-'0')/10;
            tpos2
--;
            tpos1
--;
        }

//        printf("*\n");
//        printf("tpos1=%d tpos2=%d\n",tpos1,tpos2);
        if(tpos2>=0)
        
{
            
while(tpos2>=0)
            
{
                sum[respos
--]=(addend[tpos2]+cf-'0')%10+'0';
                cf
=(addend[tpos2]+cf-'0')/10;
                tpos2
--;
            }

        }

        
else if(tpos1>=0)
        
{
            
while(tpos1>=0)
            
{
                sum[respos
--]=(augend[tpos1]+cf-'0')%10+'0';
                cf
=(augend[tpos1]+cf-'0')/10;
                tpos1
--;
            }
            
        }

        
if(cf!=0)
        
{
            sum[respos
--]=cf+'0';
        }

    }

    
else
    
{
//        printf("*\n");
        tpos2=len2-1;
        tpos1
=len1-1;
//        printf("pos1=%d pos2=%d\n",pos1,pos2);
        while(len2-pos2<=tpos1-pos1)
        
{
            sum[respos
--]=augend[tpos1];
            tpos1
--;
        }

        
if(augend[tpos1]=='.')tpos1--;
//        printf("tpos1=%d\n",tpos1);
        cf=0;
        
while(tpos1>pos1)
        
{
            sum[respos
--]=(addend[tpos2]+augend[tpos1]+cf-'0'-'0')%10+'0';
            cf
=(addend[tpos2]+augend[tpos1]+cf-'0'-'0')/10;
            tpos2
--;
            tpos1
--;
        }

//        printf("*\n");
        tpos1--;
        tpos2
--;
        sum[respos
--]='.';
        
while(tpos1>=0 && tpos2>=0)
        
{
            sum[respos
--]=(addend[tpos2]+augend[tpos1]+cf-'0'-'0')%10+'0';
            cf
=(addend[tpos2]+augend[tpos1]+cf-'0'-'0')/10;
            tpos2
--;
            tpos1
--;
        }

//        printf("*\n");
//        printf("tpos1=%d tpos2=%d\n",tpos1,tpos2);
        if(tpos2>=0)
        
{
            
while(tpos2>=0)
            
{
                sum[respos
--]=(addend[tpos2]+cf-'0')%10+'0';
                cf
=(addend[tpos2]+cf-'0')/10;
                tpos2
--;
            }

        }

        
else if(tpos1>=0)
        
{
            
while(tpos1>=0)
            
{
                sum[respos
--]=(augend[tpos1]+cf-'0')%10+'0';
                cf
=(augend[tpos1]+cf-'0')/10;
                tpos1
--;
            }
            
        }

        
if(cf!=0)
        
{
            sum[respos
--]=cf+'0';
        }

//        printf("*\n");
    }

//    printf("*\n");
    for(i=0;;i++)
    
{
        
if(sum[i]!='0')break;
    }

    
if(sum[i]=='.')i--;
    
for(j=i;j<450;j++)
    
{
        sum[j
-i]=sum[j];
    }

    sum[j
-i]='\0';
    
if(sum[strlen(sum)-1]=='.')
    
{
        
int xx=strlen(sum);
        sum[xx]
='0';
        sum[xx
+1]='\0';
    }

}


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理