(2条未读私信) 牛客2025秋季算法编程训练联赛5-基础组_ACM/NOI/CSP/CCPC/ICPC算法编程高难度练习赛_牛客竞赛OJ

C 牛牛战队的秀场

1.首先需要知道pai的精确表示方法：acos(−1.0)acos(-1.0)

2.解三角形c^2 = a^2+b^2-2ab cosC 用二倍角公式化简完成后得：c = 2r sin(pai / n) 求得边长

3.左右两边都可以走相当于一个环，没必要用循环移位，可以用O(1)O(1)写出来。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <bits/stdc++.h>

using namespace std;

const double pai = 3.1415926;

int r, n, i, j;

int main()
{
	cin >> n >> r >> i >> j;
	
	double len = 2 * r * sin(acos(-1.0) / n);

	int diff = abs(i - j);
	int min_steps = min(diff, n - diff);
	
	// 输出最短距离
	cout << fixed << setprecision(10) << min_steps * len << endl;
	return 0;
}

D Enjoy the game

本题一上手直接判断奇偶数然后就WA了

如若牌数为奇数则Bob赢如若为偶数

1偶数中含有（除一以外）奇数因子，则Bob赢

2偶数中（除一以外）不含奇数因子，则Alice赢（即牌数为2的n次幂）

这里写了一种O(logn)O(logn)来判断一个数是否有奇数因子的方法，替代用sqrt(n)sqrt(n)的因数判断来做，会超时

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include <bits/stdc++.h>

using namespace std;

int check(long long n)
{
	while (!(n & 1))//偶数时候继续做
        n >>= 1;
	
	if (n == 1)//没有奇数因子
        return 1;
    else
        return 0;
}

int main()
{
	long long n;
	
	cin >> n;
	
	if (n % 2 == 1)
		cout << "Bob" << endl;
	else
	{
		if (check(n))
			cout << "Alice" << endl;
		else
			cout << "Bob" << endl;
	}
	
	return 0;
}

F 牛牛战队的比赛地

很棒的一道二分答案的题目，帮助我复习了二分答案的做题步骤

看到题目中出现最大距离的最小值，我就想到了需要用二分答案求解

回顾一下二分答案做题步骤：

1找到使某命题p(x)成立（或不成立）的最大（或最小）的x

2把p(x)看做一个值为真或假的函数，他一定在某个分界线的一侧全部为真，另一侧全部为假

2找到一个复杂度优秀的算法来验证p(x)的真假

1 这里x是需要二分的距离，p(x)代表对于给定的d，判断是否存在一点在x轴上的p使得所有训练基地到p点的距离都不超过d

2.p(x)符合二分答案条件

3.验证p(x)的真假

关键步骤分析

  1. 检查纵坐标条件
1
2
3
4
if (abs(y[i]) > mid) { //由于不确定在x轴上方还是下方，所以要加绝对值(不加只能过93%)
    valid = false;
    break;
}

· 如果某个点的纵坐标绝对值大于D，那么该点到x轴上任何点的最小距离就是|y_i|（当p = x_i时）
· 如果|y_i| > D，那么无论p取什么值，该点到P的距离都大于D
· 因此这种情况直接判定为不可行

  1. 计算x轴上的可行区间
1
2
3
double dx = sqrt(mid * mid - (double)y[i] * y[i]);
double l = x[i] - dx;
double r = x[i] + dx;

· dx表示在x轴方向上可以偏离的距离
· 从几何上看：以(x_i, y_i)为圆心，D为半径作圆，该圆与x轴的交点就是(x_i - dx, 0)和(x_i + dx, 0)
· 区间[l, r]表示：如果点P在这个区间内，那么该训练基地到P的距离不超过D

  1. 维护区间交集
1
2
3
4
5
6
if (l > low) low = l;
if (r < high) high = r;
if (low > high) {
    valid = false;
    break;
}

· 我们维护一个交集区间[low, high]
· 每个训练基地都会给出一个区间，我们需要找到所有区间的公共部分
· 如果交区间为空（即low > high），说明不存在这样的点P

几何直观理解

想象每个训练基地在x轴上投射一个"阴影"：

· 基地(x_i, y_i)在x轴上投射的阴影是从x_i - dx到x_i + dx
· 这个阴影表示：如果比赛地点在这个区间内，该基地到比赛地点的距离≤D
· 我们需要找到所有阴影的重叠部分

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include <bits/stdc++.h>

using namespace std;

const double eps = 1e-9;

const int N = 1e5 + 10;

int n;

struct point
{
	int x, y;
} a[N];

bool check(double d)
{
	double p = -100100, q = 100100;
	for (int i = 1; i <= n; i++)
	{
		if (fabs(a[i].y) > d) //点不一定在x轴上方
			return 0;
		double len = sqrt(d*d-a[i].y*a[i].y);
		double l = a[i].x-len, r = a[i].x+len;
		if (l > p)
			p = l;
		if (r < q)
			q = r;
		if (p > q)
			return 0;
	}
	return 1;
}

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> n;
	for (int i = 1; i <= n; i++)
		cin >> a[i].x >> a[i].y;
	
	double l = 0, r = 10000000;
	while (r - l > eps)
	{
		double mid = (l + r) / 2;
		if (check(mid))
			r = mid;
		else
			l = mid;
	}	
	
	cout << l << endl;
	return 0;
}