前言

​    今天又是颓废的一天,被大佬拉去跟他一起做牛客网的题,QAQ...那我会点啥嘛,就只能替大佬写两道水题了···


A. 牛牛战队的比赛地

题意

​    由于牛牛战队经常要外出比赛,因此在全国各地建立了很多训练基地,每一个基地都有一个坐标 $(x,y)$ 。
​    这周末,牛牛队又要出去比赛了,各个比赛的赛点都在 $x$ 轴上。牛牛战队为了方便比赛,想找一个到达训练基地最大距离最小的地方作为比赛地。请你求出选择的比赛地距离各训练基地最大距离的最小值。

思路

​    这个题首先一看到这种什么最大的最小,第一直觉就是二分。首先我们想一下应该二分什么,肯定先想的是枚举 $x$ 轴上的点,但是这样就会有个问题,二分要用的话必须是单调的,那么我们不能够确定越往右或者越往左,他们的这个值是单调的。因此我们可以用三分,一直向单峰逼近,最终寻找到那个极值点。(说实话这是我第一次接触到三分法,我太菜了。)

代码实现

#include<cstdio>
#include<cstring>
#include<iostream>
#include<cmath>
#include<algorithm>

using namespace std;

const int maxn=100005;
struct node
{
    int x,y;
}p[maxn]; //point
int n;
const double eps=1e-6;
double lmid,rmid,lans,rans;
double check(double x)
{
    double ans=0;
    for(int i=1;i<=n;i++)
    {
        double dis=(p[i].x-x)*(p[i].x-x)+p[i].y*p[i].y;
        ans=max(ans,dis);
    }
    return ans;
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d%d",&p[i].x,&p[i].y);
    }
    double l=-10000,r=10000;
    double ans=9999999999;
    while(r-l>=eps)
    {
        lmid=(r+l)/2;
        rmid=(r+lmid)/2;
        lans=check(lmid);
        rans=check(rmid);
        if(lans<rans)
        {
            ans=min(ans,lans);
            r=rmid;
        }
        else 
        {
            ans=min(ans,rans);
            l=lmid;
        }
    }
    printf("%lf",sqrt(ans));
    return 0;
} 


B. 牛牛与牛妹的约会

题意

​    你想从 $(a,0)$ 点到 $(b,0)$ 点,你可以除了可以以 $1m/s$ 的速度奔跑,还可以用1秒的时间来引导闪现,这将使你从 $(x,0)$ 点闪现到 $(\sqrt[3]{x},0)$ 点,问最少需要多长时间到达 $(b,0)$ 点。$(Ps:a,b \in[-10^6,10^6])$

思路

​    一道贪心的题目,当闪现所能贡献的距离大于 $1m$ ,那么我就选择用闪现,不然就直接奔跑。那么我们可以用距离的变化来体现闪现贡献的距离,一直用闪现到不能用之后,就直接加上最后剩下的距离即可。注意pow这个函数有点坑?如果底数是负数并且指数不是整数的话好像会返回很奇怪的值···(跟大佬调了好长时间都卡在这了)

代码实现

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>

using namespace std;

int t,x,y;
double ans,a,b;
double dis,cdis;
int main(void)
{
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&x,&y);
        a =(double)x;
        b=(double)y;
        dis = abs(a-b);
        if(a<0)
        {
            cdis=abs(-pow(-a,1.0/3.0)-b);
        }
        else cdis = abs(pow(a,1.0/3.0)-b);
        ans = 0;
        while(dis-cdis>1.0)
        {
            if(a<0)
            {
                a=-pow(-a,1.0/3.0);
            }
            else a=pow(a,1.0/3.0);
            ans+=1;
            dis = cdis;
            if(a<0)
            {
                cdis = abs(-pow(-a,1.0/3.0)-b);
            }
            else cdis = abs(pow(a,1.0/3.0)-b);
        }
        ans+=dis;
        printf("%.9lf\n",ans);
    }
    return 0;
}


C. 碎碎念

题意

​    大佬豪和弱鸡战合作做题,如果大佬豪AC掉题目,那么弱鸡战会说 “宁好强啊!”,如果大佬豪WA掉了题目,那么弱鸡战会嘲讽大佬豪 $k$ 句 “宁好弱啊!” 。我们规定大佬豪提交只有AC和WA两种状态。因为大佬豪非常的强,如果一道题他WA掉了一发,那么他的下一发一定会AC。如果已知最终弱鸡战嘲讽了 $x$ 句,那么很明显可以对应很多的提交序列。现在想问你如果弱鸡战嘲讽数在 $[l,r]$ 这个区间,一共会有多少种提交序列。答案对 $1e9+7$ 取模。

思路

​    首先原始题面不是这样,我把名字改了一下,QAQ...
​    QAQ刷了这么多天的dp好像终于有点作用了,我终于看出来这是一道dp题了,还找对了他们的状态,不过转移方程却写错了。那么首先我们可以用 $f[i]$ 来表示,如果说了 $i$ 句话,那么一共有多少种可能的序列,但是这样的话我们发现没法确保上文上的如果WA掉了,下一发一定是AC。
​    所以我们可以考虑加一维状态来表示是通过哪种提交状态到达第 $i$ 句话的,也就是写成 $dp[0/1][i]$ 这个状态,$dp[0][i]$ 代表是从 $i-1$ 句话直接AC转移过来的,$dp[1][i]$ 是从 $i-k$ 句话通过WA转移过来的。所以这样的话转移方程就可以写出来了。

  • $dp[0][i] = dp[0][i-1]+dp[1][i-1]$ (可以从WA和AC转移过来)
  • $dp[1][i]=dp[0][i-k]$ (只能从第 $i-k$ 状态是AC的时候转移,不能连续两次WA)

​    因为最终是一个区间查询,那么我们可以用前缀和来优化。

代码实现

#include<cstdio>
#include<cmath>
#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;

const int maxn=100005;
int k,q;
int l,r;
int mod =1e9+7;
int dp[2][maxn];
int sum[maxn];
int ans[maxn];
int main()
{
    scanf("%d%d",&k,&q);
    dp[0][0]=1;
    for(int i=1;i<=100000;i++)
    {
        dp[0][i]=dp[0][i-1]+dp[1][i-1];
        dp[0][i]%=mod;
        if(i>=k)
        {
            dp[1][i]=dp[0][i-k];
            dp[1][i]%=mod;
        }
        ans[i]=dp[0][i]+dp[1][i];
        ans[i]%=mod; 
        sum[i]=sum[i-1]+ans[i];
        sum[i]%=mod;
    }
    for(int i=1;i<=q;i++)
    {
        scanf("%d%d",&l,&r);
        printf("%d\n",(sum[r]-sum[l-1]+mod)%mod);
    }
    return 0;
}


D. 牛牛战队的秀场

题意

​    在半径为 $r$ 的圆内有一个正接 $n$ 边形,随便选取一个顶点编号为 $1$ ,顺时针编号为 $2\sim n$ ,规定只能沿多边形边走,问从顶点 $i$ 到顶点 $j$ 最短路径为多少。

思路

​    很显然只有两条路可以走,我们只需要算出正多边形的每条边的边长,然后比较两条路径的大小,哪一个短就走哪一个就行,不过如果用了cos() 函数记得特判一下 $n=4$ 的情况,不然会发生错误。

代码实现

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<iostream>

using namespace std;

int n,ri;
double r;
int i,j;
double pi = 3.1415926535898;
int main()
{
    scanf("%d%d",&n,&ri);
    scanf("%d%d",&i,&j);
    double k=(double)2*pi/(double)n;
    double s;
    r=(double)ri;
    if(n==4)
    {
        s=sqrt(2*r*r);
    }
    else s=sqrt((double)2*r*r-2.0*r*r*cos(k));
    int p=abs(i-j);
    if(p>n/2)
    {
        printf("%lf",s*(n-p));
    }
    else printf("%lf",s*p);
    return 0;
} 
最后修改:2020 年 08 月 18 日 12 : 49 AM
如果觉得我的文章对你有用,请随意赞赏