P8317 [FOI2021] 幸运区间

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;
}