前言
今天又是颓废的一天，被大佬拉去跟他一起做牛客网的题，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;
}