生活随笔
收集整理的這篇文章主要介紹了
二进制枚举子集
小編覺得挺不錯的,現在分享給大家,幫大家做個參考.
思路：
利用二進制的“開關”特性枚舉；詳細為：如果給定集合A大小為n，則想象A = {a[0], a[1], ..., a[n-1]}的每一個元素相應一個開關位（0或1），0表示不出現，1表示出現。當每一個元素的開關位的值確定時，就得到一個子集。因此共同擁有2^n-1種情況（全0為空集，這里不考慮）；我們利用區間[1, 2^n-1]，該區間上的每一個整數相應一個子集。相應方法是遍歷該整數二進制表示的每一位。若該位為1則相應子集中存在相應元素。否則不存在。
代碼：
#include <bits/stdc++.h>
using namespace std;
void print_subset(
int n,
int s)
{
for (
int i =
0; i < n; i++)
if (s & (
1 << i))
cout << i <<
" ";
cout << endl;
}
int main(
int argc,
char const *argv[])
{
int n;
while (
cin >> n && n)
for (
int i =
0; i < (
1 << n); i++)print_subset(n, i);
return 0;
}
CF #306 (Div. 2) B. Preparing Olympiad
題意：
給你一個數組。求滿足子集的個數：滿足的條件： 子集中全部元素的和不超過給定的l 和 r ;最大值-最小值 < x;
代碼：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<math.h>
using namespace std;
#define LL long long
#define clr(a,b) memset(a,b,sizeof a)
int n,l,r,x;
int A[
26];
int main()
{
#ifndef ONLINE_JUDGEfreopen(
"in.txt",
"r",stdin);freopen(
"out.txt",
"w",stdout);
#endif while(~
scanf(
"%d%d%d%d",&n,&l,&r,&x)){
for(
int i=
0; i<n; i++){
scanf(
"%d",&A[i]);}
int m=
1<<n;
int cnt=
0;
for(
int i=
0; i<m; i++){
int Max=-
1;
int Min=
0x3f3f3f3f;
int s=
0;
for(
int j=
0; j<n; j++){
if(i&(
1<<j)){s+=A[j];
if(A[j]>Max) Max=A[j];
if(A[j]<Min) Min=A[j];}}
if(s>=l&&s<=r&&Max-Min>=x) cnt++;}
printf(
"%d\n",cnt);}
return 0;
}
總結
以上是生活随笔為你收集整理的二进制枚举子集的全部內容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。
