目录
3274. 检查棋盘方格颜色是否相同
原题链接
思路分析
AC代码
3275. 第 K 近障碍物查询
原题链接
思路分析
AC代码
3276. 选择矩阵中单元格的最大得分
原题链接
思路分析
AC代码
3277. 查询子数组最大异或值
原题链接
思路分析
AC代码
3274. 检查棋盘方格颜色是否相同
原题链接
3274. 检查棋盘方格颜色是否相同
思路分析
签到题
时间复杂度：O(1)
AC代码
class Solution:def checkTwoChessboards(self, s1: str, s2: str) -> bool:return (ord(s1[0]) % 2) ^ (ord(s2[0]) % 2) == (ord(s1[1]) % 2) ^ (ord(s2[1]) % 2)3275. 第 K 近障碍物查询
原题链接
3275. 第 K 近障碍物查询
思路分析
大根堆维护 topk 即可
时间复杂度O(qlogn)
AC代码
class Solution:def resultsArray(self, queries: List[List[int]], k: int) -> List[int]:h = []res = []for x, y in queries:heappush(h, (-abs(x) - abs(y), x, y))if len(h) > k:heappop(h)if len(h) < k:res.append(-1)else:res.append(-h[0][0])return res3276. 选择矩阵中单元格的最大得分
原题链接
3276. 选择矩阵中单元格的最大得分
思路分析
最大费用最大流
建立虚拟源汇点s，t
源点向每行连容量为1，费用为0的边
每行向行内数字连容量为1，费用为0的边
每个数字向汇点连容量为1，费用为数字的边
然后跑板子即可
时间复杂度：略，分析网络流复杂度没有意义
AC代码
using i64 = long long;struct MCFGraph{struct Edge{int v, cap, w;Edge(int _v, int _cap, int _w) : v(_v), cap(_cap), w(_w) {}};const int n;std::vector<Edge> e;std::vector<std::vector<int>> g;std::vector<i64> h, dis; // h 为 势 数组std::vector<int> pre;std::vector<bool> vis;void spfa(const int s, const int t) {static std::queue<int> q;h.assign(n, std::numeric_limits<i64>::min());q.push(s);h[s] = 0;while (q.size()) {int u = q.front();q.pop();vis[u] = false;for (int i : g[u]) {const auto& [v, cap, w] = e[i];if (cap > 0 && h[v] < h[u] + w) {h[v] = h[u] + w;if (!vis[v])q.push(v), vis[v] = true;}}}}bool dijkstra(const int s, const int t){static std::priority_queue<std::pair<i64, int>, std::vector<std::pair<i64, int>>> pq;dis.assign(n, std::numeric_limits<i64>::min());pre.assign(n, -1);dis[s] = 0;pq.emplace(0, s);while (pq.size()) {auto [d, u] = pq.top();pq.pop();if (dis[u] < d) continue;for (int i : g[u]) {const auto& [v, cap, w] = e[i];if (cap > 0 && dis[v] < w + d + h[u] - h[v]) {dis[v] = w + d + h[u] - h[v];pre[v] = i;pq.emplace(dis[v], v);}}}return dis[t] > std::numeric_limits<i64>::min();}MCFGraph(int _n) : n(_n), g(n), vis(n){}void addEdge(int u, int v, int c, int f) { // 最大流g[u].push_back(e.size());e.emplace_back(v, c, f);g[v].push_back(e.size());e.emplace_back(u, 0, -f);}std::pair<int, i64> flow(const int s, const int t) {int flow = 0;i64 cost = 0;h.assign(n, 0);spfa(s, t);while (dijkstra(s, t)) {// 更新h 为实际disfor (int i = 0; i < n; ++ i) h[i] += dis[i];int aug = std::numeric_limits<int>::max();for (int i = t; i != s; i = e[pre[i] ^ 1].v)aug = std::min(aug, e[pre[i]].cap);for (int i = t; i != s; i = e[pre[i] ^ 1].v)e[pre[i]].cap -= aug, e[pre[i] ^ 1].cap += aug;flow += aug;cost += (i64)aug * h[t];}return std::make_pair(flow, cost);}
};
class Solution {
public:int maxScore(vector<vector<int>>& grid) {int n = grid.size(), m = grid[0].size();// 0~99 0~n-1std::unordered_map<int, std::unordered_set<int>> adj;std::unordered_map<int, int> id;int tot = 0;for (int i = 0; i < n; ++ i) {for (int v : grid[i])if (!id.contains(v))id[v] = tot ++;}MCFGraph g(n + tot + 2);int s = n + tot, t = s + 1;for (int i = 0; i < n; ++ i) {for (int v : grid[i]) {adj[i].insert(id[v]);}g.addEdge(s, i, 1, 0);}for (auto &[i, v] : adj) {for (int x : v)g.addEdge(i, n + x, 1, 0);}for (auto &[x, i] : id)g.addEdge(n + i, t, 1, x);return g.flow(s, t).second;}
};3277. 查询子数组最大异或值
原题链接
3277. 查询子数组最大异或值
思路分析
区间DP
定义f(l, r) 为[l, r] 的数组异或值（注意这是题目的定义）
ma(l, r) 为 [l, r] 内所有子数组的最大数组异或值
那么f(l, r) = f(l, r - 1) ^ f(l + 1, r)
ma(l, r) = max(f(l, r), ma(l, r - 1), ma(l + 1, r))
本题不难，如果没有像我一样看错题的话
时间复杂度：O(N^2)
AC代码
class Solution {
public:vector<int> maximumSubarrayXor(vector<int>& nums, vector<vector<int>>& queries) {int n = nums.size();std::vector<std::vector<int>> f(n, std::vector<int>(n)), ma(f);for (int i = 0; i < n; ++ i) f[i][i] = ma[i][i] = nums[i];for (int len = 2; len <= n; ++ len) {for (int i = 0; i + len <= n; ++ i) {int j = i + len - 1;f[i][j] = f[i][j - 1] ^ f[i + 1][j];ma[i][j] = std::max({f[i][j], ma[i + 1][j], ma[i][j - 1]});}}std::vector<int> res;for (auto &q : queries)res.push_back(ma[q[0]][q[1]]);return res;}
};