|
|
Posted on 2010-04-13 21:03 Uriel 閱讀(732) 評論(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';
}
}
|