Doveqise

Doveqise

万事皆虚,诸行皆允

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

posted on 2019-08-24 16:42:22 | under 题解 |

这道题emmm一道牛顿迭代 毒瘤卡常 题( 这里介绍一下比赛心路历程
温馨提示 为了更好的观感 代码中的Mker已隐藏 请自行添加
首先瞄一眼题 觉得可以二分答案找左右界 预期得分:70 实际得分:65
代码如下:

#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分 代码如下

#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分,代码如下:

#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;
}

然后进行疯狂卡常 失败
然后看大佬莫得用函数 就把函数搬出来

// 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