<mark>B.牛牛战队的比赛地</mark>：【三分】
要求最大距离的最小值 → 三分。
三分用于单峰函数求最值，又因为是对浮点数进行三分，可以通过限定三分的次数来达到一定的精度要求。
#include <bits/stdc++.h>
using namespace std;
const int N=1e5+5;
typedef long long ll;
ll x[N],y[N];
int n;
double check(double xx)
{
double res=0;
for(int i=1;i<=n;i++)
{
double t=sqrt((x[i]*1.0-xx)*(x[i]*1.0-xx)*1.0+y[i]*y[i]*1.0);
res=max(res,t);
}
return res;
}
double solve(double l,double r)
{
for(int i=1;i<=100;i++)
{
double midl=(l+r)/2.0;
double midr=(midl+r)/2.0;
double tl=check(midl);
double tr=check(midr);//cout<<"tl="<<tl<<" tr="<<tr<<endl;
if(tl<=tr)//极小值
r=midr;
else
l=midl;
}
return l;
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%lld%lld",&x[i],&y[i]);
printf("%.6f\n",check(solve(-10000.0,10000.0)));
return 0;
}
E.Enjoy the game：【博弈论】
我是通过找规律来做的，如果 n=2m(m≥1)，那么 Alice 胜，否则 Bob 胜。
如果不是2的幂，那么先手只要拿 n 的二进制表示中最低位的1对应的数字的牌数，后手必输。可以手推规律。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
bool check(ll m)
{
while(m%2==0)
m/=2;
if(m==1)
return 1;
return 0;
}
int main()
{
ll n;
scanf("%lld",&n);
if(n&1)
printf("Bob\n");
else
{
if(check(n))
printf("Alice\n");
else
printf("Bob\n");
}
return 0;
}
G.街机争霸：【bfs+时间】
思路：
显然这是一个二维图上的 bfs ,但和普通的 bfs 不同的是，有僵尸会走动，但他所在的位置和时间有关，并且具有周期性，而且所有的僵尸的有的规则相同。对于和时间有关的 bfs ，常在标记数组的第三维加上时间这一维处理。因为人在找到目标之前是不能停留的，如果下一个要走的位置有僵尸，人可以选择往别处走，等待时机，或者永远过不去。那么，人在周期内的同一时间点是不可能到达同一位置的。因为如果上次到达时，这个地方就有僵尸，那么这一次一定也有。如果上一次没有，那么上一次就可以通过。所以用第三维表示时间加取模周期的方法是正确的。
#include <bits/stdc++.h>
using namespace std;
const int N=550;
const int T=20;
char pic[N][N];//存图
bool vis[N][N][T];//标记数组：一，二维表示坐标，第三维表示时间
int dx[4]={0,1,-1,0};//方向：
int dy[4]={1,0,0,-1};
int t,ex,ey,sx,sy,n,m,k;
struct node
{
int x,y,time;
};
queue<node>que;
void init(int x,int y,int z)//把周期内的僵尸的行走路径标记
{
int tx=x,ty=y;
vis[x][y][0]=1;
for(int j=1;j<k;j++)
{
x=x+dx[z];
y=y+dy[z];
vis[x][y][j%t]=1;
}
//x=tx;y=ty;
for(int j=k;j<=t;j++)
{
x=x+dx[3-z];
y=y+dy[3-z];
vis[x][y][j%t]=1;
}
}
bool check(int x,int y,int tt)//检验下一个地方是否合法
{
if(x<1||x>n||y<1||y>m)
return false;
if(pic[x][y]=='&')
return false;
if(vis[x][y][tt%t]==1)
return false;
return true;
}
int bfs()//正常bfs的步骤
{//cout<<"++++"<<endl;
que.push(node{sx,sy,0});
vis[sx][sy][0]=1;
while(!que.empty())
{
node now=que.front();
que.pop();
if(now.x==ex&&now.y==ey)
return now.time;
for(int i=0;i<4;i++)
{
int tx=now.x+dx[i];
int ty=now.y+dy[i];
if(check(tx,ty,now.time+1))
{
vis[tx][ty][(now.time+1)%t]=1;
que.push(node{tx,ty,(now.time+1)});
}
}
}
return -1;
}
int main()
{
int p;
scanf("%d%d%d%d",&n,&m,&p,&k);
t=2*k-2;
for(int i=1;i<=n;i++)
{
scanf("%s",pic[i]+1);
for(int j=1;j<=m;j++)
{
if(pic[i][j]=='L')
sx=i,sy=j;
if(pic[i][j]=='A')
ex=i,ey=j;
}
}
int x,y;
char cmd[10]={0};
for(int i=1;i<=p;i++)
{
scanf("%d%d",&x,&y);
scanf("%s",cmd);
if(strcmp(cmd,"UP")==0)
init(x,y,2);
else if(strcmp(cmd,"DOWN")==0)
init(x,y,1);
else if(strcmp(cmd,"LEFT")==0)
init(x,y,3);
else if(strcmp(cmd,"RIGHT")==0)
init(x,y,0);
}
int ans=bfs();
if(ans==-1)
printf("Oh no\n");
else
printf("%d\n",ans);
return 0;
}
京公网安备 11010502036488号