题目描述
给定一个 \(n \times m\) 的正整数矩阵,求其中最大的满足其中不存在两个位置数值相等的子矩阵大小。\(1 \leq n , m \leq 400\)。
本题有多种做法,而你需要寻找常数最小的做法才能通过本题。
solution 链表+双指针
枚举上边界,逐渐下移下边界,枚举左边界,尝试双指针获得右边界。困难之处在于,指针移动一次需要加入或删除 \(O(n)\) 个元素。观察一个元素带来的限制,我们需要找出在它之上或左边,与它相同的元素的列位置的前驱与后继,然后要求双指针区间包含这个元素时,不能同时也覆盖到它的前驱和后继。找出前驱、后继后将元素插入。这个前驱后继的部分可以离线逆序,使用双向链表求得。然后是这个元素的限制,我们使用不带删的双指针,每次都要求当前区间包含的元素的所有限制,当前区间的两个端点都满足,而限制之间可以合并,就是不能删除,是不删除双指针的特征。于是可以 \(O(n^3)\) 时间解决这个问题。
需要说明的是,这个算法的链表部分常数很大,这是因为其寻址不连续,过不了这一题。
【模板】不删除双指针 - caijianhong - 博客园 (cnblogs.com)
solution 双指针
设 \(f_{l, r, u}\) 表示固定左、右、上边界分别为 \(l, r, u\) 之后的下边界最大是多少。显然至少应有:
\[f_{l, r, u}\leq\min(f_{l+1, r, u}, f_{l, r-1, u}, f_{l, r, u+1}) \]你画一个图,缺失的部分是:\(a_{u, l}\neq a_{[u, d], r}\land a_{u, r}\neq a_{[u, d], l}\)(考虑从 \(f_{l, r, u+1}\) 转移而来,再考虑两个缩左右边界的对当前未判定部分造成的影响,发现中间部分已经合法)。于是可以开两个桶,双指针维护限制。
code
#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
#define debug(...) fprintf(stderr, ##__VA_ARGS__)
#else
#define endl "\n"
#define debug(...) void(0)
#endif
using LL = long long;
int n, m, a[410][410], f[2][410][410], buc[2][160010], ans;
int main() {
#ifndef LOCAL
#ifndef NF
freopen("c.in", "r", stdin);
freopen("c.out", "w", stdout);
#endif
cin.tie(nullptr)->sync_with_stdio(false);
#endif
cin >> n >> m;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) cin >> a[i][j];
}
memset(f[0], 0x3f, sizeof f[0]);
for (int t = 1; t <= m; t++) {
memset(f[t & 1], 0x3f, sizeof f[0]);
for (int l = 1, r = t; r <= m; l++, r++) {
int d = n;
for (int u = n; u >= 1; u--) {
int lim = min(f[~t & 1][l][u], f[~t & 1][l + 1][u]);
++buc[0][a[u][l]], ++buc[1][a[u][r]];
while (d >= u && (d > lim || buc[0][a[u][r]] > (t == 1)|| buc[1][a[u][l]] > (t == 1))) --buc[0][a[d][l]], --buc[1][a[d][r]], --d;
f[t & 1][l][u] = d;
debug("f[%d][%d][%d] = %d\n", l, r, u, d);
ans = max(ans, (d - u + 1) * t);
}
while (d) --buc[0][a[d][l]], --buc[1][a[d][r]], --d;
}
}
cout << ans << endl;
return 0;
}
标签:边界,--,题解,元素,CF407D,int,SS240928C,buc,指针
From: https://www.cnblogs.com/caijianhong/p/18438434/solution-CF407D