# Leetcode 第37场双周赛题解

# Problem A - 删除某些元素后的数组均值 (opens new window)

class Solution {
public:
double trimMean(vector<int>& arr) {
sort(arr.begin(), arr.end());
int n = arr.size();
if (n == 0)
return 0.0;
double sum = 0;
for (int i = n / 20; i < n - n / 20; ++i)
sum += arr[i];
return sum / (n - n / 10);
}
};

1
2
3
4
5
6
7
8
9
10
11
12
13

# Problem B - 网络信号最好的坐标 (opens new window)

class Solution {
int calc(vector<vector<int>> &towers, int r, int x, int y) {
double res = 0.0;
for (auto &tower : towers) {
int dx = abs(x - tower[0]);
int dy = abs(y - tower[1]);
double d = sqrt(dx * dx + dy * dy);
if (d > r)
continue;
res += floor((double)tower[2] / (1 + d));
}
return (int)res;
}
public:
vector<int> bestCoordinate(vector<vector<int>>& towers, int radius) {
int hi = 0;
int ax = 0, ay = 0;
for (int x = 0; x <= 50; ++x)
for (int y = 0; y <= 50; ++y) {
int power = calc(towers, radius, x, y);
if (power > hi)
hi = power, ax = x, ay = y;
}
return {ax, ay};
}
};

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

# Problem C - 大小为 K 的不重叠线段的数目 (opens new window)

from math import comb

class Solution:
def numberOfSets(self, n: int, k: int) -> int:
return comb(n + k - 1, 2 * k) % 1000000007

1
2
3
4
5

# Problem D - 奇妙序列 (opens new window)

#define MAXN 100005
#define MOD 1000000007
#define lson (idx << 1)
#define rson (idx << 1 | 1)
typedef long long ll;

struct Seg{
int l, r, val = 0, lazymul = 1, lazyadd = 0;
};

class Fancy {
int len = 0;
Seg s[MAXN << 2];

void build(int idx, int l, int r) {
s[idx].l = l, s[idx].r = r;
if (l == r)
return;
int mid = (l + r) >> 1;
build(lson, l, mid);
build(rson, mid + 1, r);
}

void pushdown(int idx) {
for (int i = lson; i <= rson; ++i) {
if (s[idx].lazymul != 1) {
s[i].val = (ll)s[i].val * s[idx].lazymul % MOD;
s[i].lazymul = (ll)s[i].lazymul * s[idx].lazymul % MOD;
}
s[i].val = ((ll)s[i].val + (ll)(s[i].r - s[i].l + 1) * s[idx].lazyadd) % MOD;
}
}
s[idx].lazymul = 1;
}

void calc(int idx) {
s[idx].val = ((ll)s[lson].val + s[rson].val) % MOD;
}

void add(int idx, int l, int r, int d) {
if (s[idx].l >= l && s[idx].r <= r) {
s[idx].val = ((ll)s[idx].val + (ll)(s[idx].r - s[idx].l + 1) * d) % MOD;
return;
}
pushdown(idx);
int mid = (s[idx].l + s[idx].r) >> 1;
if (l <= mid)
if (mid < r)
calc(idx);
}

void mul(int idx, int l, int r, int d) {
if (s[idx].l >= l && s[idx].r <= r) {
s[idx].val = (ll)s[idx].val * d % MOD;
s[idx].lazymul = (ll)s[idx].lazymul * d % MOD;
return;
}
pushdown(idx);
int mid = (s[idx].l + s[idx].r) >> 1;
if (l <= mid)
mul(lson, l, r, d);
if (mid < r)
mul(rson, l, r, d);
calc(idx);
}

int query(int idx, int l, int r) {
if (s[idx].l >= l && s[idx].r <= r)
return s[idx].val;
pushdown(idx);
int mid = (s[idx].l + s[idx].r) >> 1;
int ans = 0;
if (l <= mid)
ans += query(lson, l, r);
if (mid + 1 <= r)
ans += query(rson, l, r);
return ans;
}
public:
Fancy() {
build(1, 1, 100000);
}

void append(int val) {
len++;
}

if (len)
}

void multAll(int m) {
if (len)
mul(1, 1, len, m);
}

int getIndex(int idx) {
if (idx + 1 > len)
return -1;
return query(1, idx + 1, idx + 1);
}
};

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
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112