[CF1592F2] Alice and Recoloring 2

news/2024/4/19 21:24:10/

题目链接

操作 2 和 3 可以用另两个代替,没有任何用。

W 表示 \(t_{i,j}=0\),B 表示 \(t_{i,j}=1\)

考虑差分。设 \(t_{i,j}=s_{i,j}\oplus s_{i+1,j}\oplus s_{i,j+1}\oplus s_{i+1,j+1}\),那么目标变为把 $t4 数组清0

那么操作 1 是把单点翻转,操作 4 是对于一个 \(x,y(x<n,y<m)\),翻转 \((n,m),(x,y),(x,m),(n,y)\)

那么操作4有用当且仅当 \(t_{x,y},t_{x,m},t_{n,y}\) 都为 1。

然后每个 \(x\)\(y\) 只能用一次,所以可以跑一个二分图匹配。
判断一下 \((n,m)\) 要不要操作。

// LUOGU_RID: 139138753
#include<bits/stdc++.h>
using namespace std;
const int N=505;
int n,m,t[N][N],ans,v[N],p[N],s[N][N],g[N][N];
char str[N];
int dfs(int x,int y)
{for(int i=1;i<m;i++){if(g[x][i]&&v[i]^y){v[i]=y;if(!p[i]||dfs(p[i],y))return p[i]=x,1;}}return 0;
}
int main()
{scanf("%d%d",&n,&m);for(int i=1;i<=n;i++){scanf("%s",str+1);for(int j=1;j<=m;j++)t[i][j]=str[j]=='B';}for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)s[i][j]=t[i][j]^t[i+1][j]^t[i+1][j+1]^t[i][j+1],ans+=s[i][j];for(int i=1;i<n;i++)for(int j=1;j<m;j++)g[i][j]=s[n][j]&&s[i][m]&&s[i][j];int c=0;for(int i=1,k;i<=n;i++)k=dfs(i,i),ans-=k,c+=k;ans-=s[n][m];if(c&1^s[n][m])ans++;printf("%d\n",ans);
}

http://www.ppmy.cn/news/1266636.html

相关文章

Vue学习笔记-Vue3中setup函数注意点

setup编写示例 <script> import {reactive} from vue export default {name: "DemoVue",props:[xxx,yy,...],setup(props,context){const data reactive({......})//setup必须有返回值return {data,}} } </script>setup执行的时机 在beforeCreate()之…

西工大网络空间安全学院计算机系统基础实验二(phase_2下——漫漫深夜过后的黎明!!!)

内存地址内存地址中的数注释指向这块内存的寄存器0xffffd0e8函数phase_2的栈帧0xffffd0e40xffffd0f4函数phase_2的栈帧0xffffd0e00x5655b7b0函数phase_2的栈帧0xffffd0dc0x565566ca函数read_six_numbers的返回地址&#xff0c;函数phase_2的栈帧0xffffd0d80x5655af64旧%ebx的值…

友元c++

#include <iostream> #include <string> using namespace std; class Lovers//爱人关系,基类 { public: Lovers(string theName);// void kiss(Lovers *lover); void ask(Lovers *lover, string something); protected: string name; friend cla…

Python:核心知识点整理大全8-笔记

目录 ​编辑 4.5 元组 4.5.1 定义元组 dimensions.py 4.5.2 遍历元组中的所有值 4.5.3 修改元组变量 4.6 设置代码格式 4.6.1 格式设置指南 4.6.2 缩进 4.6.3 行长 4.6.4 空行 4.6.5 其他格式设置指南 4.7 小结 第5章 if语句 5.1 一个简单示例 cars.py 5.2 条…

计算机网络:应用层(一)

我最近开了几个专栏&#xff0c;诚信互三&#xff01; > |||《算法专栏》&#xff1a;&#xff1a;刷题教程来自网站《代码随想录》。||| > |||《C专栏》&#xff1a;&#xff1a;记录我学习C的经历&#xff0c;看完你一定会有收获。||| > |||《Linux专栏》&#xff1…

算法通关村——计算器问题解析

计算器问题 问题描述 LeetCode227. 给你一个字符串表达式s&#xff0c;请你实现一个基本计算器来计算并返回它的值。整数除法仅保留整数部分。你可以假设给定的表达式总是有效的。所有中间结果将在[-231,231-1]的范围内。 注意&#xff1a;不允许使用任何将字符串作为数学表…

多线程(Thread)

一、实现多线程 多线程是为了同步完成多项任务&#xff0c;提高资源使用率提高系统使用率。 1、继承Thread类 void run()在线程开启后&#xff0c;此方法将被调用执行&#xff0c;run()封装了被线程执行的代码void start()启动线程&#xff0c;Java虚拟机会调用run方法()、即…

解决oracle.sql.TIMESTAMP序列化转换失败问题 及 J2EE13Compliant原理

目录 报错现象报错内容处理方法Oracle驱动源码总结 报错现象 oracle表中存在TIMESTAMP类型的列时&#xff0c;jdbc查出来做序列化时报错 报错内容 org.springframework.web.util.NestedServletException: Request processing failed; nested exception is org.springframewo…

C语言--每日练习题--Day38

第一题 1. 下列代码的运行结果&#xff08;&#xff09; short i 65537; int j i 1; printf("i%d,j%d\n", i, j); A&#xff1a;i 65537&#xff0c;j 65538 B&#xff1a;i 1&#xff0c;j 2 C&#xff1a;i -1&#xff0c;j 0 D&#xff1a;i 1&#xff…

(新手必看)自定义数据传输通信协议+STM32代码详解

前言 本篇博客主要学习和了解一些单片机协议的格式&#xff0c;在对传输大数据或者要求准确性的时候&#xff0c;都需要通过协议来发送接收&#xff0c;下面通过了解协议的基本构成和代码来分析和实现协议的发送和接收。本篇博客大部分是自己收集和整理&#xff0c;如有侵权请联…

AlexNet 阅读笔记

“ImageNet Classification with Deep Convolutional Neural Networks” (Krizhevsky 等, 2012, p. 1) 使用深度卷积神经网络进行 ImageNet 分类 3公式&#xff0c;26个引用&#xff0c;4张图片&#xff0c;2个简单表格 Abstract 我们训练了一个大型深度卷积神经网络&#…

Android获取Wifi网关

公司有这样一个应用场景&#xff1a;有一台球机设备&#xff0c;是Android系统的&#xff0c;它不像手机&#xff0c;它没有触摸屏幕&#xff0c;所以我们对球机的操作很不方便&#xff0c;于是我们搞这样一个设置&#xff1a;点击球机电源键5次分享出一个热点&#xff0c;然后…

混合预编码(Hybrid Precoding)的全连接结构与子连接结构

A Survey on Hybrid Beamforming Techniques in 5G: Architecture and System Model Perspectives 全连接结构的混合预编码 子连接结构的混合预编码 Alternating Minimization Algorithms for HybridPrecoding in Millimeter Wave MIMO Systems

国产芯片D4145 的特性是什么?

D4145 是交流电源插座接地故障中断器的低功率控制器。 在发生有 害或致命冲击前&#xff0c;这些器件检测是否有危险的接地情况&#xff0c;比如设备( 与 AC 线路反相连接) 与水以及与裸露电线接触。内含一个 26V 齐纳并联稳压 器、 一个运算放大器和一个 SCR 驱动器。 D4145 新…

单节点hadoop搭建

下载Hadoop-bin.*.tar.gz 解压文件&#xff0c;配置HADOOP_HOME 编辑文件etc/hadoop/hadoop-env.sh配置JAVA_HOME 配置etc/hadoop/core-site.xml文件 <configuration><property><name>fs.defaultFS</name><value>hdfs://dachengnode1:9000<…

解决Sortable拖动el-table表头时,由于选择列造成的拖拽顺序错乱的bug

原因 由于我的表头是由数组循环遍历生成的&#xff0c;而选择列不在数组内&#xff0c;只能在循环外定义el-table-column&#xff0c;造成拖动时索引错乱错误代码 <el-tableheader-dragend"headerDragend"id"out-table":data"state.sliceTable&quo…

Vue.observable

让一个对象可响应。Vue 内部会用它来处理 data 函数返回的对象。 返回的对象可以直接用于渲染函数和计算属性内&#xff0c;并且会在发生变更时触发相应的更新。也可以作为最小化的跨组件状态存储器&#xff0c;用于简单的场景&#xff1a; const state Vue.observable({ coun…

【sqli靶场】第二关和第三关通关思路

目录 前言 一、sqli靶场第二关 1.1 判断注入类型 1.2 判断数据表中的列数 1.3 使用union联合查询 1.4 使用group_concat()函数 1.5 爆出users表中的列名 1.6 爆出users表中的数据 二、sqli靶场第三关 2.1 判断注入类型 2.2 观察报错 2.3 判断数据表中的列数 2.4 使用union联合…

将List<Map<String,Object>>转为List<Object>

经常在开发中会需要将List<Map<String&#xff0c;Object>>转为List&#xff0c;Object也就是你自己对应的目标对象&#xff0c;因为经常要用&#xff0c;干脆就自己封装了一个&#xff0c;代码示例如下&#xff1a; 假设有一个类&#xff1a;Animal.java public …

Ant Design 发布 5.12.2 版本

2023-12-11 Ant Design 发布 5.12.2 版本。 &#x1f41e; MISC: 修复 React 17 以下使用 webpack 构建时报错 useId 找不到的问题。#46261 Pagination&#x1f41e; 修复 Pagination 在低版本浏览器上报错的问题。react-component/pagination#545&#x1f41e; 修复 Paginati…