玖的数学&算法录
0%

2022牛客多校第一场

发表于 更新于
本文字数： 2.3k 阅读时长 ≈ 2 分钟

难度：

check-in：G

easy：A D

Medium - easy : C I

Medium : J

Medium - hard : H

Hard : B E F

very - hard : K

统计结果：

A：1334 / 3358 (一血：12)

B：23 / 239 (一血：45)

C：17 / 85 (一血：70)

D：960 / 6414 (一血：30)

E：28 / 222 (一血：45)

F：18 / 135 (一血：46)

G：1482 / 4184 (一血：3)

H：39 / 291 (一血：13)

I：310 / 590 (一血：18)

J：31 / 783 (一血：18)

K：0 / 36 (一血：无)

A. Villages: Landlines

题意：

一个一维数组上有一个发电站与n - 1个建筑物

在数轴上放置一些电力塔使得所有建筑物通过电力塔与发电站连通

能量站位于x_s,能与距离r_s内的电力塔直接连通

第$$i$$个建筑物位于x_i，能与距离r_i内的电力塔直接连通

可以消耗|x_a - x_b|长度的电线连通x_a与x_b的电力塔

问最小消耗电线长度使得所有建筑物都通上电。

范围：

$$1\leq n \leq 2 \times 10^5 , -10^9 \leq x_s, x_i \leq 10^9, 1 \leq r_s, r_i \leq 10^9$$

做法：

模拟,区间合并

区间合并起来，如果说中间有断层的话，则使用电线连接，即为答案。

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
#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define pb push_back
const int MAXN = 2e5 + 10;
using namespace std;

struct node{
	int l,r;
}a[MAXN];


int cmp(node a,node b){
	if(a.l == b.l) return a.r < b.r;
	return a.l < b.l;
}
int main(){
    int n;
	cin >> n;
	for(int i = 0; i < n ;i ++){
		int o,r;
		cin >> o >> r;
		a[i].l = o - r;
		a[i].r = o + r;
	}
	sort(a,a+n,cmp);

	int ans = 0;
	for(int i = 0; i < n - 1 ;i ++){
		if(a[i].r >= a[i+1].l){
			if(a[i].r > a[i + 1].r){
				a[i+1].r = a[i].r;
			}
		} else{
			ans += a[i+1].l - a[i].r;
		}
	}
	cout << ans << endl;
	return 0;

}

D. Mocha and Railgun

题意：

  • 给定一个圆和严格位于圆内的一点 P
  • 从点 P 向任意角度发射一个长度为 2d的电磁炮
  • 电磁炮底边的中点为点 P 且两端位于圆内
  • 问单次发射能摧毁的最大圆弧长度

范围：

$$1\leq T \leq 1000, -10^9 \leq x,y \leq 10^9, 1\leq r,d \leq 10^9$$

计算几何

图与思维来自：为新生振翅而上

img

 根据中学数学我们知道，想要圆弧更长，那么它对应的弦就得更长。那么，对于线段AB，我们需要令其对应的弦c最长。做线段b，令其垂直于电磁炮的边界。这样我们就得到了一个三角形：其中易得b的长度为2d，是固定的，那么想让c最长就等价于找到最长的a了。不难得知当Q的位置和d固定时，当线段AB或AB的延长线经过O时a最长。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define pb push_back
const int MAXN = 1e5 + 10;
const double pi = acos(-1);
int a[MAXN];
using namespace std;

int main(){
    int T;
    cin >> T;
    while(T--){
        double r,x,y,d;
        cin >> r >> x >> y >> d;
        double dis = sqrt(x * x + y * y);
        double a1 = acos((d-dis) / r);
        double a2 = acos((d+dis) / r);
        double a3 = pi - a1 - a2;
        double ans = a3 * r;
        cout << setprecision(12)<< ans << endl;
    }
}

G.Lexicographical Maximum

题意：

给定一个 n , 将1，2，…，n视为不含前导零的字符串，求这些字符串种字典序最大的字符串。

范围:

1<=n<=10^1000000

模拟

显然，除去最后一位，其他位必然是9，如果n除去最后一位，其余都是9的话，那么答案是n，若不然答案有n-1个9

1
2
3
4
5
6
7
8
9
10
void solve(){
    string s;
    cin >> s;
    string ans(s.length()-1,'9');
    if(s > ans){
        cout << s << endl;
    } else{
        cout << ans << endl;
    }
}