NOI2014 起床困难综合症

wjh15101051's space

卧薪尝胆，厚积薄发。

NOI2014 起床困难综合症

Date: Mon Sep 10 14:15:51 CST 2018

In Category: NoCategory

Description：

在 $[0,m]$ 中选一个数使得它与一些给出的数进行位运算得到的数最大。

$1\le n \le 10^5$

Solution：

由于每一位之间独立，记一个 $s1$ 表示每一位都是一最后能得到的结果， $s0$ 同理，最后按位贪心。

Code：


#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cstring>

using namespace std;

int n,m;

int a1,a0;

int main()

{

	a1 = 0x7fffffff;a0 = 0;

	scanf("%d%d",&n,&m);

	char c[10];int k;

	for(int i = 1;i <= n;++i)

	{

		scanf("%s%d",c,&k);

		if(c[0] == 'A'){a1 = a1 & k;a0 = a0 & k;}

		if(c[0] == 'O'){a1 = a1 | k;a0 = a0 | k;}

		if(c[0] == 'X'){a1 = a1 ^ k;a0 = a0 ^ k;}

	}

	int res = 0;

	for(int i = 29;i >= 0;--i)

	{

		if((a0 >> i) & 1)res |= (1 << i);

		else if(((a1 >> i) & 1) && (1 << i) <= m)

		{

			res |= (1 << i);

			m -= (1 << i);

		}

	}

	cout << res << endl;

	return 0;

}

In tag: 其他-二进制算法-贪心

wjh15101051