P5515 [MtOI2019]灵梦的计算器 题解

这道题emmm一道牛顿迭代 ~~毒瘤卡常~~ 题（ 这里介绍一下比赛心路历程 **温馨提示 为了更好的观感 代码中的Mker已隐藏 请自行添加** 首先瞄一眼题 觉得可以二分答案找左右界 预期得分：70 实际得分：65 代码如下： ```c++ #include<bits/stdc++.h> using namespace std; const double eps = 1e-7; double now=0,ans=0; bool equal(double a,double b) { return a+eps>=b&&a-eps<=b; } double solve(double n,double a,double b) { return pow(n,a)+pow(n,b); } double judge(double n,double a,double b) { double mid,lft=4,rht=n; mid=(lft+rht)/2; while(!equal(lft,rht)) { if(floor(solve(n,a,b))==floor(solve(mid,a,b))) rht=mid; else lft=mid; mid=(lft+rht)/2; } return lft; } double judge1(double n,double a,double b) { double mid,lft=n,rht=5; mid=(lft+rht)/2; while(!equal(lft,rht)) { if(floor(solve(n,a,b))==floor(solve(mid,a,b))) lft=mid; else rht=mid; mid=(lft+rht)/2; } return rht; } signed main() { int T; scanf("%d",&T); double n,a,b; Mker::init(); while(T--) { Mker::read(n,a,b); ans+=judge1(n,a,b)-judge(n,a,b); // printf("%lf\n",ans); } printf("%lf",ans); return 0; } ``` 然后被机房大佬牛顿迭代DD 然后写了个牛顿迭代 结果和暴力一个分 65分 代码如下 ```cpp #include<bits/stdc++.h> using namespace std; const double eps = 1e-4; double ans=0; bool equal(double a,double b) { return a+eps>=b&&a-eps<=b; } double f(double n,double a,double b) { return pow(n,a)+pow(n,b); } double solve(double n,double a,double b) { double ret=n-(f(n,a,b)/(a*pow(n,a-1)+b*pow(n,b-1))); while(!equal(floor(f(n,a,b)),floor(f(ret,a,b)))) { ret=ret-((f(ret,a,b)-f(n,a,b))/(a*pow(ret,a-1)+b*pow(ret,b-1))); } return ret; } double solve2(double n,double a,double b) { double ret=n-(f(n,a,b)/(a*pow(n,a-1)+b*pow(n,b-1))); while(!equal(floor(f(n,a,b))+1,floor(f(ret,a,b)))) { ret=ret-((f(ret,a,b)-f(n,a,b)-1)/(a*pow(ret,a-1)+b*pow(ret,b-1))); } return ret; } signed main() { int T; scanf("%d",&T); double n,a,b; Mker::init(); while(T--) { Mker::read(n,a,b); ans+=fabs(solve2(n,a,b)-solve(n,a,b)); // printf("%lf\n",ans); } printf("%lf",ans); return 0; } ``` （（接着机房大佬告诉我这玩意跑一遍就能满足精度需求 然后就跑了一遍 只有80分，代码如下： ```cpp #include<bits/stdc++.h> using namespace std; const double eps = 1e-6; double ans=0; double f(double n,double a,double b) { return pow(n,a)+pow(n,b); } double solve(double n,double a,double b) { double ret=(f(n,a,b)-floor(f(n,a,b))/(a*pow(n,a-1)+b*pow(n,b-1))); return ret; } double solve2(double n,double a,double b) { double ret=(f(n,a,b)-ceil(f(n,a,b))/(a*pow(n,a-1)+b*pow(n,b-1))); return ret; } signed main() { int T; scanf("%d",&T); double n,a,b; Mker::init(); while(T--) { Mker::read(n,a,b); ans+=solve(n,a,b)-solve2(n,a,b); // printf("%lf\n",ans); } printf("%lf",ans); return 0; } ``` 然后进行疯狂卡常 失败 然后看大佬莫得用函数 就把函数搬出来 ```cpp // luogu-judger-enable-o2 #include<bits/stdc++.h> using namespace std; double ans=0; signed main() { int T; scanf("%d",&T); double n,a,b; Mker::init(); while(T--) { Mker::read(n,a,b); double powa=pow(n,a-1),powb=pow(n,b-1); ans+=(powa*a+powb*b-floor(powa*a+powb*b))/(a*powa+b*powb)-(powa*a+powb*b-ceil(powa*a+powb*b))/(a*powa+b*powb); } printf("%lf",ans); return 0; } ``` 然后就A了emmm （（为什么比赛莫得把函数整出来啊QAQ