首页 > 其他分享 >CF1592F2 题解

CF1592F2 题解

时间:2023-04-15 11:13:01浏览次数:51  
标签:题解 元素 矩阵 取反 CF1592F2 操作 operatorname op

题意

传送门

给定一个 \(n\) 行 \(m\) 列的目标矩阵,矩阵元素只有 W 或 B ,并且你有一个初始矩阵,元素全为 W 。

现在你可以矩阵实施以下操作:

使用一块钱,选定一个包含 \((1,1)\) 的子矩阵,把矩阵中的元素全部反转( W 变 B , B 变 W )。

使用三块钱,选定一个包含 \((n,1)\) 的子矩阵,把矩阵中的元素全部反转。

使用四块钱,选定一个包含 \((1,m)\) 的子矩阵,把矩阵中的元素全部反转。

使用两块钱,选定一个包含 \((n,m)\) 的子矩阵,把矩阵中的元素全部反转。

现在需要你求出把初始矩阵变为目标矩阵最少需要几块钱。

\(1\le n,m\le 500\)。

题解

首先 \(2,3\) 操作是无用的,只需考虑 \(1,4\) 操作。

整个矩阵取反很难搞,做个简单的变形:\(s_{i,j}=a_{i,j}\oplus a_{i,j+1}\oplus a_{i+1,j}\oplus a_{i+1,j+1}\),则操作 \(1\) 是单点取反,操作 \(4\) 是同时取反 \((x,y),(x,m),(n,y),(n,m)\)。倒着考虑,目标态是全为 \(0\)。称操作 \(4\) 为 \(\operatorname{op}(x,y)\)。

接下来是两个重要结论:

  • \(\operatorname{op}(x,y)\) 的必要条件是 \(s_{x,y}=s_{x,m}=s_{n,y}=1\)。因为如果不是,操作后至少还需要 \(1\) 的代价使这三位都归零。不如直接三次操作 \(1\)。
  • 不存在 \(\operatorname{op}(x_1,y_1),\operatorname{op}(x_2,y_2)\),有 \(x_1=x_2\) 或 \(y_1=y_2\)。因为如果存在,不妨设为 \(y_1=y_2\),则 \((n,y_1),(n,m)\) 两位是不动的,另外 \(4\) 位直接操作 \(1\) 即可。

第二个结论提供了很好的二分图模型。再稍加推导,易知答案为 \(rem-k\),其中 \(rem\) 为 矩阵变换后 \(1\) 的数目,\(k\) 为最大匹配。\((n,m)\) 处需特殊判断。

标签:题解,元素,矩阵,取反,CF1592F2,操作,operatorname,op
From: https://www.cnblogs.com/fish07/p/17320700.html

相关文章

  • Luogu_P1613 跑路 题解
    发现和最短路差不多,不过不能朴素的跑最短路。考虑对于每两个相隔\(2\)的整数次幂的点建边,在这个新图上跑最短路就是答案。设\(f_{i,j,k}\)表示从点\(i\)跳\(2^k\)步能否到点\(j\),转移方程就是一个普通的倍增。如果点\(i\)和点\(j\)可以一步到达,那么就在新图上建一条......
  • ABC249F 题解
    前言题目传送门!更好的阅读体验?很好玩的贪心。思路如果第\(i\)次操作为覆盖操作,那么\(1\simi-1\)次操作都是无效的,原因显然。这启示我们从后往前扫(前面的会被忽略,后面的不会啊!)。在此基础上,就是分类讨论一下(假设当前的最大答案为\(sum\)):当前操作是覆盖操作:如果不......
  • 【题解】Tree MST
    题面给定一棵\(n\)个节点的树,现有有一张完全图,两点\(x,y\)之间的边长为\(w_x+w_y+dis_{x,y}\),其中\(dis\)表示树上两点的距离。求完全图的最小生成树。\(n\leq2\times10^5\)。题解???神秘借鉴支配对的思想,点分治后将树中点权替换为\(dep_i+w_i\),选择点权最小的一个......
  • [ABC296Ex] Unite 题解
    考虑状压dp。设\(f_{i,j,s}\)表示当前正在决策坐标为\((i,j)\)的格子,且列状态为\(s\)。其中列状态维护了当前轮廓线上的连通块,我们可以使用最小表示法来简单维护。(为什么不用广义括号序列?因为其涉及到\(5\)个可选值,由于\(m\le7\),所以这两个都需要用到八进制,而最小表示......
  • [Educational Codeforces Round 118 (Rated for Div. 2)]题解
    A题意:给定两个数,每一个数有两个属性,第一个属性是p1,第二个属性是p2.表示这个数有p2个后缀0.这个数本身等于p1后面加p2个0.问给你两个这种数,判断大小。思路:赛场上想到的:如果最终的长度不一样,可以直接根据长度判断。如果相等,就把后缀0加上直接比较大小就可以(比较字典序的大小),但......
  • 2012-2013 ACM-ICPC, NEERC, Moscow Subregional Contest题解
    题目链接:2012-2013ACM-ICPC,NEERC,MoscowSubregionalContestC.Cinderella(贪心)思路答案为大于平均值的数的数量代码#include<bits/stdc++.h>usingnamespacestd;usingi64=longlong;intmain(){ios::sync_with_stdio(false);cin.tie(nullptr);......
  • CF1473D 题解
    题目传送门题目分析线段树、前缀和、\(\text{ST}\)表题解都有了,我补一发猫树题解吧。由于每次操作只能将大小改变成跟原来差\(1\),所以只需要知道这段操作中的最大值和最小值,最后所求的答案的范围就被卡住了。对于每一次操作,我们把操作序列拦腰斩断,那么分别求两边的范围,最后减......
  • CF1758D 题解
    前言题目传送门!更好的阅读体验?用一种非常麻烦的做法把自己写自闭了,和题解区不一样,但是方法困难很多。思路代码属于混乱邪恶了,凑合着看看。#include<iostream>#include<cstdio>#include<cmath>usingnamespacestd;intn,ans[300005];longlongcalc(){ longlo......
  • ubuntu 20.04 基于docker快速搭建中文 的一些问题解决 Utilization of discoverer pro
    1.Utilizationofdiscovererprocessesover75%解决办法问题状态如下zabbixserver在开启Discovery功能后,zabbixweb页面报警提示:“Zabbixserver:Ulitizationofdiscovererprocessesover75%”。原因:每个discovery任务占用一个discovery进程,但是zabbixserver默认只配置了一......
  • scikit-learn 中 Boston Housing 数据集问题解决方案
    scikit-learn中BostonHousing数据集问题解决方案在部分旧教程或教材中是sklearn,现在【2023】已经变更为scikit-learn作用:开源机器学习库,支持有监督和无监督学习。它还提供了用于模型拟合、数据预处理、模型选择、模型评估和许多其他实用程序的各种工具。安装pipinsta......