ACM必做50题的解题数学Word下载.docx
- 文档编号:1004215
- 上传时间:2023-04-30
- 格式:DOCX
- 页数:18
- 大小:20.28KB
ACM必做50题的解题数学Word下载.docx
《ACM必做50题的解题数学Word下载.docx》由会员分享,可在线阅读,更多相关《ACM必做50题的解题数学Word下载.docx(18页珍藏版)》请在冰点文库上搜索。
算法:
这是数论中的进位制问题,我们可以仿照原来的求一个数二进制表示方法;
但首先,我们应该考虑几个问题;
①k位这种类2进制的表示范围;
显然,当给出的'
p'
'
序列中,我们将所有p的位置都置为1其余位是0,此时最大;
当我们将所有n的位置置为1,其余为0,此时最小;
不过当我们求最大限max和最小限min时会有一个溢出问题;
比如64位全是p的序列,那么max会溢出,值为-1;
同理min在全是n时也会溢出,为1;
显然是max>
=0,min<
=1,溢出时产生异常,依次可以判断;
②是否是最大限和最小限之间的数都能表示呢?
都可以,而且能够表示的数是2^k个,这个原始2进制是一样的;
因为每个位上要么是0,要么是1,而且每个位上的权重唯一的,不能通过其他位的01组合获得;
最后,我们就可以仿照原始二进制来算在类2进制下的表示;
不断求N的二进制最后一位和右移;
如果取余是1,则该位上一定是1,如果该位对于字母为‘n’,则高位应该再加1;
这里对2取余可能会出错,因为对于负数,补码的表示,最后一位一定是和原码一样的每次的右移后(有时需先加1)补码表示正好符合要求(可找实例验证);
__int64N,M;
chars[100],res[100]={'
\0'
};
intT;
scanf("
%d"
T);
inti,j;
__int64_max,_min;
charch;
while(T--)
scanf("
%I64d"
N);
%s"
s);
_max=0;
_min=0;
for(i=0;
i<
N;
i++)//找出能表示的范围;
if(s[i]=='
)_max=2*_max+1,_min*=2;
else_min=2*_min-1,_max*=2;
M);
if((M<
_min&
_min<
=0)||(M>
_max&
_max>
=0))puts("
Impossible"
);
//注意防止64位数的溢出;
else
memset(res,'
sizeof(res));
for(i=N-1;
=0;
i--)
intflag=0;
if(M&
1)//这里不能是平常的%2;
res[i]='
1'
;
)flag=1;
elseres[i]='
0'
M>
>
=1;
if(flag)M++;
//如果是n就需其高位加1;
%s\n"
res);
system("
pause"
}
POJ2506Tiling递推+高精
给看似复杂的题找到了合适的规律就会变得简单。
这个题就是这样。
对于n列来说,可以在n-1列的基础上加上一块,或者是在n-2列的基础上加上2块
而2块独立的,不依赖于1块的情况有两种,所以得到递推公式f(n)=f(n-1)+2f(n-2)
看样例,要用到高精。
//f(n)=f(n-1)+2f(n-2)
intf[251][300];
voidHPprint(int*a)
for(inti=a[0];
i--)cout<
<
a[i];
cout<
endl;
voidHPplus(int*a,int*b,int*c)
inti,j;
j=0;
for(i=1;
=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;
=a[0];
c[i]+=a[i]*b;
k=0;
for(j=1;
j<
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&
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;
=250;
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<
stdio.h>
math.h>
structfrac{
__int64up,down;
__inline__int64gcd(__int64a,__int64b)
__int64r;
if(a<
b){
r=a;
a=b;
b=r;
while
(1){
r=a%b;
if(!
r)
returnb;
__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<
f.up=-f.up;
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){
%I64d/%I64d\n"
f.up,f.down);
min_dis=dis;
\n"
poj1019NumberSequence(找规律)
找规律的题目:
先计算出从1到n这个小区间有多长,保存到digit[]数组中,然后计算从112123到n一共有多少位数字,然后根据输入数据查找,其中我在找那一位时比较暴力,把从1开始一直存放,直到存放的比那一位还多,然后取出那一位。
sstream>
string>
cmath>
usingnamespacestd;
constintMaxSize=100000+10;
__int64digit[MaxSize],len[MaxSize];
stringstreamss;
voidinit()
inti;
digit[1]=len[1]=1;
for(i=2;
i<
MaxSize;
++i){
digit[i]=digit[i-1]+(int)log10((double)i)+1;
len[i]=len[i-1]+digit[i];
/*for(i=1;
10;
cout<
i<
"
位数"
<
digit[i]<
长度"
len[i]<
endl;
}*/
chargetDigit(intnum)
for(i=1;
len[i]<
num;
++i)
;
intpos=num-len[i-1];
//清空ss
ss.str("
"
=pos;
ss<
i;
//cout<
ss.str()<
return(ss.str())[pos-1];
inti,sets,num;
init();
cin>
sets;
while(sets--){
num;
getDigit(num)<
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<
=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);
至此,问题得到了解决。
voidfun(intn,intk){
inti,sum=0;
if(1==n){putchar('
X'
return;
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);
)'
}
if(n-i-1){
fun(n-i-1,(k-1)%L[n-i-1]+1);
intmain(){
intn,i,j,sum;
n)&
n){
sum=0;
for(i=1;
n>
i++)sum+=L[i];
fun(i,n-sum+L[i]);
\n'
POJ1905ExpandingRods
algorithm>
intmain(intargc,char*argv[])
doubleN,C,L;
%lf%lf%lf"
L,&
N,&
C)&
N>
=0&
C>
L>
=0)
if(N==0||L==0||C==0)
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;
maxv=midv;
%.3lf\n"
L2/midv*(1-cos(midv/2)));
POJ1064Cablemaster
AC率较低的题,也是很明显的二分题,但是由于精度问题WA了很多次,最终看discuss过的,这题一个很重要的精度思想就是把每个浮点数全部变成int型,然后二分,不然会有很大的精度问题,其次就是读入的时候不能用double读入,可能是因为把double转换成int时有精度的丢失吧,要用字符串读入,然后再转换成int型。
#defineMAX10005
intn,k;
inta[MAX];
boolcan(intt){
intans=0;
inti;
=n;
i++){
ans=ans+a[i]/t;
if(ans>
=k)returntrue;
returnans>
=k;
voidsolve(){
if(!
can
(1)){
0.00\n"
return;
intbottom=1,top=0;
if(top<
a[i])top=a[i];
while(bottom<
top){
if(bottom==top-1){
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;
%.2lf\n"
ans);
intmain(){
charstr[100];
cin>
k;
str);
//****精度的问题,要用字符串输入******
intj;
a[i]=0;
for(j=0;
str[j]&
str[j]!
='
'
j++){
if(str[j]!
.'
)a[i]=a[i]*10+str[j]-'
//把读入的数乘以100转换成int型
solve();
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- ACM 50 解题 数学
![提示](https://static.bingdoc.com/images/bang_tan.gif)