P8317 [FOI2021] 幸运区间
分治 + dfs
首先可以发现 \(k\) 和 \(d\) 很小，所以是可以搜索的。
那么就考虑如何枚举区间，显然 \(n^2\) 枚举是会超时的，所以就考虑分治来求。
求的过程中就分成三种情况来处理：在左边一半，在右边一半，以及跨越中间点。显而易见的是，跨越中间点的区间肯定是包含 \(mid\) 的，所以我们就可以从 \(mid\) 为起点往往左右扩展。
然后搜索的时候每一次先尽量用之前选过的数来扩展这个区间，然后再向左边区间或者右边区间添加幸运数字去扩展。
int n, m, k;
int w[N][M];
bool flg[N];
int ansl, ansr, len;
int cnt;
void dfs(int l, int r, int L, int R) {
// 向左右尽可能扩展区间
while (l < L) {
bool st = false;
for (int i = 1; i <= m; i ++)
st |= flg[w[L - 1][i]];
if (st) L --;
else break;
}
while (r > R) {
bool st = false;
for (int i = 1; i <= m; i ++)
st |= flg[w[R + 1][i]];
if (st) R ++;
else break;
}
// 更新答案
if (len < R - L + 1) len = R - L + 1, ansr = R, ansl = L;
else if (len == R - L + 1 && ansl > L) ansr = R, ansl = L;
if (cnt == k) return ;
// 向左右添加幸运数字去扩展
if (l < L)
for (int i = 1; i <= m; i ++) {
cnt ++;
flg[w[L - 1][i]] = true;
dfs(l, r, L - 1, R);
flg[w[L - 1][i]] = false;
cnt --;
}
if (r > R)
for (int i = 1; i <= m; i ++) {
cnt ++;
flg[w[R + 1][i]] = true;
dfs(l, r, L, R + 1);
flg[w[R + 1][i]] = false;
cnt --;
}
}
void get(int l, int r) {
if (l == r) return ;
int mid = (l + r) >> 1;
get(l, mid), get(mid + 1, r);
cnt = 1;
for (int i = 1; i <= m; i ++) {
flg[w[mid][i]] = true;
dfs(l, r, mid, mid);
flg[w[mid][i]] = false;
}
}
int main(){
int T = fr();
for (int id = 1; id <= T; id ++) {
printf("Case #%d: ", id);
n = fr(), m = fr(), k = fr();
for (int i = 1; i <= n; i ++)
for (int j = 1; j <= m; j ++)
w[i][j] = fr();
ansl = 1, ansr = 1;
len = 1;
get(1, n);
fw(ansl - 1), kg, fw(ansr - 1), ch;
}
return 0;
}