题目描述
因为今天刚学bitset感到很开心,所以来做一做这个位运算的经典题。
本题解bitset的用法 :
bitset<10(长度)>s(变量名);
s.set() 全都变成1
s.reset() 全都变成0
bitset的其他用法详见:
https://www.cnblogs.com/fengxunling/p/9864827.html
因为是位运算,在二进制下,所以最后的答案的每一位上要么是0要么是1,也就是无论怎么运算都是只有两种情况。而且初始的状态每一位上也就只有两种情况——
那么我们先设两个量,一个初始化每一位都是1,一个初始化每一位都是0,然后模拟着运算。运算到最后我们可以得到每一位上如果开始是1和如果开始是0的最后情况。
之后就是贪心,我们要让答案中出现的1越多越好。所以如果开始是0最后变成了1,(也就是伤害变多了)一定是需要选取的。
如果开始是1最后变成了0,或者开始是0结果还是0这种无意义情况,都不选。
如果开始是1最后变成了1,只要初始伤害值比1<<
(1在这一位的位数)大(也就是满足题目条件),显然也是要选取的。
所以说。。代码如下:
C++ 代码
#include<bits/stdc++.h>
using namespace std;
int n , m ;
int main()
{
bitset<40> none , one ;
none.reset(); // 一个初始化每一位都是0
one.set(); // 一个初始化每一位都是1
cin >> n >> m ;
while(n--)
{
string x ;
int y ;
cin >> x >> y ;
if(x == "AND") none &= y , one &= y ;
else if(x == "OR") none |= y , one |= y ;
else none ^= y , one ^= y ;
}
int ans = 0 ;
for(int i = 0 ; i < 31 ; i ++)
{
if(none[i] == 1) ans += (1 << i);
//所以如果开始是0最后变成了1,(也就是伤害变多了)一定是需要选取的。
else if(one[i] == 1 && m >= (1 << i)) ans += (1 << i);
//如果开始是1最后变成了1,只要初始伤害值比1<<
// (1在这一位的位数)大(也就是满足题目条件),显然也是要选取的。
}
cout << ans << endl;
return 0;
}
修正代码:
请教一下为什么把bitset[HTML_REMOVED]改成bitset<40>会出错
代码中那个
for (int i = M; i >= 0; i--)
i赋值为M了,改成i=30就行测试了一下1 << i 改成1LL << i 就没问题了,似乎是越界造成了奇奇怪怪的错误
突然发现bitset都不需要,-1,0就可以代表完了,还能进一步优化空间。
要判断特殊情况了
for从30开始,每次选1的时候m要更新,这样应该就没问题了,我没试,错了别怪我hh
是的,正确的贪心策略就应该是从高位获取,而m应当有个动态维护的过程来满足“不大于m”的这个条件。
现在的数据貌似用不了这个题解了 不知道为啥子 我也感觉没错呀 最后一个数据通过不了
作者在one[i]==1对ans操作时判断条件是1<<i小于m,这点应该改为所有的1<<i加起来小于m。就是说加一个变量
记录一下最开始哪一位取1,判断条件加一个这个变量加1<<i小于m。这时候为了让最终结果最大,最后一个循环应该从i=30开始往下遍历。
最开始哪一位取1 是指 最高位吗
就是说作者 else if(one[i] == 1 && m >= (1 << i)) ans += (1 << i); 代表最开始的数字的第i位是1,作者只考虑了这一位能不能取1,没有考虑如果取1了会不会影响之后的。题目限制最大不超过m。
加一个变量记录取1后的和,保证这个不超过m
方便私聊吗
我怀疑这个题解有bug,你的如果m>=(1<<i)这里,如果刚好m==(1<<i)并且前面有0转换成1的情况,ans在加上(1<<i),是不是ans就会大于m
那怎么改呀
答主大大,我刚才提交了个工单把你hack了 qwq
改了丢丢。。。不知道比特树的小伙伴可以看看
赞~~QWQ
现在过不了了
m >= (1 << i) + ans 这句判断有点问题吧,ans是最后受到的伤害,不能用作判断初始选取的大小吧
是的有丢丢问题 ,不用管ans
是的 有问题 已更新
我的想法没问题,假如直接用题主的源代码将
for(int i = 0 ; i < 31 ; i ++)
改成for(int i=30;i>=0;i--)
会WA,这是因为else if比较的是ans,实际上应该开一个新的变量来存当前的初始攻击力,我定义为savem将else if 里面的ans替换成savem,for改成30~0也可以AC了owo
还有为什么for是0~31,而31~0 WA了呢……不是应该是从最高位开始判断吗
是30到0 位运算的每一位是独立的
之前m >= (1 << i) + ans这个地方错了
可能导致你30到0wa了
至于为啥i最大是30 是因为m的最大值是1e9
在所有可能的位运算中
1e9的二进制是 111011100110101100101000000000
刚好是30位
最后的答案最大就是30个1
和你从哪一位开始判断没有任何关系
嗯嗯好的,我明白了~
m >= (1 << i) + ans 这里没有看懂,不是说m限制的是最开始的攻击力,但是这里是和ans做比较,感觉不对呀,可以解惑吗
是的 已更新
之前犯糊涂了 好久之前写的了
太强了
else if(all[i]==1&&m>=(1<<i)+ans)ans+=(1<<i);是不是这里应该这样写啊
现在在看的话 位运算的每一位是独立计算的
0变成1 是不用管m的限制
1变成1 的前提是m >= 1 << i
所以m>=(1<<i)+ans这么写是不对的
ans是经过若干次操作之后可能的答案
m是你一开始选的那个值的最大值
建议可以在读读题
这个题解爱了
为什么for里面的i,<31,而其他的不行?
因为位运算不改变二进制的位数 这题t的大小最大是1e9 而2的30次方刚好是1 073 741 824比1e9大 所以是可以这样的
至于为啥i最大是30 是因为m的最大值是1e9
在所有可能的位运算中
1e9的二进制是 111011100110101100101000000000
刚好是30位
最后的答案最大就是30个1
强强强
强,c++写代码真舒服
说实话这个题解才是最好的