【CF662C】Binary Table
2024-08-24 02:05:33
好吧,我连板子都不会了
有一个非常显然的做法就是\(O(2^nm)\)做法就是枚举每一行的状态,之后我们贪心去看看每一列是否需要翻转就好啦
显然这个做法非常垃圾过不去
首先我们发现每一列都不超过\(20\),考虑把每一列都压成一个状态
我们考虑设一些奇怪的东西
设\(g_i\)表示行的翻转状态为\(i\)的最优解,\(f_i\)表示有多少列的状态为\(i\),\(dp_i\)表示\(i\)这个状态最少有多少个\(1\)
显然\(dp_i=min\{bit(i),n-bit(i)\}\)
我们考虑有一列原来的状态是\(k\),行的翻转状态为\(i\),翻转之后这一列的状态是\(j\)
就会存在\(i\bigoplus k=j\),也就是\(i=j\bigoplus k\)
也就是说
\[g_i=\sum_{j\bigoplus k=i}f_k\times dp_j
\]
\]
发现这是一个异或卷积,于是我们\(fwt\)一下就好了
代码
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#define re register
#define LL long long
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
const int maxn=(1<<20)+6;
LL cnt[maxn],dp[maxn],f[maxn];
int n,m,len;
char S[21][100005];
inline int Fwt(LL *t,int o) {
for(re int i=2;i<=len;i<<=1)
for(re int ln=i>>1,l=0;l<len;l+=i)
for(re int x=l;x<l+ln;++x) {
LL g=t[x],h=t[x+ln];
t[x]=g+h,t[ln+x]=g-h;
if(o) t[x]/=2ll,t[x+ln]/=2ll;
}
}
int main() {
scanf("%d%d",&n,&m);len=(1<<n);
for(re int i=0;i<len;i++) cnt[i]=cnt[i>>1]+(i&1);
for(re int i=0;i<len;i++) dp[i]=min(cnt[i],cnt[(len-1)^i]);
for(re int i=1;i<=n;i++) scanf("%s",S[i]+1);
for(re int i=1;i<=m;i++) {
int now=0;
for(re int j=1;j<=n;j++) {
if(S[j][i]=='1') now|=1;
now<<=1;
}
f[now>>1]++;
}
Fwt(f,0),Fwt(dp,0);
for(re int i=0;i<len;i++) f[i]*=dp[i];
Fwt(f,1);LL ans=f[0];
for(re int i=1;i<len;i++) ans=min(ans,f[i]);
std::cout<<ans;
return 0;
}
最新文章
- 创建自定义的Cocos2d-x场景
- The 2013 ACM-ICPC Asia Changsha Regional Contest - A
- 03静态链表_StaticLinkList--(线性表)
- Spring二 Bean详解
- python成长之路9——socket和socketserver
- unity 双面shader
- win7-x64安装mysql5.7.11(官方zip版)
- Asp.Net下,基于Jquery的Ajax二级联动
- nc 搭建环境流程及问题
- 44)django-环境变量设置
- 深入学习Motan系列(四)—— 客户端
- springboot用@Autowired和@PostConstruct注解把config配置读取到bean变成静态方法
- redis 的数据结构
- linux命令行打包、压缩及解压缩
- Linux - seq 预设外部命令
- 构建-13 Analyzer APK文件分析
- CentOS环境变量配置并生效
- java对对象排序
- 自制MVC框架的插件与拦截器基础
- bzoj 2131 免费的馅饼