求助排版不整齐
  • 板块灌水区
  • 楼主VioletIsMyLove
  • 当前回复17
  • 已保存回复17
  • 发布时间2020/8/11 19:27
  • 上次更新2023/11/6 20:37:07
查看原帖
求助排版不整齐
188879
VioletIsMyLove楼主2020/8/11 19:27

这道题的题目描述就是给你一个 aa 数组,然后再给你个 mm ,让你找一个最大的 kk ,使 kk 异或整个 aa 数组的和小于等于 mm

笨蛋的方法就是从大到小枚举 kk,一旦异或 aa 数组的和小于等于 mm,了,就输出 kk,但这样的时效使绝对不行的。

所以我们来想一想异或的实质,两个数,AA,BB, AA 异或 BB 的值就是将 AABB 都转为二进制数,然后向右按位对其,将小的数左边塞 00 使 22 个数的二进制位数相等,然后从左往右扫,一旦这一位上的二进制不同,假设位数为 yy ,异或的值 xx 就要加上 2y2^y

好了既然是求 kk 异或整个 aa 数组的和,那其实就是将整个 aa 数组转成二进制数,然后存在一个数组中,将 kk 也转换成二进制数进行比对不就得了?但其实想到这里就不需要枚举 kk,只需要通过模拟,当异或 yy 这一位的时候,如果 kk 的二进制数在这一位为0的时候,异或的值就加上 1<<(n这一位上1的个数)1<<(n-这一位上1的个数),为 11 时 异或的值就加上 1<<这一位上1<<这一位上 1的个数 的个数。只要为1时符合这一位就取 11 ,因为要 kk 越大越好嘛,不符合再取 00 ,而如果2个都不符合时就回朔嘛,所以要用DFS来模拟这个过程。

但是!在处理异或和的过程中,1<<(n这一位上1的个数)1<<(n-这一位上1的个数)1<<这一位上1的个数1<<这一位上1的个数 的值可能会爆出long long,为了不开高精我们可以与处理一下,在代码中标出了。

2020/8/11 19:27
加载中...