【题解】洛谷P2114 [NOI2014]起床困难综合症

题目

洛谷P2114 [NOI2014]起床困难综合症

题解

题意简化为:在0~m之间找一个数,使得这个数在一系列操作后最大。

由于原数有大小限制,又要使得到的数尽量大,为了充分地利用限制,就需要按位从高到低贪心,确定原数是选0还是选1。如果可以使得到的数为1,则尽量选,同时要考虑原数限制,还要使原数尽量小。

需要记录每一位为0或1时,在经过操作后会变成什么。只要用一个全0数和一个全1数整体操作即可,最后一位位取出来。

代码

Subscribe
提醒
guest
1 评论
Oldest
Newest Most Voted
Inline Feedbacks
View all comments
cyx
cyx
2020年8月13日 下午1:06

【小白解析】
改题目可以看作:输入一二进制数,在每一次操作中(即每过一扇门),都对每一位进行一次相同的位运算,最终使结果最大化。值得注意的是,“与或非”位运算并不会导致二进制中的进位或退位,因此可以将每一位看作是独立的成分;贪心算法的意义便在此:只要尽可能使结果的高位为1,得到的必然是最大结果。
不过传统的枚举必然不可行,因此不妨先让两个包含了所有可能性的极端值(即等于0的a0和表示为30个1的a1)首当其冲——先对之进行所有操作,得到两串二进制数。第一串数的每一位都是0进过操作的结果,第二串则是1。因此,我们只需要从高位到地位比对这两个结果,若某一串的更高位是1,我们的结果就在这一位为1。简单粗暴。
具体实现位于第10-12行。第10行生成考察从左往右第i位的掩码cur,第11行考察最小值(输入全部为0)的情况:若该位为1,最终结果的该位也为1;第12行考察最大值(输入全部为1),此时同时需要注意,若输入值大于m则不成立,因此需要判断st+cur是否大于m(此处cur不仅是判断a1转换后的第i为是否为1,也代表a1的原本第i位是1,因此可以顺手牵羊拿来使用。第11行没有操作是因为a0全部位数位0,不操作和操作效果一致)。若两者判断都为false,说明这一位怎么着也捞不到1(大悲)。最后拼出的缝合怪数字既是最高伤害。
*这题目真是有够中二的。