「题目链接」

点击打开链接

「题目概括」

给定$n$个操作,以op v的形式给出,$op$是$And,Or,Xor$中一个,$v$为非负整数。
现在请你求出一个$x\in[1,m]$,使得按照顺序执行操作后得到的数$Ans$最大。
数据范围 $n\leq 10^5,m,v\leq 2^{30}$

「思路要点」

因为每一位都是独立的,所有就按位贪心。
注意上界的处理。
时间复杂度 $\mathcal O(30\times n)$

「代码」

#include <bits/stdc++.h>

using namespace std;

vector<pair<int, long long> > op; 
int n;
long long m;

int get(int x, int d) {
  int ans = x;
  for (int i = 1; i <= n; i++) {
    if (op[i].first == 1) {
      ans &= op[i].second >> d & 1;
    } else if (op[i].first == 2) {
      ans |= op[i].second >> d & 1;
    } else {
      ans ^= op[i].second >> d & 1;
    }
  }
  return ans;
}

int main() {
#ifdef chhokmah
  freopen("input.in", "r", stdin);
#endif
  ios::sync_with_stdio(false);
  cin >> n >> m;
  op.resize(n + 1);
  for (int i = 1; i <= n; i++) {
    char opt[5]; 
    long long v;
    cin >> opt >> v;
    if (opt[0] == 'A') {
      op[i] = make_pair(1, v); 
    } else if (opt[0] == 'O') {
      op[i] = make_pair(2, v);
    } else {
      op[i] = make_pair(3, v);
    }
  }
  bool up = 1;
  long long ans = 0;
  for (int i = 30; i >= 0; i--) {
    int lim = up ? m >> i & 1 : 1, v = 0;
    for (int j = lim; j >= 0; j--) {
      if (get(j, i) == 1) {
        v = j;
        ans |= (1 << i);
      }
    }
    if (v != lim) {
      up = 0;
    }
  }
  cout << ans << '\n';
  return 0; 
}
最后修改:2020 年 03 月 24 日 04 : 38 PM
如果觉得我的文章对你有用,请随意赞赏