首页 > 代码库 > topcoder srm 694 div1 -3
topcoder srm 694 div1 -3
1、给出$n$个数字，将其分成三个非空的组，每组的权值为该组所有数字的抑或。选择一种分法使得三组的权值和最大？
思路：记录前两组的权值且三组有没有数字时第三组的值。（当前两组的值知道时第三组的权值是确定的，因为三组的抑或值是确定的）
#include <iostream>#include <stdio.h>#include <cstdlib>#include <algorithm>#include <cmath>#include <string.h>#include <set>#include <vector>#include <time.h>#include <queue>#include <stack>#include <map>#include <assert.h>using namespace std;int f[2][256][256][8];class TrySail{public: int get(vector<int> A) { int pre=0,cur=1; memset(f[pre],-1,sizeof(f[pre])); f[0][0][0][0]=0; for(int i=0;i<(int)A.size();++i) { memset(f[cur],-1,sizeof(f[cur])); const int w=A[i]; for(int b=0;b<256;++b) { for(int c=0;c<256;++c) { for(int d=0;d<8;++d) { int k=f[pre][b][c][d]; if(k==-1) continue; f[cur][b^w][c][d|4]=k; f[cur][b][c^w][d|2]=k; f[cur][b][c][d|1]=k^w; } } } pre^=1; cur^=1; } int ans=0; for(int a=0;a<256;++a) { for(int b=0;b<256;++b) { if(f[pre][a][b][7]!=-1) { ans=max(ans,f[pre][a][b][7]+a+b); } } } return ans; }};
2、给出$n*m$的只包含‘A‘到‘Z‘的字符矩阵。对于一个列的集合$S$，如果任意两行$i,j$在$S$上不完全相同，称$S$可以区分所有行。问有多少种列的子集可以区分所有行？$n\leq 1000,m\leq 20$
思路：首先，找到哪些列的子集不能区分所有行。令$f[s]=1$表示集合$s$不能区分所有行，那么所有的$s$^$2^{k}$都不能区分。其中$k$满足$s$&$2^{k}\neq 0$。
#include <iostream>#include <stdio.h>#include <cstdlib>#include <algorithm>#include <cmath>#include <string.h>#include <set>#include <vector>#include <time.h>#include <queue>#include <stack>#include <map>#include <assert.h>using namespace std;int f[1<<20];class DistinguishableSetDiv1{public: int count(vector<string> A) { int n=A.size(); int m=A[0].size(); memset(f,0,sizeof(f)); for(int i=0;i<n;++i) for(int j=i+1;j<n;++j) { int s=0; for(int k=0;k<m;++k) if(A[i][k]==A[j][k]) s|=1<<k; f[s]=1; } int ans=0; for(int i=(1<<m)-1;i>=0;--i) { if(f[i]) { for(int k=0;k<m;++k) if(i&(1<<k)) f[i^(1<<k)]=1; } else ++ans; } return ans; }};
topcoder srm 694 div1 -3
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。