【题解】cf 1592 f-爱丽丝和重新着色
很神的思维题。
观察以下发现对于矩阵取反非常不好做。
这时候我们可以联想到差分，将它转化为单点取反。
所以我们构造广义差分数组\(a_{i，j}=s_{i，j}\oplus s_{i 1，j}\oplus s_{i，j 1}\oplus s_{i 1，j 1}\)。原矩阵\(s\)全\(0\) 等价于矩阵\(a\)全\(0\)。
手算以下发现\(1,2,3\) 操作对应单点取反，\(4\) 操作对应\(4\) 个点取反。
所以对于\(F1\)题，\(4\) 操作最多只会进行一次，枚举以下即可。
对于\(F2\)题，一个位置除了\((n，m)\)只会翻转一次，且尽量先用\(4\) 操作，所以直接套二分图模型即可。
#定义编号505
整数N，m，a[N][N]，u[N][N]；字符s[N]；
int main(){ 0
//int T=read()；while(T-)solve()；
n=read()，m=read()；
代表(I，1，n){ 0
scanf(“% s “，S1)；
rep(j，1，m)a[I][j]=s[j]==’ B ‘；
}
int ans=0；
rep(i，1，n)rep(j，1，m)ans=(u[I][j]=a[i][j]^ a[I 1][j]^ a[I][j 1]^ a[I 1][j 1])；
if(u[n][m])
rep(i，1，n – 1)rep(j，1，m – 1)if(u[i][j] u[n][j] u[i][m])
printf(‘%d\n ‘，ans-1)；返回0;
}
printf(‘%d\n ‘，ans)；
返回0;
}
#定义编号505
int n，m，u[N][N]，a[N][N]，s，t；字符w[N]；
int h[N 1]，tot=1，d[N 1]，cur[n1]；
结构边{int to，nxt，cap } e[N * N * 4]；
void add(int x，int y，int z){ 0
总收入.nxt=h[x]，h[x]=tot，e[tot].to=y，e[tot].cap=z；
总收入.nxt=h[y]，h[y]=tot，e[tot].to=x，e[tot].cap=0；
}
queueintq
bool bfs(){ 0
memset(d，0，sizeof(d))；
d[s]=1，q . push(s)；
while(！q . empty()){ 0
int x=q . front()；q . pop()；cur[x]=h[x]；
for(int I=h[x]；我；i=e[i]。nxt)if(e[i].船长！d[e[i].to])
d[e[i].to]=d[x] 1，q.push(e[i]).到);
}
返回d[t]1 : 0；
}
int dfs(int x，int flow){ 0
if(t==x)回流；
int res=flow
for(int I=cur[x]；我；i=e[i]。nxt) if(e[i].cap d[x] 1==d[e[i].to](
int now=dfs(e[i]).to，min(res，e[i]).cap))；
if(！现在d[e[I]].to]=0；
否则。现在，^ 1号cap=now，RES-=now；
if(！res)回流；
}
回流；
}
int main(){ 0
//int T=read()；while(T-)solve()；
n=read()，m=read()；
代表(I，1，n){ 0
scanf(“% s “，w1)；
rep(j，1，m)a[I][j]=w[j]==’ B ‘；
}
int ans=0；
rep(i，1，n)rep(j，1，m)ans=(u[I][j]=a[i][j]^ a[I 1][j]^ a[I][j 1]^ a[I 1][j 1])；
rep(i，1，n – 1)rep(j，1，m – 1)if(u[i][j])add(i，j n – 1，1)；
s=n m – 1，t=S1；
rep(i，1，n – 1)if(u[i][m])add(s，I，1)；
rep(i，1，m – 1)if(u[n][i])add(i n – 1，t，1)；
int sum=0；
while(bfs())sum=dfs(s，n ^ m)；
if(sum)printf(‘%d\n ‘，ans-sum((sum 1)^ u[n][m])-u[n][m])；
else printf(‘%d\n ‘，ans)；
返回0;
}
内容来源网络，如有侵权，联系删除，本文地址：https://www.230890.com/zhan/74747.html