首页 > 试题广场 >

按位或

[编程题]按位或

热度指数：1595 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

小易有一个初始为空的数字集合，支持两种操作：
1、加入数字x到集合中。

2、询问集合中是否存在一个子集，满足子集中所有数字的Or值恰好为k。

Or为二进制按位或操作，C++中表示为"|"。
小易希望你能解决这个问题。

输入描述:

第一行数字q,表示操作个数 
接下来q行，每行两个数字： 
1 x表示插入数字x 
2 x表示询问数字x(即题设中询问的数值k)
 ,  。

输出描述:

对于每个询问，输出"YES"或者"NO"表示是否存在。

示例1

输入

输出

NO
YES
NO
NO
YES

算法知识视频讲解

Python

Fzldq

import sys

def main():
    
    def exist(x):
        y = 0
        for i in lst:
            if i | x == x:
                y |= i
                if x == y:
                    return True
        else:
            return False

    lst = set()
    res = []
    q = int(sys.stdin.readline().strip())
    m = map(int, sys.stdin.read().split())
    xlst = list(zip(m, m))
    for i, j in xlst:
        if i == 1:
            lst.add(j)
        else:
            res += ['YES' if exist(j) else 'NO']
    print(*res, sep='\n')


if __name__ == '__main__':
    main()

Python玩这种题就是亏，只能过60%

编辑于 2020-07-20 15:51:08 回复(1)

帽子短了

#include <iostream>
#include <string>
#include <vector>
using namespace std;
bool isexist(vector<int> temp,int x)
{
	int y = 0;
	for (int i = 0; i < temp.size(); i++)
	{
		if ((x | temp[i]) == x)
			y = y | temp[i];
	}
	return x == y;
}
int main()
{
	int n;
	cin >> n;
	vector<int> temp;
	while (n--)
	{
		int a, x;
		cin >> a >> x;
		if (a == 1)
			temp.push_back(x);
		else
		{
			if (isexist(temp, x))
				cout << "YES" << endl;
			else
				cout << "NO" << endl;
		}	
	}
	system("pause");
	return 0;
}

发表于 2020-06-17 19:47:52 回复(0)

xiyu

#python3

try:
    data = []
    ks = []
    q = int(input())
    n = 1
    while n <= q:
        temp = []
        insert = list(input().split(" "))
        x = int(insert[0])
        k = int(insert[1])
        if x == 1:
            temp = []
            data.append(k)
            ks.append(k)
            ks = list(set(ks))
            if len(data) != 1:
                for i in range(len(ks)):
                    temp.append(ks[i] | k)
                for i in range(len(temp)):
                    ks.append(temp[i])
                ks = list(set(ks))
        if x == 2:
            flag = 0
            for i in range(len(ks)):
                if ks[i] == k:
                    flag = 1
                    break
            if flag:
                print("YES")
            else:
                print("NO")
except:
    pass

发表于 2020-04-11 18:38:38 回复(1)

offer-冲鸭

import java.util.*;
public class Main{
  public static void main(String[] args){
    Scanner sc = new Scanner(System.in);
    int q = sc.nextInt();
    Set<Integer> set = new HashSet<>();
    while(q-->0){
      int flag =sc.nextInt(),target=sc.nextInt();
      if(flag==1){set.add(target);}
      else{
        int temp=0;
        for(Integer each:set){
          if((each&target)==each){
            temp|=each;
          }
          if(each==target){temp=target;break;}
          if(target==temp)break;
        }
        if(temp==target){
          System.out.println("YES");
          set.add(target);
        }
        else System.out.println("NO");
      }
    }
     
  }
}
就通过60

发表于 2020-04-07 15:08:33 回复(0)

牛客327042102号

这道题可以建立一个位矩阵，每加入一个数据转化成二进制按行存入矩阵，查询时先匹配列上与要查数（按位）同为0的行，再看这些行上其他列上是否有1（每列只要一行有1即可）

发表于 2020-02-23 23:19:56 回复(3)

dragonlogin

思路

难点就是：怎么在一个集合 a 中判断是否存在一个子集，使得子集中所有元素或运算后的结果为 x

暴力想法
找到集合a中的所有子集，然后一一判断是否满足条件。
子集个数一共有2^n,n为集合元素个数。所以肯定超时
优化
有没有可能遍历一遍集合，就可以完成。
假设元素 x 的二进制为 100100101
如果存在a1 | a2 | a3 | 。。。 | an = x
根据 | 的特点，
0 | 0 = 0,
1 | 0 = 1,
0 | 1 = 1,
1 | 1 = 1
如果我x的倒数第二位是0，那么a1, a2,…,an的倒数第二位肯定不能为1
所以，需要满足a1 | x = x, a2 | x = x,可以用反证法证明。

#include <bits/stdc++.h>
using namespace std;
const int N = 100010;
bool st[N];
int q, o, x;

int main() {
    scanf("%d", &q);
    vector<int> a;
    while (q --) {
        scanf("%d%d", &o, &x);
        if (o == 1) {
            if (st[x] == false)
                a.push_back(x);
                st[x] = true;
        }
        else {
            int y = 0;
            for (int v : a) {
                if ((v | x) == x)
                    y |= v;
            }

            if (y == x) {
                printf("YES\n");
            }
            else {
                printf("NO\n");
            }
        }
    }
    return 0;
}

发表于 2020-07-30 18:20:07 回复(2)

一行代码&

a1=int(input())
a=[]
for i in range(a1):
    a.append(list(map(int, input().split())))
fun1(a)
def fun1(a):
    global ar1
    ar1=[]
    for i in range(len(a)):
        if a[i][0]==1:
            charu(a[i][1])
        elif a[i][0]==2:
            chaxun(a[i][1])    
def charu(x1):
    ar1.append(x1)
def chaxun(x2):
    for i in range(1,len(ar1)+1):
        for j in combinations(ar1,i):
            a=j[0]
            for k in range(1,len(j)):
                a=a|j[k]
            if x2==a:
                break
        if x2==a:
            break
    if x2==a:
        print("YES")
    else:
        print("NO")

python方便很多

发表于 2022-03-28 22:25:35 回复(0)

Java

爱面包的芋泥少女

public class solution1 { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int a = sc.nextInt(); int[] arr = new int[a]; int i = 0; while(a>0) { int b = sc.nextInt(); if(b == 1){ arr[i] = sc.nextInt();
                i++;
            }else{ int c = sc.nextInt(); int sum = 0; int j =0; for(;j<arr.length;j++) { if ((c | arr[j]) - c == 0) {
                     sum = sum | arr[j]; if (sum == c) { System.out.println("YES"); break;
                     }
                 } else { continue;
                 }
             } if(j == arr.length) System.out.println("NO");
            }
            a--;
        }
    }
    }

发表于 2021-03-17 21:13:17 回复(0)

秃头的代码菜鸟

大佬们，我没看懂为什么有5个输出啊，不应该有9个吗？🤣

发表于 2020-09-23 12:47:17 回复(0)

Python

Yvonne_Liu

from itertools import chain, combinations
n = int(input())
i = 0
data = []
total_list = []
# Create all the subsets that generated by input data
def powerset(iterable):
"powerset([1,2,3]) --> () (1,) (2,) (3,) (1,2) (1,3) (2,3) (1,2,3)"
s = list(iterable)
return chain.from_iterable(combinations(s, r) for r in range(len(s) + 1))

# Create a total_list to store all outputs that generated by OR operation
def add_function(list_of_subset): #subset = powerset(lst)
for i in list_of_subset:
if len(i) == 1:
total_list.append(i[0])
elif len(i) > 1:
total = 0
"new_function(tuple) --> 取出tuple里的value，再进行Or操作"
for elem in i:
total = (total | elem)
total_list.append(total)
return set(total_list)

# Main function: combine all functions together
while i < n:
command, num = input().split()
i += 1
if int(command) == 1:
data.append(int(num))
elif int(command) == 2:
total_set = add_function(powerset(data))
if int(num) in total_set:
# output.append('YES')
print('YES')
else:
print('NO')

只能通过30%

编辑于 2020-07-17 21:41:39 回复(0)

kelly逸狼居

或操作，确定某一位是否存在于集合中

发表于 2020-05-16 12:43:59 回复(0)

Burn201910171304230

#include<bits/stdc++.h>
using namespace std;
vector<int> v;
// 因为是按位或，对于待判断的数字中，若一位为1，则集合中所有数字，只要有一个这一位为1即可
// 如果完全能匹配上，就是存在
bool ifExist(int x){
    int y=0;
    for(int i=0;i<v.size();i++){
        if((x|v[i])==x){
            y = y|v[i];
        }
    }
    return x==y;
}
int main(){
    vector<bool> ans;
    int n;
    scanf("%d",&n);
    for(int i=0;i<n;i++){
        int o,x;
        scanf("%d%d",&o,&x);
        if(o==1) v.push_back(x);
        else{
            if(ifExist(x)) ans.push_back(true);
            else ans.push_back(false);
        }
    }
    for(int i=0;i<ans.size();i++){
        ans[i]?printf("YES\n"):printf("NO\n");
    }
    return 0;
}

编辑于 2020-04-07 15:18:10 回复(2)