null - 程序员宅基地

解题报告：CodeForces - 662C:Binary Table FWT(快速沃尔什变换)-程序员宅基地

技术标签： FWT 数论数学 ACM

题目链接

题意：

给定一个至多20*100000的01矩阵，可以选择任意行或列，选择行或列的01值改变，问经过操作能到最少的含1的数量。

思路：

因为行最大为20，考虑将每一列压缩成一个20位的整数，选择的行也最多只有20，同样压缩到一个20位的整数。

改变行上的01值，对应的操作为异或，那么就能写出对应的卷积式：

根据异或运算的性质，可以交换j,k的位置，得到：

C[k] : 选择操作的行的集合为k的最少含1数量

A[i]：列上数值为 i 的个数

B[j]：数 j 的最少含1个数

这就是一个标准的可以用FWT进行加速的卷积运算了

代码：

#include<bits/stdc++.h>

using namespace std;

void FWT(long long a[],int l,int on){
   for(int d=1;d<l;d<<=1){
      for(int m=d<<1,i=0;i<l;i+=m){
         for(int j=0;j<d;j++){
            long long x = a[i+j],y=a[i+j+d];
            a[i+j]=x+y;
            a[i+j+d]=x-y;
            if(on<0){
               a[i+j]>>=1;
               a[i+j+d]>>=1;
            }
         }
      }
   }
}



int n,m;
char str[100005];
int A[100005];
long long num[1<<21];
long long B[1<<21];
long long C[1<<21];
int main()
{
   scanf("%d%d",&n,&m);
   long long ans = n * m;
   for(int i=1,x;i<=n;i++){
      scanf("%s",str+1);
      for(int j=1;j<=m;j++){
         x = str[j]-'0';
         A[j] = (A[j]<<1) + x ;
      }
   }for(int i=1;i<=m;i++){
      num[A[i]]++;
   }int l = (1<<n);
   for(int i=0;i<l;i++){
      B[i] = B[i>>1] + (i&1);
      C[i] = min(B[i],n-B[i]);
   }FWT(num,l,1);FWT(C,l,1);
   for(int i=0;i<l;i++){
      C[i] = C[i] * num[i];
   }FWT(C,l,-1);
   for(int i=0;i<l;i++){
      ans = min(ans,C[i]);
   }printf("%I64d\n",ans);
   return 0;
}

本文链接：https://blog.csdn.net/qq_32570675/article/details/76602300

原作者删帖不实内容删帖广告或垃圾文章投诉

智能推荐

图像处理——过程全解析，配图超详细！-程序员宅基地

文章浏览阅读1.4k次。点击上方“小白学视觉”，选择加"星标"或“置顶”重磅干货，第一时间送达摘自先进测控之家《长着眼睛的机械手》课题摘要——利用图像处理技术，在50*50CM的区域内识别出5枚硬币（硬币位置任意），并且控制机械手逐一拾取5枚硬币，然后把5枚硬币逐一叠放到指定位置（指定位置随机）。图像处理过程详解——LabVIEWVision Assistant硬币位置识别算法分析与设计硬币的识别是本系统软件设计最为关..._图像处理

[ MATLAB ] 傅里叶变换（三）：傅里叶变换_傅里叶变换可视化,plot3函数,matlab-程序员宅基地

文章浏览阅读774次，点赞35次，收藏25次。专题的前两篇文章（[ MATLAB ] 傅里叶变换（二）：傅里叶级数（复指数表示）），我们讨论了连续周期信号傅里叶级数的两种表示形式，初步建立了频谱的概念。然而，就实际经验而言，非周期信号才是主流。因此，这篇文章将讨论非周期连续信号的谱密度（通常简称为频谱），即大名鼎鼎的傅里叶变换FT，并用Matlab仿真加强理解。可以采用物理中的密度的方式类比谱密度的概念，从而理解傅里叶变换中谱密度的意义。不需要再执着于分量幅值的绝对大小，而是聚焦于相对大小。_傅里叶变换可视化,plot3函数,matlab

5G手机回归，鸿蒙份额激增，将进一步夯实三大操作系统的地位-程序员宅基地

文章浏览阅读360次，点赞8次，收藏8次。市调机构给出的数据指11月份华为手机在国内手机市场的份额达到14%，远超此前鸿蒙系统在国内手机操作系统8%的市场份额，这意味着随着华为5G手机的回归，鸿蒙系统的市占率将快速上涨。此前鸿蒙系统主要依靠华为手机的存量用户支持，在华为的推动下，诸多华为存量手机用户都转为了鸿蒙系统，这成为鸿蒙系统的第一批种子。随后华为在自己的穿戴设备、汽车等诸多产品上发展鸿蒙系统，还通过与美的等国内家电企业合作推广鸿蒙系...

openstack pike单机一键安装shell的方法（后期会转为python）-程序员宅基地

文章浏览阅读183次，点赞9次，收藏2次。#VM虚拟机8G内存，安装完毕，半个小时左右#在线安装#环境 centos 7.4.1708 x86_64#在线安装openstack pikePS: 排版问题，还在研究。wangleideMacBook-Pro:Downloads wanglei$ cat pike.install.sh#!/bin/sh# openstack pike 单机一键安装# 环..._ali-pike.repo

通过formData数据发送ajax请求-程序员宅基地

文章浏览阅读1.9k次。formData1.创建一个formData对象var fd = new FormData(‘form表单’);(创建formdtata对象的小括号里面，就是需要一个form表单dom对象)。2.往fd对象中添加对象fd.append(‘sex’,‘男’);3.formData里面就会有form表单中有name属性的这些标签的取值。//键值对形式console.log(fd.ge...

监控神器Prometheus，开箱即用！-程序员宅基地

文章浏览阅读244次。文章来源：【公众号：云加社区】‍目录简介整体生态工作原理Metric 指标PromQLGrafana 可视化监控告警简介Prometheus 是一个开源的完整监控解决方案，本文将从指标抓取到查询及可视化展示，以及最后的监控告警，对 Prometheus 做一个基本的认识。Prometheus 是古希腊神话里泰坦族的一名神明，名字的意思是“先见之明”，下图中是 Promet..._dtm prometheus

随便推点

前端数据可视化ECharts使用指南——制作时间序列数据的可视化曲线_echarts 时间序列-程序员宅基地

文章浏览阅读3.7k次，点赞6次，收藏9次。我为什么选择ECharts ? 本周学校课程设计，原本随机佛系选了一个51单片机来做音乐播放器，结果在粗略玩了CN-DBpedia两天后才回过神，课设还没有开始整。于是懒癌发作，碍于身上还有比赛的作品没交，本菜鸡对硬件也没啥天赋，所以就直接把题目切换成软件方面的题目。写python的同学选择了一个时间序列数据的可视化曲线程序设计题目，果真python在数据可视化这一点性能很优秀。..._echarts 时间序列

ApplicationEventPublisherAware事件发布-程序员宅基地

文章浏览阅读1.6k次。事件类：/** * * 　 * @className: EarlyWarnPublishEvent * 　　* @description:数据风险预警发布事件 * 　　* @param: * 　　* @return: * 　　* @throws: * 　　* @author: lizz * 　　* @date: 2020/05/06 15:31 * */public cl..._applicationeventpublisheraware

自定义View实现仿朋友圈的图片查看器，缩放、双击、移动、回弹、下滑退出及动画等_imageview图片边界回弹-程序员宅基地

文章浏览阅读1.2k次。如需转载请注明出处！点击小图片转到图片查看的页面在Android开发中很常用到，抱着学习和分享的心态，在这里写下自己自定义的一个ImageView，可以实现类似微信朋友圈中查看图片的功能和效果。主要功能需求：1.缩放限制：自由缩放，有最大和最小的缩放限制 2居中显示：.若图片没充满整个ImageView，则缩放过程将图片居中 3.双击缩放：根据当前缩放的状态，双击放大两倍或缩小到原来 4.单指_imageview图片边界回弹

PreScan第二课：构建实验_prescan坐标系-程序员宅基地

文章浏览阅读5.5k次，点赞8次，收藏37次。为了自己和他人学习的需要，建了一个PreScan的QQ群：613469333（已满）/ 778225322（可加），加群前请私聊群主（QQ：2059799865）加入。群管理需要花费时间和精力，为了鼓励管理员和群成员积极互动，入群需交￥9.99的群费。目录1 Conventions坐标系统2 Roads3 Path&trajectories路径和轨迹3.1 Pat..._prescan坐标系

三分钟带你掌握 CSS3 的新属性_采用css转换,边框阴影等新特性完成css3偏光图像画廊设计-程序员宅基地

文章浏览阅读3.8w次，点赞9次，收藏10次。1. css3简介CSS 用于控制网页的样式和布局,CSS3 是最新的CSS标准,CSS3 完全向后兼容，因此您不必改变现有的设计。浏览器通常支持 CSS2,但是现在大部分浏览器也实现了css3的很多特性。CSS3 被划分为模块。其中最重要的 CSS3 模块包括：选择器框模型背景和边框文本效果2D/3D 转换动画多列布局用户界面2. css3边框2.1 边框圆角Internet Explorer 9+ 支持 border-radius 和 box-shadow 属性。Fir_采用css转换,边框阴影等新特性完成css3偏光图像画廊设计

设计模式--组合模式-程序员宅基地

文章浏览阅读47次。定义：允许将对象组成树形结构来表现 “整体/部分” 层次结构。组合能让客户以一致的方式处理个别对象及对象组合。说白了，就是类似于树形结构。只是它要求子节点和父节点都具备统一的接口。类图如下：示例如下：比如我们常见的电脑上的目录，目录下面有文件夹，也有文件，然后文件夹里面还有文件及文件夹。这样一层层形成了树形结构。示例代码如下：#include <iostream>#include <stdio.h>#include "string"#includ..