【蓝桥杯】每日练习 Day 16,17

前言

接下来是这两天的题目（昨天主播打完模拟赛感觉身体被掏空所以没有写题目的总结），只有三道题。

一道并查集，一道单调栈和一道单调队列。

---

奶酪

---

分析

这是一道模板题（连通块），只讲思路。

bfs和dfs是可以解的，不过这道题推荐使用并查集，代码也简单。

---

代码

/*n ^ n。并查集，如果两个节点能够相切或相交就放到一起
*/
#include<iostream>
using namespace std;
const int N = 10010;
typedef long long LL;
int n, h, r;
int t;
int f[N];
struct Node
{int x, y, z;
}node[N];
​
LL ls(Node& A, Node& B)
{LL x = A.x - B.x, y = A.y - B.y, z = A.z - B.z;return x * x + y * y + z * z;
} //计算距离
​
int find(int x)
{if(f[x] == x) return x;return f[x] = find(f[x]);
}
​
bool func()
{scanf("%d%d%d", &n, &h, &r);for(int i = 1; i <= n; i++)f[i] = i;for(int i = 1; i <= n; i++)scanf("%d%d%d", &node[i].x, &node[i].y, &node[i].z);for(int i = 1; i <= n; i++)for(int j = i + 1; j <= n; j++){ //计算距离if(ls(node[i], node[j]) <= (LL)r * r * 4) //相切或相交f[find(i)] = find(j); //合并}for(int i = 1; i <= n; i++){if(node[i].z <= r) //在底端。{for(int j = 1; j <= n; j++) //顶端{if(node[j].z + r >= h && find(i) == find(j)) return true;}}}return false;
}
​
int main()
{scanf("%d", &t);while(t--){if(func())printf("Yes\n");elseprintf("No\n");}return 0;
}

---

矩形牛棚

---

分析

又是一道模板题，模板请见：直方图之中的最大矩形

讲一下模板的思路，显然直接枚举的话时间复杂度O(n^6)这很恐怖了，虽然可以使用前缀和将时间复杂度降低到O(n^4)但这显然也是无法通过的。

所以我们考虑优化，能不能通过线性的时间复杂度来通过这道题。

根据木桶定理，一个矩形的面积往往是由高度最低的点决定的。

但这道题高度显然是两个方向，我们控制变量，来枚举下边界。

随后我们预处理出每个点向上的高度，再根据贪心，一个矩形若想要面积最大一定要到达某个点的最高高度，所以我们枚举这个点即可。

在枚举这个点时就要考虑到宽度，因为我们假设的是这个点到达最大高度，所以我们要保证左右两端的高度都要大于等于当前高度，并且尽可能地大。

那么问题就转化成了，顺序结构中比当前点小的第一个点，考虑使用单调栈。

---

代码

/*木桶定理，矩阵的高度是由高度最低的矩形确定的预处理：分别求出左右两边高度小于当前位置的位置根据贪心，最大的矩形的高度一定是受到了某个高度的限制枚举受每个高度限制的所有可能，随后求max这题面积要用LL来存
*/
#include<iostream>
#include<stack>
#define s second
#define f first
using namespace std;
typedef pair<int, int> PII;
typedef long long LL;
const int N = 100010;
int h[N], l[N], r[N];
int n;
stack<int> stk;
int main()
{while(scanf("%d", &n) && n){for(int i = 1; i <= n; i++)scanf("%d", h + i);stk = stack<int>();for(int i = 1; i <= n; i++){while(stk.size() && h[stk.top()] >= h[i]) stk.pop();if(stk.size())l[i] = stk.top();elsel[i] = 0;stk.push(i);}stk = stack<int>();for(int i = n; i >= 1; i--){while(stk.size() && h[stk.top()] >= h[i]) stk.pop();if(stk.size())r[i] = stk.top();elser[i] = n + 1;stk.push(i);}LL s = 0;for(int i = 1; i <= n; i++){//printf("i = %d l = %d r = %d\n", h[i], h[l[i]], h[r[i]]);s = max(s, (LL)h[i] * (r[i] - l[i] - 1));}printf("%lld\n", s);}return 0;
}

---

子矩阵

---

分析

同样的是一道模板题，求区间内的最值，考虑使用单调队列。

因为区间是固定的，所以这道题我们可以先对行进行单调队列预处理，随后再对列进行单调队列预处理。（经典降维）

---

代码

/*枚举起点，单调队列O(n ^ 3)勉强可以预处理每一列的最值
*/
#include<iostream>
#include<queue>
using namespace std;
typedef long long LL;
const int N = 1010;
const int MOD = 998244353;
int a, b, n, m;
int map[N][N];
int mx[N][N], mn[N][N];
int mx1[N][N], mn1[N][N];
​
int main()
{scanf("%d%d%d%d", &n, &m, &a, &b);for(int i = 1; i <= n; i++)for(int j = 1; j <= m; j++)scanf("%d", &map[i][j]);for(int i = 1; i <= n; i++){deque<int> dq;for(int j = 1; j <= m; j++){while(dq.size() && map[i][dq.back()] <= map[i][j]) dq.pop_back();dq.push_back(j);mx[i][j] = map[i][dq.front()];if(dq.front() == j - b + 1) dq.pop_front();} //存储最大值dq = deque<int>();for(int j = 1; j <= m; j++){while(dq.size() && map[i][dq.back()] >= map[i][j]) dq.pop_back();dq.push_back(j);//printf("%d ", map[i][dq.front()]);mn[i][j] = map[i][dq.front()];if(dq.front() == j - b + 1) dq.pop_front();}}for(int j = 1; j <= m; j++){deque<int> dq;for(int i = 1; i <= n; i++){while(dq.size() && mx[dq.back()][j] <= mx[i][j]) dq.pop_back();dq.push_back(i);mx1[i][j] = mx[dq.front()][j];if(dq.front() == i - a + 1) dq.pop_front();}dq = deque<int>();for(int i = 1; i <= n; i++){while(dq.size() && mn[dq.back()][j] >= mn[i][j]) dq.pop_back();dq.push_back(i);mn1[i][j] = mn[dq.front()][j];//printf("%d ", mn[i][j]);if(dq.front() == i - a + 1) dq.pop_front();}}LL s = 0;for(int i = a; i <= n; i++)for(int j = b; j <= m; j++){//printf("%d %d\n", mx[i][j], mn[i][j]);s = (s + (LL)mx1[i][j] * mn1[i][j]) % MOD;}printf("%lld", s);
}

顺便问一下，有没有好的方法能将行优先和列优先的两个代码整合到一个函数中去？