网站开发岗位思维导图,学编程的软件有哪些,wordpress卸载 数据库,开鲁网站seo站长工具CF662C Binary Table
题意#xff1a;
有一个 n 行 m 列的表格#xff0c;每个元素都是 0/1 #xff0c;每次操作可以选择一行或一列#xff0c;把 0/1 翻转#xff0c;即把 0 换为 1 #xff0c;把 1 换为 0 。请问经过若干次操作后#xff0c;表格中最少有多少个 1 …CF662C Binary Table
题意
有一个 n 行 m 列的表格每个元素都是 0/1 每次操作可以选择一行或一列把 0/1 翻转即把 0 换为 1 把 1 换为 0 。请问经过若干次操作后表格中最少有多少个 1 n20,m1e5
题解
参考 洛谷题解第一篇讲的太详细了 因为行很小(n20)列很大(m1e5)因为我们可以考虑枚举反转了哪些行。设X表示翻转了哪些行(X是一个整数其二进制表示翻转的状态) 对于任意一列设第i列的状态为SiS_iSi也是其二进制表示该列的状态 现在开始考虑每一列都变成什么样子 设第i列翻转后变成了状态YiY_iYi,显然有YiSi⨁XY_iS_i \bigoplus XYiSi⨁X 对于一个相同的X(即一个行翻转方案)最优答案1的个数是唯一的,而X最多只有22010485762^{20}10485762201048576,也就是我们可以直接枚举X 因为每一列都是相互独立的为了让表格中1最少对于每一列翻转到最少个1位置设状态为i时经过翻转这个二进制最少有FiF_iFi个1 比如n3(3)10(011)2(3)_{10}(011)_2(3)10(011)2,翻转后为(100)2(100)_2(100)2 所以F31F_31F31 答案就是∑i1mF{X⨁Si}\sum_{i1}^mF_{\{X \bigoplus S_i\}}∑i1mF{X⨁Si} 我们枚举所有X再枚举每一列状态的S总复杂度是O(2nm)O(2^nm)O(2nm),还是不行 继续对式子优化我们枚举YiSi⨁XY_iSi \bigoplus XYiSi⨁X 式子为∑i1m∑Y02n[YSi⨁X]FY\sum_{i1}^m\sum_{Y0}^{2^n}[YS_i \bigoplus X]F_Yi1∑mY0∑2n[YSi⨁X]FY 我们试着换掉第一个枚举m的∑\sum∑,设所有列中有QiQ_iQi列的状态为i相当于用桶来存 这样就可以得到 ∑S02n∑Y02n[YS⨁X]FY×QS\sum_{S0}^{2^n}\sum_{Y0}^{2^n}[YS \bigoplus X]F_Y×Q_SS0∑2nY0∑2n[YS⨁X]FY×QS 这样枚举每个S不用再枚举[1,m] 不过还是没啥卵用因为此时复杂度是O(22n)O(2^{2n})O(22n),好像还更差了,但与m无关了 此时这个式子就有些猫腻了 ∑S02n∑Y02n[YS⨁X]FY×QS\sum_{S0}^{2^n}\sum_{Y0}^{2^n}[Y S \bigoplus X]F_Y×Q_SS0∑2nY0∑2n[YS⨁X]FY×QS ⇔∑S02n∑Y02n[Y⨁SX]FY×QS⇔\sum_{S0}^{2^n}\sum_{Y0}^{2^n}[Y \bigoplus S X]F_Y×Q_S⇔S0∑2nY0∑2n[Y⨁SX]FY×QS ⇔∑Y⨁SFY×QS⇔\sum_{Y \bigoplus S}F_Y×Q_S⇔Y⨁S∑FY×QS 设ANS[X]∑Y⨁SXFY×QSANS[X]\sum_{Y \bigoplus SX}F_Y×Q_SANS[X]∑Y⨁SXFY×QS 这这。。不就是FWT吗答案不就是F和Q的xor卷积这样复杂度就变成了O(2n∗log(2n))O(2n∗n)O(2^n*log(2^n))O(2^n*n)O(2n∗log(2n))O(2n∗n)完美解决
代码
#include bits/stdc.h
#include unordered_map
#define debug(a, b) printf(%s %d\n, a, b);
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pairint, int PII;
clock_t startTime, endTime;
//Fe~Jozky
const ll INF_ll 1e18;
const int INF_int 0x3f3f3f3f;
void read(){};
template typename _Tp, typename... _Tps void read(_Tp x, _Tps... Ar)
{x 0;char c getchar();bool flag 0;while (c 0 || c 9)flag| (c -), c getchar();while (c 0 c 9)x (x 3) (x 1) (c ^ 48), c getchar();if (flag)x -x;read(Ar...);
}
template typename T inline void write(T x)
{if (x 0) {x ~(x - 1);putchar(-);}if (x 9)write(x / 10);putchar(x % 10 0);
}
void rd_test()
{
#ifdef ONLINE_JUDGE
#elsestartTime clock ();freopen(data.in, r, stdin);
#endif
}
void Time_test()
{
#ifdef ONLINE_JUDGE
#elseendTime clock();printf(\nRun Time:%lfs\n, (double)(endTime - startTime) / CLOCKS_PER_SEC);
#endif
}
int n,m;
const int maxn1e59;
const int maxn2(120)9;
ll Q[maxn2],F[maxn2],S[maxn2],ANS[maxn];
ll a[30][maxn];
void FWT(ll x[],int t1,int t2,int len)
{const ll inv2 2;for(int i1;ilen;i1)for(int j0;jlen;j(i1))for(int k0;ki;k){ll px[jk],qx[ijk];if(t10) x[ijk](qt2*p); //orelse if(t11) x[jk](pt2*q); //andelse if(t12) //xor{x[jk](pq)/(t20?inv2:1);x[ijk](p-q)/(t20?inv2:1);} }
}
int main()
{rd_test();cinnm;for(int i1;in;i){for(int j1;jm;j){scanf(%1d,a[i][j]);}}int len1n;//S为每一列的状态预处理出S for(int i1;im;i){//列 for(int j1;jn;j){//行 S[i]|(1(j-1))*a[j][i];}}//状态为i时经过翻转这个二进制最少有F[i]个1 for(int i0;ilen;i){F[i]F[i1](i1);}for(int i0;ilen;i){F[i]min(F[i],n-F[i]);//正着与翻转着取min }//所有列中有Q[i]列的状态为i,就相当于是个桶 for(int i1;im;i)Q[S[i]];FWT(F,2,1,len);FWT(Q,2,1,len);for(int i0;ilen;i)ANS[i]F[i]*Q[i];FWT(ANS,2,-1,len);//在len种翻转方案种取最小值 ll minn9999999999; for(int X0;Xlen;X)minnmin(ANS[X],minn);coutminnendl;//开始卷Q和F//Time_test();
}
