Evacuation - 个人主页动态

2020-07-18 20:25

已编辑

侥幸全ac了，第二题多重背包的一种优化写法，前几天刚好复习过，运气好。 题目1:给定一个数x，数据对 (a, b)使得a ^ b ^ x能达到最大，求使|a - b|最小的方案总数有多少。x,a,b的范围都是0 - （2^31 次方-1）0 -> 2, 100 -> 16题目2:包粽子, 四个数n, m, c0, d0, 一共n 克面粉， m种馅料然后m行,每行四个数ai, bi, ci, di, ai 表示一共多少克该种馅料每个粽子包法, bi克第i种馅料 + ci 克面粉, 收益di, 或者 c0 克面粉, 不包馅料, 收益d0求最大收益 第一题，可知x^a^b=INT_M...

牛客相当牛：感谢楼主，终于把第一题想明白了，首先，先考虑二进制位为1的情况，比如100---1100100，要将其转换为31位全为1，x^a ^b, 必须保证x为1的位出现1的次数为奇数，只能是1^1^1或1^0^0, 每个x为1的位有两种情况；然后考虑其他位，使得|a-b|最小，那么不管x是多少，其他剩余的位都为0，所以a和b的位必定相反，a-b最小只有一种情况，因此该位!a = b, a为1b为0或者a为0b为1，最后的结果是: (1 >> num(1的个数) ) >> 1, 然后需要考虑INT_MAX和INT_MIN，如果是这两个数方案除2

投递阿里巴巴等公司10个岗位 >