起床困难综合症(0x01位运算)

简介: 笔记

起床困难综合症


题意

drd 的防御战线由 n 扇防御门组成。


每扇防御门包括一个运算 op 和一个参数 t,其中运算一定是 OR,XOR,AND 中的一种,参数则一定为非负整数。


如果还未通过防御门时攻击力为 x,则其通过这扇防御门后攻击力将变为 x op t。


最终 drd 受到的伤害为对方初始攻击力 x 依次经过所有 n 扇防御门后转变得到的攻击力。


由于 atm 水平有限,他的初始攻击力只能为 0 到 m 之间的一个整数(即他的初始攻击力只能在 0,1,…,m 中任选,但在通过防御门之后的攻击力不受 m 的限制)。


为了节省体力,他希望通过选择合适的初始攻击力使得他的攻击能让 drd 受到最大的伤害,请你帮他计算一下,他的一次攻击最多能使 drd 受到多少伤害。


思路

这道题的前提是 位运算的主要特点之一是在二进制表示下不进位


所以假设我们选择的初始值为x 那么我们可以分别考虑 x 的每一位应该选择 0 还是 1


最后组合到一起,就得到了最终的 x


那么第 k 位 选 1 还是 0 呢?


对于下面两种情况 选择 1 更优


已经填好的更高位的数值加上 1 << k 小于等于 m。

初始值为 1 得到的最终值比初始值为 0 得到的最终值大

若不满足上面两个条件,那么肯定是选 0 更优


每一位都确定好之后,就可以得到答案


代码

#include<bits/stdc++.h>
// #define int long long
#define INF 0x3f3f3f3f
#define mod 1000000007
#define rep(i, st, ed) for (int (i) = (st); (i) <= (ed);++(i))
#define pre(i, ed, st) for (int (i) = (ed); (i) >= (st);--(i))
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
template<typename T> inline T gcd(T a, T b) { return b ? gcd(b, a % b) : a; }
template<typename T> inline T lowbit(T x) { return x & -x; }
const int N = 1e5 + 10;
int n, m;
pair<string, int>a[N];
int cal(int bit, int x) {
  for (int i = 1; i <= n; ++i) {
    int k = a[i].second >> bit & 1;
    if (a[i].first == "AND") x &= k;
    else if (a[i].first == "OR") x |= k;
    else x ^= k;
  }
  return x;
}
void solve() {
  cin >> n >> m;
  for (int i = 1; i <= n; ++i) {
    string str;
    int x;
    cin >> str >> x;
    a[i] = { str,x };
  }
  int res = 0, val = 0;
  for (int i = 29; i >= 0; --i) {
    int res0 = cal(i, 0);
    int res1 = cal(i, 1);
    if (val + (1 << i) <= m && res0 < res1) {
      val += 1 << i;
      res += res1 << i;
    }
    else res += res0 << i;
  }
  cout << res << endl;
}
signed main() {
  // int t; cin >> t;
  // while (t--)
    solve();
  return 0;
}


目录
打赏
0
0
0
0
1
分享
相关文章
iOS平台如何实现RTSP|RTMP播放端录像?
我们在做RTSP、RTMP直播播放器的时候,有个比较重要的功能,就是拉流端实时录像,包括设置单个录像文件大小、文件前缀、audio转AAC、只录制视频或只录制音频、开始录像、停止录像事件状态回调等。
206 5
大连理工卢湖川团队TMI顶刊新作 | M^2SNet: 新颖多尺度模块 + 智能损失函数 = 通用图像分割SOTA网络
大连理工卢湖川团队TMI顶刊新作 | M^2SNet: 新颖多尺度模块 + 智能损失函数 = 通用图像分割SOTA网络
608 0
一天十道Java面试题----第一天(面向对象-------》ArrayList和LinkedList)
这篇文章是关于Java面试的笔记,涵盖了面向对象、JDK/JRE/JVM的区别、`==`和`equals`、`final`关键字、`String`、`StringBuffer`和`StringBuilder`的区别、重载与重写、接口与抽象类、`List`与`Set`、`hashcode`与`equals`以及`ArrayList`和`LinkedList`的对比等十个主题。
c语言《数据结构》散列表(哈希表)
c语言《数据结构》散列表(哈希表)
200 0
kde
|
6天前
|
Docker镜像加速指南:手把手教你配置国内镜像源
配置国内镜像源可大幅提升 Docker 拉取速度,解决访问 Docker Hub 缓慢问题。本文详解 Linux、Docker Desktop 配置方法,并提供测速对比与常见问题解答,附最新可用镜像源列表,助力高效开发部署。
kde
3877 8
AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等