Bzoj3517 翻硬币题解 解异或方程组
2024-09-01 02:38:38
3517: 翻硬币
Time Limit: 1 Sec Memory Limit: 128 MB
Submit: 281 Solved: 211
[Submit][Status][Discuss]
Description
有一个n行n列的棋盘,每个格子上都有一个硬币,且n为偶数。每个硬币要么是正面朝上,要么是反面朝上。每次操作你可以选定一个格子(x,y),然后将第x行和第y列的所有硬币都翻面。求将所有硬币都变成同一个面最少需要的操作数。
Input
第一行包含一个正整数n。
接下来n行,每行包含一个长度为n的01字符串,表示棋盘上硬币的状态。
Output
仅包含一行,为最少需要的操作数。
Sample Input
4
0101
1000
0010
0101
0101
1000
0010
0101
Sample Output
2
HINT
【样例说明】
对(2,3)和(3,1)进行操作,最后全变成1。
【数据规模】
对于100%的数据,n ≤ 1,000。
上来一看,第一反应,异或数学题,想了半天如何异或也没想出来,问呵呵酵母菌,他说他觉得是图论WTF?!图论有几个O(n)算法能在这道题用上的。
于是乎看了一眼题解:解异或方程组……
一个点最多翻一遍,这话不用再说了吧……
让我们先从都翻为0开始说起
我们设x[i][j]为第i,j个点是否要翻,a[i][j]为该点初始状态,则x[1][j]^x[2][j]^……^x[n][j]^x[i][1]^x[i][2]^x[i][m]^x[i][j]=a[i][j]。
我们把第i行和第j列所有的点按照上式列出方程组并合并, 由于n为偶数,则可以化为:
x[i][j]=a[1][j]^a[2][j]^……^a[n][j]^a[i][1]^a[i][2]^……^a[i][m]^a[i][j]。
那么我们只要对于每一行,每一列n^2预处理出他们的异或和再相加就好了。
至于都为1吗?由于n是偶数,我们只要把每一个点是否翻的状态取反就是答案。
#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <queue>
#include <algorithm>
#include <cmath>
#include <map>
#define N 1005
using namespace std;
int n,a[N][N];
char b[N];
int sum[][N];
int main()
{
scanf("%d",&n);
for(int i=;i<=n;i++)
{
scanf("%s",b+);
for(int j=;j<=n;j++)
{
a[i][j]=b[j]-'';
}
}
for(int i=;i<=n;i++)
{
for(int j=;j<=n;j++)
{
sum[][i]^=a[i][j];
sum[][j]^=a[i][j];
}
}
int ans=;
for(int i=;i<=n;i++)
{
for(int j=;j<=n;j++)
{
int t=sum[][i]^sum[][j];
t^=a[i][j];
ans+=t;
}
}
ans=min(ans,n*n-ans);
printf("%d\n",ans);
return ;
}
最新文章
- Bellman-Ford 单源最短路径算法
- PetaPoco4.0 实体某个字段不赋值会更新成null解决方案
- IIS部署站点相关经验总结
- nginx服务器在IE下载时,apk,ipa文件变成zip的解决方法
- hdoj 2059 :龟兔赛跑 (DP)[转]
- Linux永久挂载远程网络目录
- (转).net程序员转战android第一篇---环境部署
- R实战读书笔记四
- Winform程序
- 由Find All References引发的思考。,
- 全景智慧城市常诚——没接触过VR全景的你就是目前VR最大的新闻
- Python数据库连接池DBUtils.PooledDB
- WPF ObservableCollection 异步调用问题
- 锋利的jQuery初学(1)
- SWIG 基本概念和入门
- face detection[PyramidBox]
- nginx-1.12.1编译参数详情
- 利用原生态的(System.Web.Extensions)JavaScriptSerializer将mvc 前台提交到controller序列化复杂对象
- BestCoder Round #29——A--GTY&#39;s math problem(快速幂(对数法))、B--GTY&#39;s birthday gift(矩阵快速幂)
- Docker应用系列(一)| 构建Redis哨兵集群
热门文章
- 采用WebService客户端调用WSDL/SOAP网络报错的解决办法
- iText类库再pdf中显示中文字体
- 基于开源软件构建高性能集群NAS系统,包括负载均衡(刘爱贵)
- Use Spring @Scheduled To Achieve Timing Task
- Windows 10 (IIS 10)安装Microsoft Web Farm Framework Version 2.2 for IIS7问题
- PHPstudy + phpstrom +xdebug 断点调试(windows) - CSDN博客
- windows-qt 使用mingw编译c++boost并使用
- DUI-Windows消息机制要点(34篇)
- Java Socket基础[备忘]
- 为什么有如此多的C++测试框架 - from Google Testing Blog