}
voidHPplus(int*a,int*b,int*c)
{
inti,j;
j=0;
for(i=1;i<=min(a[0],b[0]);i++)
{
c[i]=a[i]+b[i]+j;
j=c[i]/10;
c[i]%=10;
}
if(j!
=0)c[i]=j;
c[0]=a[0]>b[0]?
a[0]+2:
b[0]+2;
while(c[c[0]]==0&&c[0]>1)c[0]--;
}
voidHPmultyNUM(int*a,intb,int*c)
{
inti,j,k;
for(i=1;i<=a[0];i++)
c[i]+=a[i]*b;
k=0;
for(j=1;j<=a[0];j++)
{
c[j]+=k;
k=c[j]/10;
c[j]%=10;
}//进位
if(k!
=0)c[j]=k;
c[0]=a[0]+3;
while(c[c[0]]==0&&c[0]>1)c[0]--;
}
intmain()
{
inti,j,t[300],test;
f[0][0]=1;f[0][1]=1;
f[1][0]=1;f[1][1]=1;f[2][0]=1;f[2][1]=3;
for(i=3;i<=250;i++)
{
memset(t,0,sizeof(t));
HPmultyNUM(f[i-2],2,t);
HPplus(t,f[i-1],f[i]);
}
while(cin>>test)
HPprint(f[test]);
return0;
}
POJ1079Ratio分数操作
题目大意:
给出一个分数,比如1498/902。
求出当分母分别为1,2,....的时候,最接近1498/902的分数。
比如:
当分母为1的时候,最接近1498/902的分数为1/1。
当分母为2的时候,最接近1498/902的分数为3/2。
当分母为3的时候,最接近1498/902的分数为5/3。
。
。
。
思路:
不要用高精度哦,直接模拟分数的操作最好了。
#include
#include
structfrac{
__int64up,down;
};
__inline__int64gcd(__int64a,__int64b)
{
__int64r;
if(a
r=a;
a=b;
b=r;
}
while
(1){
r=a%b;
if(!
r)
returnb;
a=b;
b=r;
}
}
__inlinestructfracfrac_init(__int64up,__int64down)
{
__int64r,s;
structfracf;
r=up?
gcd(up,down):
1;
if(r<0)
r=-r;
f.up=up/r;
f.down=down/r;
returnf;
}
__inlinestructfracfrac_sub(structfracfa,structfracfb)
{
returnfrac_init(fa.up*fb.down-fa.down*fb.up,fa.down*fb.down);
}
__inline__int64frac_cmp(structfracfa,structfracfb)
{
returnfrac_sub(fa,fb).up;
}
__inlinestructfracfrac_abs(structfracf)
{
if(f.up<0)
f.up=-f.up;
returnf;
}
intmain()
{
__int64up,down;
structfractarget,min_dis,f,dis;
while(scanf("%I64d%I64d",&up,&down)!
=EOF){
target=frac_init(up,down);
min_dis.down=1;
min_dis.up=(__int64)1e15;
for(down=1;down<=target.down;down++){
up=(down*target.up)/target.down;
if(((down*target.up)%target.down)*2>=target.down)
up++;
f=frac_init(up,down);
dis=frac_abs(frac_sub(f,target));
if(frac_cmp(dis,min_dis)<0){
printf("%I64d/%I64d\n",f.up,f.down);
min_dis=dis;
}
}
printf("\n");
}
return0;
}
poj1019NumberSequence(找规律)
找规律的题目:
先计算出从1到n这个小区间有多长,保存到digit[]数组中,然后计算从112123到n一共有多少位数字,然后根据输入数据查找,其中我在找那一位时比较暴力,把从1开始一直存放,直到存放的比那一位还多,然后取出那一位。
#include
#include
#include
#include
usingnamespacestd;
constintMaxSize=100000+10;
__int64digit[MaxSize],len[MaxSize];
stringstreamss;
voidinit()
{
inti;
digit[1]=len[1]=1;
for(i=2;idigit[i]=digit[i-1]+(int)log10((double)i)+1;
len[i]=len[i-1]+digit[i];
}
/*for(i=1;i<10;++i){
cout<
}*/
}
chargetDigit(intnum)
{
inti;
for(i=1;len[i];
intpos=num-len[i-1];
//清空ss
ss.str("");
for(i=1;i<=pos;++i){
ss<
//cout<}
return(ss.str())[pos-1];
}
intmain()
{
inti,sets,num;
init();
cin>>sets;
while(sets--){
cin>>num;
cout<}
return0;
}
POJ1095TreesMadetoOrder
思路:
首先,设拥有N个结点的不同形态的有序二叉树有L[N]棵。
L[N]即为卡特兰数。
那么:
(1).针对这个问题先转换为输入N,求n和k。
n表示编号为N的树所拥有的结点数。
k表示这棵编号为N的树是拥有结点数为n的树的有序集合的第几棵。
我们可以先将Catalan数表打出来:
intL[19]={1,1,2,5,14,42,132,429,1430,4862,16796,58786,208012,742900,2674440,9694845,35357670,129644790,477638700};
对于输入的N,可以求出n=min(j|L[0]+L[1]+...+L[j]>=N)。
而k=n-L[0]-L[1]-...-L[n-1]。
鉴于二叉树的固有特性,我可以构造递归函数fun(n,k)。
即打印出拥有n个结点树的第k种状态。
(2).继续转化问题,这棵树的左子树和右子树各有结点数多少?
设这棵树左子树的结点数为i,右子树的结点数为n-i-1,那么这棵树是又左子树的结点数为i,右子树的结点数为n-i-1的形态的第几种(设为第s种)?
可以知道当1<=k<=L[0]*L[n-1]时,左子树结点树为0,右子树结点数为n-1,s=k;L[0]*L[n-1]+1<=k<=L[1]*L[n-2]时,,左子树结点树为1,右子树结点数为n-2,s=k-L[0]*L[n-1];...当L[i-1]*L[n-i]+1<=L[i]*L[n-i+1]时,左子树结点树为i,右子树结点数为n-i-1,s=k-L[0]*L[n-1]-...L[i-1]*L[n-i]。
(3).继续想象s增长的过程即为树形态不断发生变化的过程。
那么首先是右子树在发生变化,从1到L[n-i-1]。
继续增长,右子树的形态复位为1,而左子树的形态增加1.因此右子树相当于秒针,左子树相当于分针。
对于s,该树的左子树编号为(s-1)/L[n-i-1]+1,右子树编号为(s-1)%L[n-i-1]+1。
(4).fun(n,k)的递归终止条件很容易知道,为n==1。
此时树的形态只有一种,所以直接打印X。
(5).综上所述,fun(n,k)的形式为:
fun(n,k){
if(1==n)打印X,返回。
求出s,i;
If(i>0){打印(;fun(i,(s-1)/L[n-i-1]+1);打印);}
打印X;
If(n-i-1>0){打印(;fun(n-i-1,(s-1)%L[n-i-1]+1);打印);}
}
至此,问题得到了解决。
#include
intL[19]={1,1,2,5,14,42,132,429,1430,4862,16796,58786,208012,742900,2674440,9694845,35357670,129644790,477638700};
voidfun(intn,intk){
inti,sum=0;
if(1==n){putchar('X');return;}
for(i=0;k>sum;i++)sum+=L[i]*L[n-i-1];
i--;
sum-=L[i]*L[n-i-1];
k-=sum;
if(i){
putchar('(');
fun(i,(k-1)/L[n-i-1]+1);
putchar(')');
}
putchar('X');
if(n-i-1){
putchar('(');
fun(n-i-1,(k-1)%L[n-i-1]+1);
putchar(')');
}
}
intmain(){
intn,i,j,sum;
while(scanf("%d",&n)&&n){
sum=0;
for(i=1;n>sum;i++)sum+=L[i];
i--;
fun(i,n-sum+L[i]);
putchar('\n');
}
return0;
}
POJ1905ExpandingRods
#include
#include
#include
usingnamespacestd;
intmain(intargc,char*argv[])
{
doubleN,C,L;
while(scanf("%lf%lf%lf",&L,&N,&C)&&N>=0&&C>=0&&L>=0)
{
if(N==0||L==0||C==0)
{
printf("0.000\n");
continue;
}
doubleminv=0,maxv=acos(-1.0),midv;
doubleL2=(1+N*C)*L;
while(maxv-minv>1e-12)
{
midv=(minv+maxv)/2;
if(2*L2/L>midv/sin(midv/2))
minv=midv;
else
maxv=midv;
}
printf("%.3lf\n",L2/midv*(1-cos(midv/2)));
}
return0;
}
POJ1064Cablemaster
AC率较低的题,也是很明显的二分题,但是由于精度问题WA了很多次,最终看discuss过的,这题一个很重要的精度思想就是把每个浮点数全部变成int型,然后二分,不然会有很大的精度问题,其次就是读入的时候不能用double读入,可能是因为把double转换成int时有精度的丢失吧,要用字符串读入,然后再转换成int型。
#include
usingnamespacestd;
#defineMAX10005
intn,k;
inta[MAX];
boolcan(intt){
intans=0;
inti;
for(i=1;i<=n;i++){
ans=ans+a[i]/t;
if(ans>=k)returntrue;
}
returnans>=k;
}
voidsolve(){
if(!
can
(1)){
printf("0.00\n");
return;
}
intbottom=1,top=0;
inti;
for(i=1;i<=n;i++){
if(top}
while(bottomif(bottom==top-1){
if(!
can(top))top=bottom;
break;
}
intmid=(bottom+top)>>1;
if(can(mid))bottom=mid;
elsetop=mid-1;
}
doubleans;
if(can(top))ans=top*0.01;//求出的数乘以0.01即为答案
elseans=bottom*0.01;
printf("%.2lf\n",ans);
}
intmain(){
charstr[100];
cin>>n>>k;
inti;
for(i=1;i<=n;i++){
scanf("%s",str);//****精度的问题,要用字符串输入******
intj;
a[i]=0;
for(j=0;str[j]&&str[j]!
='';j++){
if(str[j]!
='.')a[i]=a[i]*10+str[j]-'0';//把读入的数乘以100转换成int型
}
}
solve();
return0;
}