[题解] [JSOI2014] 拼图

题面

题解

这个 (n * m leq 100000) 数据范围告诉我们要根号分治

我们对于一段区间 ([u, d]) (上下的区间), 将所有拼图分为两类, 一类是这块中在这一段区间从左到右全都是 0 , 或者是只有一部分是 0

那么最后这一段区间的答案就是把全是零的放在中间, 左边接一个 0 最多的, 右边接一个 0 最多的

有可能这两个最多的是同一个, 所以还要记一个次大值

• (n leq m)

直接暴力枚举 (u) , (d) , 前缀和查询这一段是否全是 0

复杂度 (O(n^2 * m))

• (n > m)

悬线法求出每个点最上面的 1 , 设为 (up[i][j])

对于每一个 0 点, 拿 ([up[i][j] - 1, i]) 这一段区间去更新答案

复杂度 (O(nm * m))

感觉对这种根号分治的题目了解的还不是很多啊

Code

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
const int N = 100005; 
using namespace std;

int n, m, w[N], s, l[N], r[N], a[N], sum[N], ans, up[N], T; 

template < typename T >
inline T read()
{
    T x = 0, w = 1; char c = getchar();
    while(c < '0' || c > '9') { if(c == '-') w = -1; c = getchar(); }
    while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
    return x * w; 
}

int id(int i, int j) { if(i < 1 || j < 1) return 0; return (j - 1) * n + i; }

int S(int u, int l, int d, int r) { return sum[id(d, r)] - sum[id(d, l - 1)] - sum[id(u - 1, r)] + sum[id(u - 1, l - 1)]; }

void calc(int u, int d)
{
    for(int i = 1; i <= s; i++)
	for(int j = l[i], len = 0; j <= r[i]; j++)
	{
	    S(u, j, d, j) ? len = 0 : len++; 
	    ans = max(ans, (d - u + 1) * len); 
	}
    int tmp = 0; pair<int, int> lmx, rmx, lsmx, rsmx; 
    for(int i = 1; i <= s; i++)
    {
	int x = 0, y = 0; 
	for(int j = l[i]; j <= r[i]; j++)
	{
	    if(!S(u, j, d, j)) x++;
	    else break; 
	}
	for(int j = r[i]; j >= l[i]; j--)
	{
	    if(!S(u, j, d, j)) y++;
	    else break; 
	}
	if(x == w[i]) tmp += w[i]; 
	else
	{
	    if(x > lmx.second) lsmx = lmx, lmx.second = x, lmx.first = i;
	    else if(x > lsmx.second) lsmx.second = x, lsmx.first = i;
	    if(y > rmx.second) rsmx = rmx, rmx.second = y, rmx.first = i;
	    else if(y > rsmx.second) rsmx.second = y, rsmx.first = i; 
	}
    }
    if(lmx.first != rmx.first)
	ans = max(ans, (d - u + 1) * (tmp + lmx.second + rmx.second));
    else
    {
	ans = max(ans, (d - u + 1) * (tmp + lmx.second));
	ans = max(ans, (d - u + 1) * (tmp + rmx.second)); 
	ans = max(ans, (d - u + 1) * (tmp + lmx.second + rsmx.second));
	ans = max(ans, (d - u + 1) * (tmp + rmx.second + lsmx.second)); 
    }
}

int main()
{
    T = read <int> ();
    while(T--)
    {
	s = read <int> (), n = read <int> (), ans = m = 0; 
	for(int i = 1; i <= s; i++)
	{
	    w[i] = read <int> (), l[i] = m + 1, m += w[i], r[i] = m;
	    for(int j = 1; j <= n; j++)
		for(int k = l[i]; k <= r[i]; k++)
		    scanf("%1d", &a[id(j, k)]); 
	}
	for(int i = 1; i <= n; i++)
	    for(int j = 1; j <= m; j++)
		sum[id(i, j)] = sum[id(i - 1, j)] + sum[id(i, j - 1)] - sum[id(i - 1, j - 1)] + a[id(i, j)];
	for(int j = 1; j <= m; j++)
	    for(int i = 1; i <= n; i++)
	    {
		if(a[id(i, j)]) up[id(i, j)] = i;
		else up[id(i, j)] = up[id(i - 1, j)]; 
	    }
	if(n < m)
	{
	    for(int i = 1; i <= n; i++)
		for(int j = i; j <= n; j++) calc(i, j);
	}
	else
	{
	    for(int i = 1; i <= n; i++)
		for(int j = 1; j <= m; j++)
		    if(!a[id(i, j)]) calc(up[id(i, j)] + 1, i);
	}
	printf("%d
", ans); 
    }
    return 0; 
}