开发一个网站要学什么软件,辽阳专业建设网站公司电话号码,郑州营销型网站建设价格,巩义网站建设指标点枚举子集
二进制枚举子集下面代码就是枚举的s的子集#xff08;二进制状态压缩#xff09; for(int is;i;i(i-1)s){//i表示的就是s的子集}枚举所有子集的子集的时间复杂度 比如一个有n个元素构成的集合#xff0c;子集的数量是2n2^n2n#xff0c;现要求枚举所有子集的…枚举子集
二进制枚举子集下面代码就是枚举的s的子集二进制状态压缩 for(int is;i;i(i-1)s){//i表示的就是s的子集}枚举所有子集的子集的时间复杂度 比如一个有n个元素构成的集合子集的数量是2n2^n2n现要求枚举所有子集的子集。 一个有k个元素构成的集合子集的数量是2k2^k2k
考虑nnn个元素构成的集合子集 元素个数是000的集合个数是Cn0C_n^0Cn0 元素个数是111的集合个数是Cn1C_n^1Cn1 …\dots… 于是有以下等式 Cn0×20Cn1×2n⋯Cnn×2n(12)n3nC_n^0×2^0C_n^1×2^n\dotsC_n^n×2^n(12)^n3^nCn0×20Cn1×2n⋯Cnn×2n(12)n3n
由此最终需要枚举3n3^n3n个状态时间复杂度为Θ(3n)\Theta(3^n)Θ(3n)
Close Group
首先暴力预处理出所有满足题意的连通块连通块中的点两两之间有直接边。Θ(n22n)\Theta(n^22^n)Θ(n22n)
状态压缩dp 状态表式fif_ifi表示选择iii这些点构成的最少数量的团 状态计算枚举iii状态的子集jjj于是有fimin(fi,fjfi⊕j)f_imin(f_i,f_jf_{i\oplus j})fimin(fi,fjfi⊕j) 时间复杂度枚举所有状态的子集即上述证明Θ(3n)\Theta(3^n)Θ(3n)
时间复杂度Θ(n22n3n)\Theta(n^22^n3^n)Θ(n22n3n)
3183874204893^{18}387 420 489318387420489差不多能过谁让状态压缩就是那么玄学呢
#define IO ios::sync_with_stdio(false);cin.tie();cout.tie(0)
#pragma GCC optimize(2)
#includeiostream
#includealgorithm
using namespace std;
const int N20;
bool ok[1N];
int g[N][N];
int dp[1N];
int main()
{IO;int T1;//cinT;while(T--){int n,m;cinnm;while(m--){int a,b;cinab;--a,--b;g[a][b]g[b][a]1;}for(int i0;i1n;i){vectorint t;for(int j0;jn;j)if(ij1) t.push_back(j);ok[i]1;for(int j0;jt.size();j)for(int kj1;kt.size();k)if(!g[t[j]][t[k]]) ok[i]0;}for(int i0;i1n;i) dp[i]n1;dp[0]0;for(int i1;i1n;i){if(ok[i]) dp[i]1;for(int ji;j;j(j-1)i)dp[i]min(dp[i],dp[j]dp[j^i]);}coutdp[(1n)-1]\n;}return 0;
}E - Or Plus Max
对于K的子集一定满足iorj≤Ki\ or\ j\leq Ki or j≤K 枚举子集记录子集的最大值和次大值相加即可
#define IO ios::sync_with_stdio(false);cin.tie();cout.tie(0)
#pragma GCC optimize(2)
#includeiostream
#includealgorithm
using namespace std;
const int N500010;
int a[N];
int mx[N],f[N];
int main()
{IO;int T1;//cinT;for(int ca1;caT;ca){int n;cinn;for(int i0;i1n;i){cina[i];mx[i]a[0];}for(int i0;i1n;i)for(int ji;j;j(j-1)i){f[i]max(f[i],a[j]mx[i]);mx[i]max(mx[i],a[j]);}for(int i1;i1n;i) {f[i]max(f[i-1],f[i]);coutf[i]\n;}}return 0;
}
