首页 > 代码库 > 【数论Day4】 数学 题解
【数论Day4】 数学 题解
题目:http://www.cnblogs.com/ljc20020730/p/7041033.html
1.离散函数(function.pas/c/cpp)
观察右图,图像必须符合任意两点都在直线的下方。故三条直线中只有相邻两顶点之间的连线的斜率最大。故得出一个规律:最大斜率的直线一定由x坐标相邻的两点确定,即Xi-Xi-1最大的点对。
O(n)枚举,通过本题。
var n,i,ans1,ans2,maxk:longint; a:array[1..200000]of longint; begin assign(input,‘function.in‘); assign(output,‘function.out‘); reset(input); rewrite(output); readln(n); for i:=1 to n do readln(a[i]); ans1:=0; ans2:=0; maxk:=-maxlongint; for i:=2 to n do if a[i]-a[i-1]>maxk then begin maxk:=a[i]-a[i-1]; ans1:=i-1; ans2:=i; end; writeln(ans1,‘ ‘,ans2); close(input); close(output); end.
2.能量采集(energy)
由于n和m都不超过1000,考虑O(n2)枚举每个植物。
通过观察,对于植物(a,b),它与(0,0)连线上植物的被挡住的数量,三条虚线处:
(2,3) 有1个
(4,4) 有3个
(4,2) 有1个
好似与a,b数值的最大公约数数有关。
则每一个坐标点被挡住的个数等于gcd(a,b)-1。
var n,m,i,j,sum,k:longint; function gcd(a,b:longint):longint; begin if a mod b=0 then gcd:=b else exit(gcd(b,a mod b)); end; begin assign(input,‘energy.in‘); assign(output,‘energy.out‘); reset(input); rewrite(output); readln(n,m); for i:=1 to n do for j:=1 to m do begin k:=gcd(i,j)-1; inc(sum,2*k+1); end; writeln(sum); close(input); close(output); end.
3.大逃亡(escape.c/cpp/pas)
注意:由于数据范围很大存实型和整型时要注意用int64和extended.
var v2,d2,v1,d1:int64; t:extended; function f1(t:extended):extended; begin exit((d1+v1*t)*(d1+v1*t)+(d2-v2*t)*(d2-v2*t)); end; function f2:double; begin exit(-(v1*d1-v2*d2)/(v1*v1+v2*v2)); end; begin assign(input,‘escape.in‘); assign(output,‘escape.out‘); reset(input); rewrite(output); readln(v2,d2,v1,d1); if f2<=0 then t:=0 else t:=f2; writeln(sqrt(f1(t)):0:6); close(input); close(output); end.
【数论Day4】 数学 题解
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。