QOJ 1283 Petrozavodsk Summer 2020. Day 4. Xi Lin Contest 6 题解

· · 个人记录

题意

给一个 n\times m (n\times m \le 10^6)的矩阵，元素皆为 0 或者 1。可以进行任意次（可以不做）如下操作：

以行为例，假设 \exists i\in [2,n-1],\forall k \in [1,\min(i,n-i)],l\in [1,m],a_{k,l}=a_{2i+1-k,l}，那么可以选择 [1,i]\times [1,m] 和 [i+1,n]\times [1,m] 中较大的一份，列同理。

形象化的，若一个矩形能沿一行或一列对折，那么可以选择保留其中较大的一部分。

求进行任意次如上操作，矩形内包含的 0 的连通块的最小个数，并输出最小个数。

题解

首先暴力模拟这个操作大概率是不行的。那么我们考虑寻找操作的一个性质。

观察到这是裁剪一个类似回文串的过程，手摸一下图会发现，对于任意一个行的操作和列的操作，他们之间的操作顺序（不改变行的相对顺序和列的相对顺序）不会对裁剪出来的矩形进行改变。

假设先操作行再操作列，若操作可行的话由回文串可以推出行被裁掉的部分也相等，也就是说先操作行并没有为后面的过程提供有利的条件。

那么我们可以把行和列的操作分开考虑。

于是我们大胆推了一下，发现：存在一种方案到达一个最终矩形 [l,r]\times [u,d] 的充要条件是 [1,l]\times [1,m],[r+1,n]\times [1,m],[1,n]\times [1,d],[1,n]\times [u+1,m] 均可以单独被操作减掉。

那么我们把问题分成两部分，先来解决第一部分：怎么判断一个矩形 [1,i]\times [1,m] 是否能被裁掉。注意到列并没有被操作过，那么我们可以用列把 hash 压成一个元素跑 manacher。之后从左往右模拟裁剪过程即可。注意到贪心一定是对的，因为对于一个 [l,r] 的回文串，我们肯定是希望之前的裁剪点 \ge l,这样就能直接接上去。那么显然裁剪点越往右越好。

那么怎么判断矩形内的连通块个数呢？

那么一个比较 \color{red}{na}\color{black}{i}\color{red}ve 的想法就是枚举 l,r 用预处理判断出 u,d 的最小取值。我们发现若一个连通块与裁剪的中点相连，那么他在裁剪过后依然是一个连通块。否则不改变连通性。即原本联通的连通块仍然联通，那么我们可以看成这样一个问题：所有在原矩阵中的连通块与新矩阵是否有交。这个怎么判？

注意到回文串的性质，我们用一个最小的矩形框柱这个连通块，若列操作或者行操作没有经过矩形，那么我们发现如果有与他对称的矩形，那么肯定是他更靠近中间矩形，即保留的肯定是他。否则由于边界上都至少有一个点，那么肯定存在路径 l \to r,u \to d，即若一条折线穿过矩形，那么也一定穿过连通块。注意到对折之后连通块仍然联通，那么对折之后的点肯定也属于矩形内。容易发现折到最后形成的询问矩形中至少含有一个点，那么这个点本来存在或者由对折产生。因为对折不改变连通性，所以这个点包含在原来的矩形内，即联通块与询问 矩形有交。

那么这就是一个经典问题：对于每个矩形，求有多少个矩形和他有交。容斥数据结构维护即可。复杂度 O(nm\log nm)

但是，容易发现 l 的取值只和 l 有关。即 l,r,d,u 除了 l\le r,d\le u 之外互不相关。贪心取最大的 l,d 和最小的 r,u 再暴力判断即可。复杂度 O(nm)。

#include<bits/stdc++.h>
#define ull unsigned long long 
using namespace std;
const int N=1e6+100;
int n,m;
ull h1[N],h2[N];
int c[N];
vector<int>vis[N];
string s[N];
int chk(int l,int mid){return mid-c[mid]+1<=l;}
void manacher(ull *s,int n,int &l,int &r)
{
    int R=0,mid=0;s[n+1]=123848755314ull;
    for(int i=1;i<=n;i++)
    {
        c[i]=i>R?0:min(R-i,c[2*mid-i]);
        while(i-c[i]>0&&s[i-c[i]]==s[i+c[i]+1])c[i]++;
        if(i+c[i]>R)R=i+c[i],mid=i;
    }
    l=1;for(int i=1;i+i-l<n;i++)if(chk(l,i))l=i+1;
    r=n;for(int i=n-1;i-(r-i-1)>=l;i--)if(chk(i-(r-i-1),i))r=i;
}
int l1,l2,r1,r2;
const int dx[]={1,-1,0,0},dy[]={0,0,1,-1};
void dfs(int x,int y)
{
    vis[x][y]=1;
    for(int i=0;i<4;i++)
    {
        int tx=x+dx[i],ty=y+dy[i];
        if(tx>=l1&&ty>=l2&&tx<=r1&&ty<=r2&&s[tx-1][ty-1]=='0'&&!vis[tx][ty])dfs(tx,ty);
    }
}
void solve()
{
    cin>>n>>m;
    for(int i=0;i<n;i++)cin>>s[i];
    for(int i=1;i<=max(n,m)+1;i++)h1[i]=h2[i]=0;
    for(int i=1;i<=n;i++)vis[i].resize(m+1);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            h1[i]=h1[i]*2+(s[i-1][j-1]=='0'),
            h2[j]=h2[j]*2+(s[i-1][j-1]=='0'),
            vis[i][j]=0;
    manacher(h1,n,l1,r1),manacher(h2,m,l2,r2);
    int ans=0;
    for(int i=l1;i<=r1;i++)
        for(int j=l2;j<=r2;j++)
            if(!vis[i][j]&&s[i-1][j-1]=='0')dfs(i,j),ans++;
    cout<<ans<<endl;
}
signed main()
{
    ios::sync_with_stdio(0);
    int _;cin>>_;
    while(_--)solve();
    return 0;
}