周赛传送门
还是两道题，怎么办呢？
1991. 找到数组的中间位置
思路：枚举，求和
时间复杂度： O ( n ) O(n) O(n)
首先求出 n n n 个数字的累加和 s u m sum sum。
然后枚举位置 i i i，并在枚举过程中计算前缀和 p a r t part part，如果 p a r t = s u m ? p a r t ? n u m s i part = sum - part - nums_i part=sum?part?numsi?，则 i i i 即为答案。如果不存在这样的 i i i，则答案为 ? 1 -1 ?1。
完整代码如下：
class Solution {
public:
int findMiddleIndex(vector<int>& nums) {
int sum = 0;
for (auto n : nums) { sum += n; }
int part = 0;
for (int i = 0; i < nums.size(); i++) {
if (part == sum-part-nums[i]) {
return i;
}
part += nums[i];
}
return -1;
}
};
1992. 找到所有的农场组
思路：暴力枚举，标记
时间复杂度： O ( n ? m ) O(n*m) O(n?m)
从上到下，从左到右依次枚举枚举 ( i , j ) (i,j) (i,j)，如果 l a n d i , j land_{i,j} landi,j? 为 1，则说明 ( i , j ) (i,j) (i,j) 为一块农场组的左上角。
接着，从 ( i , j ) (i,j) (i,j) 找出该农场组的高和宽，并将属于该农场组的 l a n d x , y land_{x,y} landx,y? 全部置为 0。
不难发现，每个初始值为 1 的 l a n d ( i , j ) land_(i,j) land(?i,j) 最多会被访问三次，每个初始值为 0 0 0 的 l a n d ( i , j ) land_(i,j) land(?i,j) 会被访问一次。因此总的时间复杂度为 O ( n ? m ) O(n*m) O(n?m)。
class Solution {
public:
vector<vector<int>> findFarmland(vector<vector<int>>& land) {
int n = land.size();
int m = land[0].size();
vector<vector<int>> anw;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (land[i][j]) {
int r = j;
while (r+1 < m && land[i][r+1]) { r++; }
int b = i;
while(b+1 < n && land[b+1][j]) {b++;}
anw.push_back(std::vector<int>{i,j,b,r});
for (int k = i; k <= b; k++) {
for (int p = j; p <= r; p++) {
land[k][p] = 0;
}
}
}
}
}
return anw;
}
};
1993. 树上的操作
思路：模拟，树的遍历
时间复杂度： O ( n ? o p ) O(n*op) O(n?op)，其中 n n n 是节点的数量， o p op op 是操作次数(确切的说，是 upgrade 的次数)。
设有一维数组 l o c k e r locker locker， l o c k e r i locker_i lockeri? 表示第 i i i 个节点的持有者。如果 l o c k e r i locker_i lockeri? 为 -1，代表对应节点未上锁。
lock 操作
判断 l o c k e r i locker_i lockeri? 是否为 ? 1 -1 ?1 即可：
- 如果为 -1，则上锁成功，更新 l o c k e r i locker_i lockeri? 并返回 true。
- 如果不为 ? 1 -1 ?1，则上锁失败，返回 false。
时间复杂度为 O ( 1 ) O(1) O(1)。
unlock 操作
判断 l o c k e r i locker_i lockeri? 是否与 u s e r user user 相等 ：
- 相等，解锁成功，更新 l o c k e r i locker_i lockeri? 为 -1，并返回 true。
- 不相等，解锁失败，返回 false。
时间复杂度为 O ( 1 ) O(1) O(1)。
upgrade 操作
首先，检查
n
u
m
num
num 到
r
o
o
t
root
root 这条路径上的节点是否全未上锁。
其次，检查
n
u
m
num
num 的子树中是否有已上锁的节点。
如果上述条件都满足，则更新 l o c k e r n u m locker_num lockern?um 并将子树中的节点全部解锁。
时间复杂度为 O ( n ) O(n) O(n)。
class LockingTree {
bool check(int root) {
bool res = (locker[root] != -1);
locker[root] = -1;
for (auto next : edge[root]) {
res = (check(next) || res);
}
return res;
}
public:
vector<int> parent;
vector<int> locker;
vector<vector<int>> edge; // 构造边表，方便遍历子树。
LockingTree(vector<int>& p) : parent(p), locker(parent.size(), -1), edge(parent.size()) {
for (int i = 0; i < parent.size(); i++) {
if (parent[i] != -1) {
edge[parent[i]].push_back(i);
}
}
}
int ans = 1;
bool lock(int num, int user) {
if (locker[num] != -1) {
return false;
}
locker[num] = user;
return true;
}
bool unlock(int num, int user) {
if (locker[num] != user) {
return false;
}
locker[num] = -1;
return true;
}
bool upgrade(int num, int user) {
int p = num;
while (p != -1 && locker[p] == -1) {
p = parent[p];
}
if (p != -1) {
return false;
}
if (!check(num)) {
return false;
}
locker[num] = user;
return true;
}
};
1994. 好子集的数目
思路：状态压缩，滚动数组，组合
时间复杂度： O ( s + m ? 2 p ) O(s+m*2^p) O(s+m?2p)。
时间复杂度的标识比较啰嗦，这里解释下：
- s s s 为输入数字的数量
- m m m 为不重复的数字的数量
- p p p 为取值范围内素数的数量
假设用前 i ? 1 i-1 i?1 个数字可构造出 k k k 个好子集，记为 S 1 S_1 S1?， S 2 S_2 S2?，…， S k S_k Sk?。现在要用这 k k k 个集合以及数字 n u m s i nums_i numsi? 构造出一批新的集合，该如何构造呢？
不难想到，如果 n u m s i nums_i numsi? 本身包含重复的质因子，如 12 12 12 可拆分为 2 , 2 , 3 2,2,3 2,2,3，则显然无法构造出新的好子集。因此，只需考虑本身无重复质因子的 n u m s i nums_i numsi?。
新的好子集可由两种方式构造而来：
- 第一种：仅包含 n u m s i nums_i numsi? 的好子集，这种子集有且只有一个。
- 第二种：由 S j S_j Sj? 和 n u m s i nums_i numsi? 拼接而来。
不难想到，可遍历所有的 S j S_j Sj?，判断 S j S_j Sj? 包含的质因子是否与 n u m s i nums_i numsi? 的有重复，如果没有重复，则得到了一个新的好子集 S j ′ = { S j , n u m s i } S_j' = \{S_j, nums_i\} Sj′?={Sj?,numsi?}。
但是，
k
k
k 很大，枚举的效率太低，不能接受。继续分析，由于
n
u
m
s
i
nums_i
numsi? 的取值范围为 [1,30]，因此
S
j
S_j
Sj? 包含的质因子不外乎以下十个素数：
(
2
,
3
,
5
,
7
,
11
,
13
,
17
,
19
,
23
,
29
)
(2,3,5,7,11,13,17,19,23,29)
(2,3,5,7,11,13,17,19,23,29)
考虑把包含相同质因子的好子集划分为一类，则最多有 2 10 ? 1 = 1023 2^{10}-1=1023 210?1=1023 种好子集。
设有二维数组 d p dp dp。 d p i , m a s k dp_{i,mask} dpi,mask? 表示前 i i i 个数字中，恰好包含素数集 m a s k mask mask 的好子集的数量。 m a s k mask mask 最低位的十个比特对应上述十个素数，比特值为 1 代表包含了对应素数，反之则未包含。
m a s k mask mask 的取值范围为 [ 0 , 1023 ] [0,1023] [0,1023]， m a s k = 0 mask=0 mask=0 表示空集或仅含 1 1 1 的集合的数量。
设 n u m s i nums_i numsi? 包含的素数集为 q i q_i qi?。特别的，如果 n u m s i nums_i numsi? 包含重复的素数，则将 q i q_i qi? 置为 ? 1 -1 ?1。
于是可得出状态转移方程：
- 当
q
i
=
?
1
q_i=-1
qi?=?1 或者
q
i
?
m
a
s
k
q_i\nsubseteq mask
qi??mask 时:
d p i , m a s k = d p i ? 1 , m a s k dp_{i,mask} = dp_{i-1,mask} dpi,mask?=dpi?1,mask? - 当
q
i
≠
?
1
q_i\ne -1
qi??=?1 且
q
i
?
m
a
s
k
q_i\subseteq mask
qi??mask 时:
d p i , m a s k = d p i ? 1 , k + d p i ? 1 , k ? x o r ? q i dp_{i,mask} = dp_{i-1,k} + dp_{i-1,k\ xor\ q_i} dpi,mask?=dpi?1,k?+dpi?1,k?xor?qi??
上述方程的时间复杂度太高了，大约是 1 e 5 ? 2 1 0 = 1 e 9 1e5*2^10=1e9 1e5?210=1e9 量级的，基本是超时啦。
继续分析，考虑到里面有大量重复的数字，我们先统计每个数字出现的次数，记为 c n t cnt cnt。
c n t i cnt_i cnti? 代表数字 i i i 在 n u m s nums nums 中出现的次数，显然在本题中 i ∈ [ 1 , 30 ] i\in [1,30] i∈[1,30]。
因此， d p i , m a s k dp_{i,mask} dpi,mask? 的含义变化为在前 i i i 种数字中，恰好包含素数集 m a s k mask mask 的好子集的数量。设 q i q_i qi? 为数字 i i i 包含的素数集。
状态转移方程如下：
- 当
i
=
1
i = 1
i=1 时，显然
m
a
s
k
mask
mask 只能为 0:
d p 1 , m a s k = { 2 c n t 1 , m a s k = 0 0 , m a s k ≠ 0 dp_{1,mask} = \left\{ \begin{array}{c} 2^{cnt_1}&, mask = 0 \\ 0&,mask\ne 0 \\ \end{array}\right. dp1,mask?={2cnt1?0?,mask=0,mask?=0? - 当
i
>
1
i \gt 1
i>1，且
q
i
=
?
1
q_i = -1
qi?=?1 或者
q
i
?
m
a
s
k
q_i\nsubseteq mask
qi??mask 时:
d p i , m a s k = d p i ? 1 , m a s k dp_{i,mask} = dp_{i-1,mask} dpi,mask?=dpi?1,mask? - 当
i
>
1
i \gt 1
i>1，且
q
i
≠
?
1
q_i \ne -1
qi??=?1 且
q
i
?
k
q_i\subseteq k
qi??k 时:
d p i , m a s k = d p i ? 1 , m a s k + d p i ? 1 , m a s k ? x o r ? q i ? c n t i dp_{i,mask}=dp_{i-1,mask} + dp_{i-1,mask\ xor\ q_i}*cnt_i dpi,mask?=dpi?1,mask?+dpi?1,mask?xor?qi???cnti?
最终答案为
∑
i
=
1
1023
d
p
30
,
i
\sum_{i=1}^{1023}dp_{30,i}
i=1∑1023?dp30,i?
class Solution {
public:
int numberOfGoodSubsets(vector<int>& nums) {
const int n = (1<<10);
int64_t dp[2][n] = {0};
int now = 0, pre = 1;
const int mod = 1e9+7;
int p[10] = {2,3,5,7,11,13,17,19,23,29};
int d[31] = {0};
for (int i = 2; i <= 30; i++) {
int mask = 0;
int tmp = i;
for (int j = 0; j < 10; j++) {
if (tmp%p[j] == 0) {
tmp /= p[j];
mask |= (1<<j);
}
}
if (tmp == 1) {
d[i] = mask;
}
}
int64_t cnt[31] = {0};
for (int i = 0; i < nums.size(); i++) {
cnt[nums[i]]++;
}
dp[pre][0] = 1;
for (int i = 1; i <= cnt[1]; i++) {
(dp[pre][0] *= 2) %= mod;
}
for (int i = 2; i <= 30; i++, swap(pre, now)) {
memcpy(dp[now], dp[pre], sizeof(dp[now]));
if (d[i] == 0) { continue; }
for (int j = 0; j < n; j++) {
if ((j&d[i]) == d[i]) {
(dp[now][j] += dp[pre][j^d[i]]*cnt[i]) %= mod;
}
}
}
int sum = 0;
for (int i = 1; i < n; i++) {
(sum += dp[pre][i])%=mod;
}
return sum;
}
};