说明网站建设与网站运营的区别,网站用静态域名解析,wordpress如何接入支付接口,wordpress弹窗视频播放插件problem
洛谷链接
solution
第二次做的时候发现自己还是不会。发现自己没有写过题解#xff0c;看来当时是没有完全搞懂的。 nnn 与 mmm 的量级相差很大#xff0c;nnn 的范围是完全可以状压的。
不妨考虑枚举最后翻转了哪些行#xff0c;将操作状压为一个数 XXX。
显然…problem
洛谷链接
solution
第二次做的时候发现自己还是不会。发现自己没有写过题解看来当时是没有完全搞懂的。
nnn 与 mmm 的量级相差很大nnn 的范围是完全可以状压的。
不妨考虑枚举最后翻转了哪些行将操作状压为一个数 XXX。
显然对于同样的 XXX 其最优答案是唯一的。
记第 iii 列操作状态为 C(i)C(i)C(i)。
每一列都是相互独立的所以贪心的可以在一开始就将这一列预先翻转到最少的 111。
记列状态为 iii 时经过翻转最终的最少有 B(i)B(i)B(i) 个 111。
对于该列而言最后的列状态是列操作和行操作的叠加即 X⨁C(i)X\bigoplus C(i)X⨁C(i) 。
因此最后的 111 的个数统计方法就是枚举每一列然后记录∑i1mB(X⨁C(i))\sum_{i1}^mB(X\bigoplus C(i))∑i1mB(X⨁C(i))
考虑枚举最后列的状态∑i1m∑j02n−1[X⨁C(i)j]B(j)\sum_{i1}^m\sum_{j0}^{2^n-1}[X\bigoplus C(i)j]B(j)∑i1m∑j02n−1[X⨁C(i)j]B(j)。
记所有列中有 A(i)A(i)A(i) 列的状态为 iii。
则 ∑i02n−1∑j02n−1[X⨁ij]B(j)⋅A(i)\sum_{i0}^{2^n-1}\sum_{j0}^{2^n-1}[X\bigoplus ij]B(j)·A(i)∑i02n−1∑j02n−1[X⨁ij]B(j)⋅A(i)。
X⨁ij⇒Xi⨁j⇒∑i02n−1∑j02n−1[i⨁jX]A(i)⋅B(j)⇒ans[X]∑i⨁jXA(i)B(j)X\bigoplus ij\Rightarrow Xi\bigoplus j\Rightarrow \sum_{i0}^{2^n-1}\sum_{j0}^{2^n-1}[i\bigoplus jX]A(i)·B(j)\Rightarrow ans[X]\sum_{i\bigoplus jX}A(i)B(j)X⨁ij⇒Xi⨁j⇒∑i02n−1∑j02n−1[i⨁jX]A(i)⋅B(j)⇒ans[X]∑i⨁jXA(i)B(j)。
其实最后的答案就是 A,BA,BA,B 的卷积。
code
#include bits/stdc.h
using namespace std;
#define int long long
char s[25][100005];
int A[1 21], B[1 21];
int n, m, N;void fwt( int *c, int f ) {for( int i 1;i N;i 1 )for( int j 0;j N;j ( i 1 ) )for( int k 0;k i;k ) {int x c[j k], y c[j k i];c[j k] x y;c[j k i] x - y;if( f -1 ) c[j k] / 2, c[j k i] / 2;}
}signed main() {scanf( %lld %lld, n, m );N 1 n;for( int i 1;i n;i ) scanf( %s, s[i] 1 );for( int j 1;j m;j ) {int k 0;for( int i 1;i n;i ) k k 1 | (s[i][j] ^ 48);A[k] ;}for( int i 0;i N;i ) {int k __builtin_popcount( i );B[i] min( k, n - k );}fwt( A, 1 );fwt( B, 1 );for( int i 0;i N;i ) A[i] A[i] * B[i];fwt( A, -1 );int ans 0x3f3f3f3f;for( int i 0;i N;i ) ans min( ans, A[i] );printf( %lld\n, ans );return 0;
}
