- A 签到
- B
- 题意:在x轴上找一个点,使得它到给定的点之间的最大距离最小,输出最大距离的最小值
- 思路:答案点的左/右侧,得到的最大距离都比答案大,所以答案所在的点是一个极小值点。可以对在x轴上找的这个点三分,或者对最大距离二分,找到第一个满足答案的最大距离(该距离最小)
- ac代码:
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5+10;
struct node{
int x, y;
}a[maxn];
int n;
double maxdis(double x)
{
double ans = 0;
for(int i = 1; i <= n; i++)
ans = max(ans, sqrt(a[i].y*a[i].y+(a[i].x-x)*(a[i].x-x)));
return ans;
}
int main()
{
scanf("%d", &n);
for(int i = 1; i <= n; i++) scanf("%d %d", &a[i].x, &a[i].y);
double l = -10000, r = 10000;
while((r-l)>1e-7)
{
double midl = (r+l)/2;
double midr = (midl+r)/2;
if(maxdis(midl)>=maxdis(midr)) l = midl;
else r = midr;
}
printf("%.6f\n", maxdis(r));
return 0;
}
#include<bits/stdc++.h>
#define lowbit(x) ((x)&(-(x)))
using namespace std;
typedef long long LL;
const int INF=0x3f3f3f3f;
const int maxn=1e5+10;
int n;
double x[maxn],y[maxn];
bool check(double r)
{
double low=-1e10,up=1e10;
for(int i=1;i<=n;i++)
{
if(abs(y[i])>r)
return false;
double s=x[i]-sqrt(r*r-y[i]*y[i]),t=x[i]+sqrt(r*r-y[i]*y[i]);
if(t<low||s>up)
return false;
if(t<up)
up=t;
if(s>low)
low=s;
}
return true;
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%lf %lf",&x[i],&y[i]);
double L=0,R=10000*sqrt(2)+10;
while((R-L)>1e-7)
{
double MID=(R+L)/2;
if(check(MID))
R=MID;
else
L=MID;
}
printf("%.7f\n",L);
return 0;
}
- C 模拟 逃💨
- D 贪心
- 题意:a和b都是x轴上的点,a每次可以选择花费1s跳到 3a ,或者选择以1单位/s的速度前进,问a到达b最少需要多久。
- 思路:先假设接下来全部按照1单位/s的速度走,na= 3ca ,如果abs(na-cb)+1.0 < abs(ca-cb),那么下一步选择直接跳到na,否则剩下的距离只能全部按照1单位/s的速度走。
- E 签到
- F dp
- 思路:题意:AC会说一句话,RJ会连续说x句话,已知共说了n句话,问有多少种说话的排列(且RJ下一次必须是AC)
考虑说的最后一段话是AC还是RJ的时候说的
dp[i][1]表示共说了i句话最后一段话说了一句 dp[i][0]表示最后一段话说了x句
dp[i][1]=dp[i−1][0]+dp[i−1][1]
dp[i][0]=dp[i−x][1]
ans[n]=dp[i][0]+dp[i][1]
- G
- 题意:n*m的矩阵,&表示是障碍物,A是被被追赶者,L是追赶者,#表示可走。给出p个僵尸的位置及往返的方向和长度k(所有僵尸的k都相同,朝给定方向走(k-1)步再折返),问L是否能到A,能输出最小步数。
- 思路:所有僵尸循环的周期是2k-2,即第0s和第2k-2s都会在初始位置,那么只需要在bfs的时候记录上时间并记忆化即可(对2k-2取模),判断该时刻该位置是否有僵尸。
- ac代码:
#include <bits/stdc++.h>
using namespace std;
const int maxn = 510;
int ans[maxn][maxn][20];
bool js[maxn][maxn][20];
char s[maxn][maxn], dir[maxn];
int n, m, p, k, modt;
int fx, fy;
int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, -1, 1};
struct node{
int x, y, t;
};
queue<node> q;
bool check(int x, int y, int t)
{
if(x<1 || x>n || y<1 || y>m || s[x][y]=='&' || js[x][y][t] || ans[x][y][t]!=-1) return false;
return true;
}
void bfs()
{
int res = -1;
while(!q.empty())
{
node tmp = q.front(); q.pop();
int xx = tmp.x, yy = tmp.y, tt = tmp.t;
if(xx==fx && yy==fy) {res = ans[xx][yy][tt]; break;}
for(int i = 0; i < 4; i++)
{
int nx = xx+dx[i], ny = yy+dy[i], nt = (tt+1)%modt;
if(check(nx, ny, nt))
{
ans[nx][ny][nt] = ans[xx][yy][tt]+1;
q.push(node{nx, ny, nt});
}
}
}
if(res==-1) printf("Oh no\n");
else printf("%d\n", res);
}
int main()
{
memset(ans, -1, sizeof(ans));
scanf("%d %d %d %d", &n, &m, &p, &k);
modt = 2*k-2;
for(int i = 1; i <= n; i++)
{
scanf("%s", s[i]+1);
for(int j = 1; j <= m; j++)
{
if(s[i][j]=='A') fx = i, fy = j;
if(s[i][j]=='L') q.push(node{i, j, 0}), ans[i][j][0] = 0;
}
}
int x, y;
for(int i = 1; i <= p; i++)
{
scanf("%d %d %s", &x, &y, dir);
int id = 0;
if(dir[0]=='U') id = 0; if(dir[0]=='D') id = 1;
if(dir[0]=='L') id = 2; if(dir[0]=='R') id = 3;
js[x][y][0] = true;
for(int j = 1; j < k; j++)
{
x = x+dx[id]; y = y+dy[id];
js[x][y][j] = js[x][y][modt-j] = true;
}
}
bfs();
return 0;
}