# # Leetcode 第35场双周赛题解

## # Problem A - 所有奇数长度子数组的和 (opens new window)

class Solution:
def sumOddLengthSubarrays(self, arr: List[int]) -> int:
n = len(arr)
s = [0]
for i in arr:
s.append(s[-1] + i)
ans = 0
for i in range(1, n + 1, 2):
for j in range(1, n + 1):
if j + i - 1 > n:
break
ans += s[j + i - 1] - s[j - 1]
return ans

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

## # Problem B - 所有排列中的最大和 (opens new window)

typedef long long ll;
const ll MOD = 1e9 + 7;

class Solution {
public:
int maxSumRangeQuery(vector<int>& nums, vector<vector<int>>& requests) {
int n = nums.size();
vector<int> d(n + 2);
for (auto v : requests) {
int l = v[0] + 1, r = v[1] + 1;
d[l]++;
d[r + 1]--;
}
vector<int> t(n);
t[0] = d[1];
for (int i = 1; i < n; ++i)
t[i] = t[i - 1] + d[i + 1];
sort(t.rbegin(), t.rend());
sort(nums.rbegin(), nums.rend());
ll ans = 0;
for (int i = 0; i < n; ++i)
ans = (ans + (ll)nums[i] * t[i]) % MOD;
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

## # Problem C - 使数组和能被 P 整除 (opens new window)

typedef long long ll;

class Solution {
public:
int minSubarray(vector<int>& nums, int p) {
int ans = -1;
unordered_map<int, int> last;
ll sum = 0;
for (int num : nums)
sum += num;
int target = sum % p;
if (target == 0)
return 0;
last[0] = 0;
int n = nums.size();
ll now = 0;
for (int i = 1; i <= n; ++i) {
now += nums[i - 1];
now %= p;
ll need = (now - target + p) % p;
if (last.count(need)) {
int len = i - last[need];
if (ans == -1)
ans = len;
else
ans = min(ans, len);
}
last[now] = i;
}
return ans == n ? -1 : 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

## # Problem D - 奇怪的打印机 II (opens new window)

#define C 60
#define INF 0x3f3f3f3f

class Solution {
public:
bool isPrintable(vector<vector<int>>& targetGrid) {
int n = targetGrid.size(), m = targetGrid[0].size();
vector<int> l(C + 1, INF), r(C + 1, 0), u(C + 1, INF), d(C + 1, 0);
vector<bool> vis(C + 1);
for (int i = 0; i < n; ++i)
for (int j = 0; j < m; ++j) {
int c = targetGrid[i][j];
vis[c] = true;
l[c] = min(l[c], j + 1);
r[c] = max(r[c], j + 1);
u[c] = min(u[c], i + 1);
d[c] = max(d[c], i + 1);
}
vector<int> in(C + 1);
int cnt = 0;
for (int i = 1; i <= C; ++i) {
if (!vis[i])
continue;
cnt++;
for (int j = 1; j <= C; ++j) {
if (!vis[j] || i == j)
continue;
int L = max(l[i], l[j]), R = min(r[i], r[j]);
int U = max(u[i], u[j]), D = min(d[i], d[j]);
bool vi = false, vj = false;
for (int p = U; p <= D; ++p)
for (int q = L; q <= R; ++q) {
if (targetGrid[p - 1][q - 1] == i)
vi = true;
if (targetGrid[p - 1][q - 1] == j)
vj = true;
}
if (vi && vj)
return false;
if (vi)
if (vj)
}
}
queue<int> q;
for (int i = 1; i <= C; ++i)
if (vis[i] && in[i] == 0)
q.push(i);
vector<int> topo;
while (!q.empty()) {
int u = q.front();
q.pop();
topo.emplace_back(u);
for (int v : adj[u]) {
in[v]--;
if (in[v] == 0)
q.push(v);
}
}
return cnt == (int)topo.size();
}
};

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