Codeforces 1581 C. Portal(前缀和)

传送门

题意：

给出一个 n × m n times m n×m 的 01 01 01 矩阵，一次操作可以反转某个单元格的值。求最少需要多少次操作，才能使得矩阵中存在一个子矩阵，满足矩阵中间的值都为 0 0 0,矩阵边界的值都为 1 1 1,四个顶点可以不用考虑，且子矩阵的长要 ≥ 5 geq 5 ≥5,宽 ≥ 4 geq 4 ≥4。

题解：

枚举左上角顶点的行，再枚举左下角顶点的行，再枚举列，那么此时就确定了一条竖线。

设 c n t 1 cnt1 cnt1该竖线为子矩阵边界所需要的操作数， c n t 2 cnt2 cnt2 为该竖线为子矩阵中间的列的操作数。

假设当前列为 k k k ,设 s u m [ i ] sum[i] sum[i]表示前 i i i列的 c n t 2 cnt2 cnt2的和。

那么如果我们以当前第 k k k列为子矩阵的右边界，那么我们就需要找一个最大的 s u m [ i ] − c n t 1 sum[i]-cnt1 sum[i]−cnt1 ,满足 s u m [ k − 1 ] − s u m [ i ] + c n t 1 sum[k-1]-sum[i]+cnt1 sum[k−1]−sum[i]+cnt1 最小，因为这样表示中间所用的操作数是最少的。

代码：

#pragma GCC diagnostic error "-std=c++11"
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define iss ios::sync_with_stdio(false)
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
typedef pair pii;
const int mod=1e9+7;
const int MAXN=4e2+5;
const int inf=0x3f3f3f3f;
char s[MAXN][MAXN];
int b[MAXN][MAXN],a[MAXN][MAXN];
int pre[MAXN];
void work()
{
    int n, m;
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n;i++){
        for (int j = 1; j <= m;j++){
            cin >> s[i][j];
            int id = s[i][j] - '0';
            a[i][j] = id;
            b[i][j] = b[i - 1][j] + id;
        }
    }
    int ans = 1e9;
    for (int i = 1; i <= n;i++){
        for (int j = i+4; j <= n;j++){
            int sum = 0;
            pre[0] = -1e9;
            for (int k = 1; k <= m;k++){
                int p1 = b[j - 1][k] - b[i][k];
                int p0 = 2 - a[j][k] - a[i][k];
                int r = j - i - 1 - p1;
                if(k>=4){
                    ans = min(ans, r + sum - pre[k - 3]);
                }
                sum += p1 + p0;
                pre[k] = max(pre[k - 1], sum - r);
            }
        }
    }
    cout << ans << endl;
}
int main()
{
    int t;
    cin >> t;
    for (int i = 1; i <= t;i++)
        work();
}

Codeforces 1581 C. Portal(前缀和)

C/C++/C#相关栏目本月热门文章