Warning: session_start(): open(/tmp/sess_f263cae88ebe447e1eddf85d802ff83c, O_RDWR) failed: No space left on device (28) in /data/wiki/inc/init.php on line 239

Warning: session_start(): Failed to read session data: files (path: ) in /data/wiki/inc/init.php on line 239

Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/auth.php on line 430

Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/actions.php on line 38

Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/lib/tpl/dokuwiki/main.php on line 12
2020-2021:teams:wangzai_milk:fwt刷题 [CVBB ACM Team]

用户工具

站点工具


2020-2021:teams:wangzai_milk:fwt刷题

FWT刷题

总之我先放一个题表在这里。

CF662C

题意:给定一个n*m的01矩阵,可以取反若干次任意行或列,问若干次操作之后1最少是多少。

数据范围:$n\leq 20,m\leq 100000$

题解:n的范围很小,我们可以考虑二进制枚举行的取反策略,假设行的翻转策略为S,那么这道题目的答案就是$\sum_{i=1}^m min(f(S\oplus a_i),n-f(S\oplus a_i))$,f函数为这一列1的个数。

那么我们假设$g(i)=min(f(i),n-f(i))$,那么原式就可以改写为$\sum_{j,i\oplus S = j}g(j)\times f(i)$,按照异或的性质,可以直接改写为

$\sum_{j,i\oplus j = S}g(j)\times f(i)$

那么好了,接下来我们就可以轻松的用fwt解决这道题目了。

点击以显示 ⇲

点击以隐藏 ⇱

#include <bits/stdc++.h>
using namespace std;
const int V = 1<<20;
const int N = 22;
const int M = 100005;
 
int n,a[M];
long long dp[V],cnt[V];
char s[N][M];
int calc(int x) {
	int ans = 0;
	while (x) {
		ans+=(x&1);
		x>>=1;
	}
	return ans;
}
 
void FWT(long long *src,int len) {
	for (int sz = 2;sz <= len; sz<<=1) {
		int step = sz>>1;
		for (int i = 0;i < len;i+=sz) {
			for (int j = i;j < i+step;j++) {
				long long a = src[j],b = src[j+step];
				src[j] = a+b;
				src[j+step] = a-b;
			}
		}
	}
}
 
void IFWT(long long *src,int len) {
	for (int sz = 2;sz <= len;sz <<= 1) {
		int step = sz >> 1;
		for (int i = 0;i<len;i+=sz) {
			for (int j = i;j < i+step;j++) {
				long long a = src[j],b = src[j+step];
				src[j] = (a+b)>>1;
				src[j+step] = (a-b)>>1;
			}
		}
	}
}
int main()
{
	int n,m;
	scanf("%d%d",&n,&m);
	for (int i = 0;i<n;i++)
		scanf("%s",s[i]+1);
	for (int i = 1;i<= m;i++) {
		int tmp = 0;
		for (int j = 0;j < n;j++)
			tmp |= ((s[j][i]-'0')<<j);
		cnt[tmp]++;
	}
	int len = 1<<n;
	for (int i = 0;i<len;i++)
	{
		int tmp = calc(i);
		dp[i] = min(tmp,n-tmp);
	}
	FWT(cnt,len);
	FWT(dp,len);
	for (int j = 0;j < len;j++)
		dp[j] *= cnt[j];
	IFWT(dp,len);
	long long ans = n*m+1;
	for (int j = 0;j < len;j++)
		ans = min(ans,dp[j]);
	printf("%lld\n",ans);
	return 0;
}

CF914G

HDU5909

HDU5823

HDU6057

2020-2021/teams/wangzai_milk/fwt刷题.1594915410.txt.gz · 最后更改: 2020/07/17 00:03 由 infinity37