# # Leetcode 第301场周赛题解

## # Problem A - 装满杯子需要的最短总时长 (opens new window)

### # 方法一：数学

• 时间复杂度 $\mathcal{O}(N)$
• 空间复杂度 $\mathcal{O}(1)$

class Solution:
def fillCups(self, amount: List[int]) -> int:
hi = max(amount)
tot = sum(amount)
return (tot - 1) // 2 + 1 if hi * 2 <= tot else hi


1
2
3
4
5
6

## # Problem B - 无限集中的最小数字 (opens new window)

### # 方法一：平衡树

• 时间复杂度：初始化 $\mathcal{O}(C\log C)$popSmallest() $\mathcal{O}(\log C)$addBack() $\mathcal{O}(\log C)$
• 空间复杂度 $\mathcal{O}(C)$

class SmallestInfiniteSet {
set<int> s;
public:
SmallestInfiniteSet() {
for (int i = 1; i <= 1001; ++i)
s.insert(i);
}

int popSmallest() {
int ret = *s.begin();
s.erase(s.begin());
return ret;
}

s.insert(num);
}
};


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

## # Problem C - 移动片段得到字符串 (opens new window)

### # 方法一：依次比较

• 时间复杂度 $\mathcal{O}(|S|+|T|)$
• 空间复杂度 $\mathcal{O}(|S|+|T|)$

class Solution {
public:
bool canChange(string start, string target) {
int n = start.size();
vector<pair<char, int>> ps, pt;
for (int i = 0; i < n; ++i) {
if (start[i] != '_')
ps.emplace_back(start[i], i);
if (target[i] != '_')
pt.emplace_back(target[i], i);
}

if (ps.size() != pt.size())
return false;

int m = ps.size();
for (int i = 0; i < m; ++i) {
if (ps[i].first != pt[i].first)
return false;

if (ps[i].first == 'L' && ps[i].second < pt[i].second)
return false;

if (ps[i].first == 'R' && ps[i].second > pt[i].second)
return false;
}

return true;
}
};

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

## # Problem D - 统计理想数组的数目 (opens new window)

### # 方法一：动态规划

• 时间复杂度 $\mathcal{O}(N+K(\log K)^2)$
• 空间复杂度 $\mathcal{O}(N+K)$

using ll = long long;
const ll MOD = 1e9 + 7;
const int N = 10005;

ll fexp(ll x, ll y) {
ll ans = 1;
while (y) {
if (y & 1) ans = (ans * x) % MOD;
x = (x * x) % MOD;
y >>= 1;
}
return ans;
}

ll mod_inv(ll x) { return fexp(x, MOD - 2); }

bool inited = false;

ll fac[N], ifac[N];

void init() {
if (!inited) {
inited = true;
fac[0] = ifac[0] = 1;
for (int i = 1; i < N; ++i) fac[i] = (fac[i - 1] * i) % MOD;
ifac[N - 1] = mod_inv(fac[N - 1]);
for (int i = N - 2; i >= 0; --i) ifac[i] = (ifac[i + 1] * (i + 1)) % MOD;
}
}

ll comb(int n, int k) { return fac[n] * ifac[k] % MOD * ifac[n - k] % MOD; }

class Solution {
public:
int idealArrays(int n, int maxValue) {
init();
ll ans = 0;
unordered_map<int, ll> now;
for (int i = 1; i <= maxValue; ++i) now[i] = 1;

for (int round = 1; !now.empty() && round <= n; ++round) {
for (auto [_, v]: now)
ans = (ans + comb(n - 1, round - 1) * v % MOD) % MOD;
unordered_map<int, ll> nxt;
for (auto [k, v]: now)
for (int i = 2; i * k <= maxValue; ++i)
nxt[i * k] = (nxt[i * k] + v) % MOD;
now = move(nxt);
}

return ans;
}
};

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