題目

一個整數(shù)集合S是合法的，指S的任意子集subS有Fun（SubS）！=X，其中X是一個固定整數(shù)，Fun(A)的定義如下：
A為一個整數(shù)集合，設(shè)A中有n個元素，分別為a0，a1，a2,...,an-1,那么定義：Fun(A)=a0 or a1 or ... or an-1；Fun({}) = 0,即空集的函數(shù)值為0.其中，or為或操作。
現(xiàn)在給你一個集合Y與整數(shù)X的值，問在集合Y至少刪除多少個元素能使集合Y合法？

例如：Y = {1,2,4}，X=7；顯然現(xiàn)在的Y不合法，因為 1 or 2 or 4 = 7，但是刪除掉任何一個元素后Y將合法。所以，答案是1.

輸入

第一行兩個整數(shù)N，X，其中N為Y集合元素個數(shù)，X如題所述，且1<=N<=50,1<=X<=1,000,000,000.
之后N行，每行一個整數(shù)yi，即集合Y中的第i個元素，且1<=yi<=1,000,000,000.

輸出

一個整數(shù)，表示最少刪除多少個元素。

輸入樣例

5 7
1
2
4
7
8

輸出樣例

2

思路：

為了讓集合的所有子集不等于所給的值，所以要去算這個原集合會對這個數(shù)二進制所在位的貢獻

如果一個數(shù)|所給的數(shù)大于所給數(shù)時，由于其|任何數(shù)不會等于所給數(shù)，那么這個數(shù)是不需要刪除的

之后計算所有 (x|y)<=y 的數(shù)，然后選擇最小的那個

源程序

#include<iostream> #include<cstdio> #include<cstdlib> #include<string> #include<cstring> #include<cmath> #include<ctime> #include<algorithm> #include<utility> #include<stack> #include<queue> #include<vector> #include<set> #include<map> #define EPS 1e-9 #define PI acos(-1.0) #define INF 0x3f3f3f3f #define LL long long const int MOD = 1E9+7; const int N = 1000000+5; const int dx[] = {-1,1,0,0}; const int dy[] = {0,0,-1,1}; using namespace std;LL a[N]; int num[N]; int judge(LL n,LL x) {while(n) {if(x%2==0&&n%2==1)return 1;n=n/2;x=x/2;}return 0; } void calculate(LL n) {for(int i=1; i<=35&&n!=0; i++) {if(n%2==1)num[i]++;n/=2;} } int main() {int n;LL x;scanf("%d%lld",&n,&x);int sum=0;for(int i=1; i<=n; i++) {scanf("%lld",&a[i]);sum^=a[i];if(a[i]<=x&&judge(a[i],x)==0)calculate(a[i]);}int res=INF;for(int i=1; i<=35; i++) {if(x%2==1)res=min(res,num[i]);x/=2;}printf("%d\n",res);return 0; }

?

總結(jié)

以上是生活随笔為你收集整理的合法整数集（51Nod-1315）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。