F. Alice and Recoloring 1&2

题意：给定一个 n * m 的 0 1 矩阵，你需要使用以下四种操作使得个矩阵全为 0 ，求出最小的代价。

代价为 1 的第一种操作：反转矩阵的某个左上子矩阵。
代价为 2 的第二种操作：反转矩阵的某个左下子矩阵。
代价为 4 的第三种操作：反转矩阵的某个右上子矩阵。
代价为 3 的第四种操作：反转矩阵的某个右下子矩阵。

分析：

首先需要发现第二种和第三种操作是可以被第一种操作替代的，且代价不会更高。
将原先的矩阵做差分。原先对关于（x，y）的子矩阵的操作，对于差分后的矩阵，第一种操作等价于反转（x，y）一个单元，第四种操作相当于反转（x-1，y-1），（x-1，m），（n，y-1），（n，m）这四个单元。
考虑第四种操作什么时候是有意义的，显现需要这个操作使得四个单元都由 0 变成 1 。又由于它们都是关于（n，m）的，所以该操作最多执行一次。

#include<bits/stdc++.h>
#define ll long long
#define ls u<<1
#define rs u<<1|1
#define mm(x) memset(x,0,sizeof(x))
#define debug(x) cout << #x << ":" << x << '
'
using namespace std;
int read()
{
    int a=0;int f=0;char p=getchar();
    while(!isdigit(p)){f|=p=='-';p=getchar();}
    while(isdigit(p)){a=(a<<3)+(a<<1)+(p^48);p=getchar();}
    return f?-a:a;
}
const int INF=998244353;
int T;
int n,m;
int ans;
char s[550][550];
bool val[550][550];
int main()
{
    n=read();    m=read();
    for(int i=1;i<=n;++i)    scanf("%s",s[i]+1);
    for(int i=1;i<=n;++i)
        for(int j=1;j<=m;++j)
            val[i][j]=s[i][j]=='B';
    for(int i=1;i<=n;++i)
        for(int j=1;j<=m;++j)
            val[i][j]^=val[i+1][j]^val[i][j+1]^val[i+1][j+1];
    ans=val[n][m];
    for(int i=1;i<=n;++i)
        for(int j=1;j<=m;++j)
        {
            if(i==n&&j==m)    continue;
            if(val[i][j])
            {
                ans++;
                if(i==n)    continue;
                if(j==m)    continue;
                if(val[i][m]&&val[n][j]&&val[n][m])
                {
                    ans--;
                    val[n][m]=false;
                }
            }
        }
    printf("%d",ans);
    return 0;
}

View Code

题意：给定一个 n * m 的 0 1 矩阵，你需要使用以下四种操作使得个矩阵全为 0 ，求出最小的代价。

分析：相比于前一题，第四种操作的代价变小了。造成的结果是，第四种操作能执行多次。

#include<bits/stdc++.h> #define ll long long #define ls u<<1 #define rs u<<1|1 #define mm(x) memset(x,0,sizeof(x)) #define debug(x) cout << #x << ":" << x << ' ' using namespace std; int read() { int a=0;int f=0;char p=getchar(); while(!isdigit(p)){f|=p=='-';p=getchar();} while(isdigit(p)){a=(a<<3)+(a<<1)+(p^48);p=getchar();} return f?-a:a; } const int INF=998244353; int T; int n,m; int ans,tot; char s[550][550]; bool val[550][550]; bool link[550][550]; int mat[550]; int vis[550]; bool dfs(int u,int t) { for(int i=1;i<=m;++i) { if(link[u][i]&&vis[i]!=t) { vis[i]=t; if(!mat[i]||dfs(mat[i],t)) { mat[i]=u; return true; } } } return false; } int main() { n=read(); m=read(); for(int i=1;i<=n;++i) scanf("%s",s[i]+1); for(int i=1;i<=n;++i) for(int j=1;j<=m;++j) val[i][j]=s[i][j]=='B'; for(int i=1;i<=n;++i) for(int j=1;j<=m;++j) { val[i][j]^=val[i+1][j]^val[i][j+1]^val[i+1][j+1]; ans+=val[i][j]; } for(int i=1;i<n;++i) for(int j=1;j<m;++j) if(val[i][j]&&val[i][m]&&val[n][j]) link[i][j]=true; for(int i=1;i<=n;++i) if(dfs(i,i)) ++tot; ans-=val[n][m]; ans-=tot; if((tot^val[n][m])&1) ans++; printf("%d",ans); return 0; }

F. Alice and Recoloring 1&2

相关推荐