记这周的周赛题

前言

这周周赛题目前1,2,3题还是很简单的,第四个比较难。在这里贴上我对于1,2,3题目的做法。第四个题目为复制零神的题解,以此参考学习。

1.可以形成最大正发行的矩形数目

题目:给你一个数组 rectangles ,其中 rectangles[i] = [li, wi] 表示第 i 个矩形的长度为 li 、宽度为 wi 。如果存在 k 同时满足 k <= li 和 k <= wi ,就可以将第 i 个矩形切成边长为 k 的正方形。例如,矩形 [4,6] 可以切成边长最大为 4 的正方形。设 maxLen 为可以从矩形数组 rectangles 切分得到的 最大正方形 的边长。返回可以切出边长为 maxLen 的正方形的矩形 数目 。

​ 这是一道很简单的签到题

​ 显然每一个2维数组的较小的那个就是他能行成的最大的正方形的边

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
int countGoodRectangles(vector<vector<int>>& rec) {
int len=rec.size();
map<int,int> a;
int mm=0;
for(int i=0;i<len;i++){
int k=min(rec[i][0],rec[i][1]);
a[k]++;
if(k>mm) mm=k;
}
return a[mm];
}
};

2.同积元组

题目描述:给你一个由 不同 正整数组成的数组 nums ,请你返回满足 a * b = c * d 的元组 (a, b, c, d) 的数量。其中 a、b、c 和 d 都是 nums 中的元素,且 a != b != c != d 。

​ 观察他给的案例,可以发现每一个满足条件的a,b,c,d可以有八种组合。因此只要找出有多少对满足条件的a,b,c,d记为ans,那么ans*8就是最后的答案;

那么如何计算ans的值,我们可以开一个map,记下每两个的乘积,如果一个乘积出现了两次或两次以上,则说明有多的数可以组成ab=cd,而我们只要选出2组就可以满足a* b=c* d 根据组合数公式
$$
C_n^2 = \frac{(n-1)n}{2}
$$
然后ans+=C_n^2 即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:

int tupleSameProduct(vector<int>& nums) {
int ans=0;
int len=nums.size();
map<int,int> a;
for(int i=0;i<len;i++){
for(int j=i+1;j<len;j++){
if(i==j) continue;
a[nums[i]*nums[j]]++;
}
}
for(auto &[sum,k]:a){
ans+=(k*(k-1))/2;
}
return (ans)*8;
}
};

3重新排列后的最大子矩阵

题目描述:给你一个二进制矩阵 matrix ,它的大小为 m x n ,你可以将 matrix 中的 列 按任意顺序重新排列。

请你返回最优方案下将 matrix 重新排列后,全是 1 的子矩阵面积。

示例:

image-20210117183913440

我们可以先用一个数组 a[i][j]表示到第i行,第j列上,连续的为1的矩形块,然后再对它进行排序,然后计算出最大值

代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
int largestSubmatrix(vector<vector<int>>& matrix) {
int m=matrix.size();
int n=matrix[0].size();
for(int i=1;i<m;i++){
for(int j=0;j<n;j++){
if(matrix[i][j]==1){
matrix[i][j]+=matrix[i-1][j];
}
}
}
int ans=0;
for(int i=0;i<m;i++){
sort(matrix[i].begin(),matrix[i].end(),[](int x,int y){return x>y;});
for(int j=0;j<n;j++){
ans=max(ans,(j+1)*matrix[i][j]);
}
}
return ans;
}
};

4.猫和老鼠||

很难,我做不来,下面是copy的零神的题解

前言
首先我们需要明确「必胜态」和「必败态」的概念:

一个状态为「必胜态」,当且仅当其相邻状态中至少有一个「必败态」。这里相邻的状态的定义为:在当前状态中进行决策的玩家可以到达的所有状态。也就是说,玩家可以选择移动到一个「必败态」,使得对手必败,因此当前状态是必胜的。

一个状态为「必败态」,当且仅当其相邻的所有状态都是「必胜态」。这里的道理是类似的,如果所有相邻状态都是「必胜态」,那么对手必胜,当前玩家必败。

在本题中,我们可以用(c_x,c_y,m_x,m_y,op) 表示一个状态,其中 (c_x, c_y)表示猫的位置,(m x,m y) 表示老鼠的位置,op 表示当前玩家是猫(op=1)还是老鼠(op=0)。

如果我们把每个状态抽象成图中的一个节点,状态A 可以到达状态B 就在它们对应的节点之间连接一条有向边,那么我们就可以使用动态规划或者记忆化搜索计算出所有状态是「必胜态」还是「必败态」。然而我们注意到,由于猫和老鼠都是根据规则任意进行移动的,甚至它们可以不进行移动,因此这个图实际上是存在环的。举一个很简单的例子,如果猫和老鼠在它们的轮次中都不进行移动,那么状态 A 可以到达状态 A (猫不移动),而状态A 也可以到达状态 A (老鼠不移动),这样 A 是否为「必胜态」依赖于其本身,我们就没法计算这些状态了。

然而题目中给出了一个提示:「如果老鼠不能在 10001000 次操作以内到达食物,那么猫获胜」,这使得我们可以在状态中加入一个维度,即 (c_x, c_y, m_x, m_y,op,step) ,其中 step 表示老鼠进行的操作次数。这样一来,整个图中就不存在环了,也就是图存在一个拓扑排序,我们就可以计算出所有状态了。实际上,老鼠的操作次数最多也就是 $ 8\times8=64 $ 次,因为老鼠不进行移动或者移动到之前到过的地方,都是没有意义的。

上面的做法已经可以通过本题,例如 【记忆化搜索】思路简单,比较暴力
题解中就使用了这种方法。这里我们给出一种时间复杂度更优的做法,可以忽略 \textit{step}step 维度,直接在存在环的原图上进行一种特殊的「拓扑排序」并得到答案。

方法一:拓扑排序
思路与算法

虽然图中的每个节点都至少在一个环中,我们无法计算出任意一个节点的状态,但我们是预先知道某些状态是「必胜态」还是「必败态」的,也就是游戏结束判定的前三条:

如果猫跟老鼠处在相同的位置,那么猫获胜;

如果猫先到达食物,那么猫获胜;

如果老鼠先到达食物,那么老鼠获胜。

这些判定情况对应的所有状态都可以预先计算出,那么接下来就很好办了,我们可以反过来考虑「必胜态」和「必败态」的计算条件:

一个状态为「必胜态」,当且仅当其相邻状态中至少有一个「必败态」。因此,如果一个状态是「必败态」,那么其相邻的所有状态都是「必胜态」。因此我们可以从预先计算出的所有「必败态」开始进行广度优先搜索,它们相邻的所有状态都是「必胜态」;

一个状态为「必败态」,当且仅当其相邻的所有状态都是「必胜态」。因此,如果一个状态是「必胜态」,那么我们可以将其相邻的所有状态的入度都减少 11。如果某个状态的入度减少到了 00 并且它还没有被计算过,那么说明其相邻的所有状态都是「必胜态」,那么它就是「必败态」。

因此我们只需要预处理出所有状态的入度,并且计算出所有与游戏结束相关的状态,随后进行广度优先搜索即可。由于图中存在环,因此并不是每个状态都能够确定其是「必胜态」还是「必败态」,那些状态实际上就是猫和老鼠陷入了循环,那么根据规则判定猫获胜。

流程

算法的流程如下:

预处理出所有状态的入度;

预处理出所有已经确定的游戏结束状态是「必胜态」还是「必败态」,并把它们放入队列中;

依次从队列中取出状态,如果该状态是「必败态」,那么将所有其相邻且未计算的状态变为「必胜态」,并全部放入队列中;如果该状态是「必胜态」,那么将所有其相邻且未计算的状态的入度减少 11,如果某个相邻的状态入度减少为 00,那么就将其状态变为「必败态」,并放入队列中。

在广度优先搜索结束后,如果初始状态如果为「必败态」或者未计算过,那么猫获胜,否则老鼠获胜。

代码

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
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
class Solution {
private:
// f[cat_x][cat_y][mouse_x][mouse_y][is_cat_round] = 如果当前玩家必胜那么为 1,否则为 -1
int f[8][8][8][8][2];
// 统计每个状态的入度,用于拓扑排序
int degree[8][8][8][8][2];

static constexpr int dirs[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

public:
bool canMouseWin(vector<string>& grid, int catJump, int mouseJump) {
int m = grid.size();
int n = grid[0].size();

auto findPosition = [&](char c) -> pair<int, int> {
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (grid[i][j] == c) {
return {i, j};
}
}
}
return {-1, -1};
};

auto getNeighbors = [&](int x, int y, int bound) -> vector<pair<int, int>> {
vector<pair<int, int>> ret = {{x, y}};
for (int d = 0; d < 4; ++d) {
int xx = x, yy = y;
for (int _ = 1; _ <= bound; ++_) {
xx += dirs[d][0];
yy += dirs[d][1];
if (xx < 0 || xx >= m || yy < 0 || yy >= n || grid[xx][yy] == '#') {
break;
}
ret.emplace_back(xx, yy);
}
}
return ret;
};

auto [cx, cy] = findPosition('C');
auto [mx, my] = findPosition('M');
auto [fx, fy] = findPosition('F');

for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (grid[i][j] != '#') {
for (int k = 0; k < m; ++k) {
for (int l = 0; l < n; ++l) {
if (grid[k][l] != '#') {
degree[i][j][k][l][0] = getNeighbors(i, j, catJump).size();
degree[i][j][k][l][1] = getNeighbors(k, l, mouseJump).size();
}
}
}
}
}
}

memset(f, 0, sizeof(f));
queue<tuple<int, int, int, int, int>> q;

// 猫和老鼠重合
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (grid[i][j] != '#' && grid[i][j] != 'F') {
f[i][j][i][j][0] = 1;
f[i][j][i][j][1] = -1;
q.emplace(i, j, i, j, 0);
q.emplace(i, j, i, j, 1);
}
}
}

// 猫 or 老鼠到达食物
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (grid[i][j] != '#' && grid[i][j] != 'F') {
f[fx][fy][i][j][1] = -1;
f[i][j][fx][fy][0] = -1;
q.emplace(fx, fy, i, j, 1);
q.emplace(i, j, fx, fy, 0);
}
}
}

while (!q.empty()) {
auto [catx, caty, mousex, mousey, op] = q.front();
q.pop();
if (op == 0) {
vector<pair<int, int>> neighbors = getNeighbors(mousex, mousey, mouseJump);
for (auto [x, y]: neighbors) {
--degree[catx][caty][x][y][op ^ 1];
if (!f[catx][caty][x][y][op ^ 1]) {
if (f[catx][caty][mousex][mousey][op] == -1) {
f[catx][caty][x][y][op ^ 1] = 1;
q.emplace(catx, caty, x, y, op ^ 1);
}
else if (degree[catx][caty][x][y][op ^ 1] == 0) {
f[catx][caty][x][y][op ^ 1] = -1;
q.emplace(catx, caty, x, y, op ^ 1);
}
}
}
}
else {
vector<pair<int, int>> neighbors = getNeighbors(catx, caty, catJump);
for (auto [x, y]: neighbors) {
--degree[x][y][mousex][mousey][op ^ 1];
if (!f[x][y][mousex][mousey][op ^ 1]) {
if (f[catx][caty][mousex][mousey][op] == -1) {
f[x][y][mousex][mousey][op ^ 1] = 1;
q.emplace(x, y, mousex, mousey, op ^ 1);
}
else if (degree[x][y][mousex][mousey][op ^ 1] == 0) {
f[x][y][mousex][mousey][op ^ 1] = -1;
q.emplace(x, y, mousex, mousey, op ^ 1);
}
}
}
}
}

return f[cx][cy][mx][my][1] == 1;
}
};

复杂度分析

时间复杂度:O(m^2n^2(m+n))其中 m 和 n 分别是方格的行数和列数。

空间复杂度:O(m^2n^2)O(m2n2)