题解 P4039 【[AHOI2014/JSOI2014]拼图】
龙之吻—水货
2019-03-25 14:26:49
# [AHOI2014/JSOI2014]拼图
## 题目链接
### [[AHOI2014/JSOI2014]拼图](https://www.luogu.org/problemnew/show/P4039)
## 解题报告
网上的题解都是根号分治，但是这里考虑一种$log$的做法。
首先感谢@[独秀平川](https://www.luogu.org/space/show?uid=53153)神仙告诉了我这个神奇的解法。
简单思考，可以发现，最优情况只有两种，一种是在一块拼图内部选取一个举行，一种是多个拼图联通起来，具体来说就是这个样子 :
当然，可能会没有左区间或者右区间。
暂时不考虑第一种情况。
对于第二种情况，我们先预处理出每个格子，最多可以向上延伸多少(如果这个格子上的数字为 $1$ 那么是不可延伸的)，只需要从上到下扫一遍即可。
之后，我们从下往上枚举所求矩形的下边界，寻找最优解。
考虑已知下边界如何求出最优解，显然，对于每一块拼图，情况都应该是这样子的：
其中蓝色的表示从当前下边界最多可以往上延伸的部分。
尝试从上到下枚举高度，由于在离散化之后，高度最多有 $M$ 种，而 $n \times M \leq 10^5$，所以到现在时间复杂度都还是在可接受的范围内。
每枚举到一个高度，都需要求出每一块拼图从左边向内可以延伸多少，从右边向内可以延伸多少(特别地，如果可以延伸的长度等于该块拼图的长度，说明这一块拼图被打通了，可以作为中间的块)。
只要维护了这些东西，我们找出从左边延伸最多的拼图，从右边延伸最多的拼图，以及所有被打通了的拼图，将它们组合在一起就可以得到当前高度的最优解。
由于 从左边延伸最多的拼图 和 从右边延伸最多的拼图 可能是同一个拼图，所以我们可能会同时需要最大值和次大值。同时，当一个拼图被打通之后，需要将它对最大值和次大值的贡献删去。于是选择使用两个 $set$ 分别来存储没被打通的拼图。
至于如何在枚举高度之后快速求出所需要的值，只需要两个指针就可以了。但是为了顺便解决最优情况在一块拼图内部的情况，选择使用并查集。
对于每一块拼图，我们把每一列当作一个单独的点，将这个点可以向上延伸距离称为这个点的高度，由于是从上往下枚举高度，所以相邻的两点之间只可能是在不断地合并，每枚举到一个高度 $h$，我们就只需要将所有高度为 $h$ 的点和它相邻且高度为 $h$ 的点合并即可。如果当前点所在联通块的大小为这块拼图的宽度，说明当前拼图被打通了。
同时，当前点所在联通块的大小与当前枚举到的高度 $h$ 相乘，并用结果更新 $ans$ 就可以涵盖所有最优解在一块拼图的情况了。这个简单想一下就明白了吧？
附上Code。。。
```cpp
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<string>
#include<deque>
#include<queue>
#include<set>
class Solution{
private :
typedef std::pair<int, int> par;
static const int maxn = 1e5 + 7;
struct Block{
int len, **h;
int *fa, *size;
bool *open;
std::string *str;
inline int *operator [](int x) const {
return this->h[x];
}
int find(int k) {
return fa[k] == k ? k : fa[k] = find(fa[k]);
}
int findSize(int k) {
return size[find(k)];
}
void merge(int x, int y) {
if (!open[x] || !open[y]) {
return;
}
x = find(x), y = find(y);
if (x == y) {
return;
}
fa[y] = x;
size[x] += size[y];
}
};
int t, s, n, ans;
Block b[maxn];
std::deque<par> dq;
std::priority_queue<std::pair<int, par> > pq;
std::set<par, std::greater<par> > left, right;
template<typename T>
T next(T x) {
++x;
return x;
}
template<typename T>
T prev(T x) {
--x;
return x;
}
void make(const Block &b) {
for (register int i = 1; i <= n; i++) {
for (register int j = 1; j <= b.len; j++) {
bool now = b.str[i][j - 1] - '0';
if (now) {
b[i][j] = 0;
} else {
b[i][j] = b[i - 1][j] + 1;
}
//printf("%d ", b[i][j]);
}
//putchar('\n');
}
//putchar('\n');
}
int deal(int flor) {
int res = 0;
//printf("floor = %d : \n", flor);
for (register int i = 1; i <= s; i++) {
left.insert(std::make_pair(0, i));
right.insert(std::make_pair(0, i));
memset(b[i].open, 0, b[i].len + 2);
b[i].fa[0] = 0, b[i].size[0] = 0, b[i].open[0] = 1;
b[i].fa[b[i].len + 1] = b[i].len + 1, b[i].size[b[i].len + 1] = 0, b[i].open[b[i].len + 1] = 1;
for (register int j = 1; j <= b[i].len; j++) {
b[i].fa[j] = j, b[i].size[j] = 1;
pq.push(std::make_pair(b[i][flor][j], std::make_pair(i, j)));
}
}
int mid = 0;
//fprintf(stderr, "%d\n", flor);
while (!pq.empty()) {
int height = pq.top().first, id = pq.top().second.first, pos = pq.top().second.second;
pq.pop();
int leftLen = b[id].findSize(0), rightLen = b[id].findSize(b[id].len + 1);
b[id].open[pos] = 1;
b[id].merge(pos, pos - 1);
b[id].merge(pos, pos + 1);
ans = std::max(ans, b[id].findSize(pos) * height);
//printf("%d %d : %d %d\n", id, pos, b[id].findSize(pos), height);
left.erase(std::make_pair(leftLen, id));
right.erase(std::make_pair(rightLen, id));
if (b[id].findSize(0) == b[id].len) {
//puts("233");
mid += b[id].findSize(0);
} else {
left.insert(std::make_pair(b[id].findSize(0), id));
right.insert(std::make_pair(b[id].findSize(b[id].len + 1), id));
}
//printf("%d %d : %d\n", flor, height, mid);
int sum = mid * height;
res = std::max(res, sum);
if (!left.empty()) {
par l = *left.begin();
//printf(":: %d\n", l.first);
res = std::max(res, sum + l.first * height);
if (!right.empty()) {
par r = *right.begin();
if (l.second == r.second) {
if (right.size() > 1u) {
r = *next(right.begin());
res = std::max(res, sum + (l.first + r.first) * height);
}
if (left.size() > 1u) {
l = *next(left.begin());
res = std::max(res, sum + (l.first + r.first) * height);
}
} else {
res = std::max(res, sum + (l.first + r.first) * height);
}
}
} else {
if (!right.empty()) {
par r = *right.begin();
res = std::max(res, sum + r.first * height);
}
}
//par leftFirst = *left.begin();
}
//printf("%d %d\n", flor, res);
return res;
}
public :
Solution() {
scanf("%d", &t);
while (t--) {
get();
solve();
}
}
void get() {
scanf("%d %d", &s, &n);
for (register int i = 1; i <= s; i++) {
scanf("%d", &b[i].len);
b[i].h = new int*[n + 1];
b[i].fa = new int[b[i].len + 2];
b[i].size = new int[b[i].len + 2];
b[i].open = new bool[b[i].len + 2];
b[i].str = new std::string[n + 1];
b[i].h[0] = new int[b[i].len + 1];
memset(b[i].h[0], 0, (b[i].len + 1) << 2);
for (register int j = 1; j <= n; j++) {
std::cin >> b[i].str[j];
b[i].h[j] = new int[b[i].len + 1];
memset(b[i].h[j], 0, (b[i].len + 1) << 2);
}
}
}
void solve() {
//make(b[1]);
//ans = getAns(b[1]);
ans = 0;
for (register int i = 1; i <= s; i++) {
make(b[i]);
//ans = std::max(ans, getAns(b[i]));
}
for (register int i = 1; i <= n; i++) {
ans = std::max(ans, deal(i));
}
printf("%d\n", ans);
}
};
Solution sol;
int main() {}
```