Codeforces Round #816 (Div. 2)

标签：那位 标记 int Codeforces 对应 ++ Div operatorname 816

D. 2+ doors

要让字典序最小就要让每个数字在满足条件的同时都尽可能的小并且排在前面的数字变小的优先级要比排在后面的数字的优先级更大。

\[\begin{aligned} 1\operatorname|1 &= 1\\ 0\operatorname|1 &= 1\\ 1\operatorname|0 &= 1\\ 0\operatorname|0 &= 0\\ \end{aligned} \]

先排序，让下标小的限定条件排在前面，等下才方便贪心。

如果 \(i\operatorname|j = x\) 那么当 \(x\) 二进制下某位为 \(0\) 时，\(i\) 和 \(j\) 对应的那位也必须是 \(0\) 我们用一个二维数组 \(a\) 来标记这些必须为 \(0\) 的位，标记为 \(2\)。

全部标记完以后再遍历一次，如果 \(x\) 二进制下某位为 \(1\)，若 \(i = j\)，那 \(i\) 对应的那位肯定是 \(1\)；如果 \(i\) 和 \(j\) 不相等，那么 \(i\) 对应的那位为 \(1\) 或 \(j\) 对应的那位为 \(1\)；如果 \(i\) 对应的那位已经被标记为 \(2\) 了，那么肯定是 \(j\) 对应的那位为 \(1\)，否则反之；如果是 \(1\) 那么标记为 \(1\)。

最后只剩一种情况，如果 \(x\) 二进制下某位为 \(1\) 且 \(i\) 和 \(j\) 对应的那位既没有被标记为 \(2\) 也没有被标记为 \(1\), 这种情况肯定是 \(j\) 对应的那位标记为 \(1\)。

#include "bits/stdc++.h"

using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);

  int n, m;
  cin >> n >> m;

  vector<array<int, 3>> q(m);

  for (int i = 0; i < m; i++) {
    int x, y, w;
    cin >> x >> y >> w;
    x--;
    y--;
    if (x > y) {
      swap(x, y);
    }
    q[i] = {x, y, w};
  }

  sort(q.begin(), q.end());

  vector<array<int, 30>> a(n);

  for (int i = 0; i < m; i++) {
    auto [x, y, w] = q[i];
    for (int j = 0; j < 30; j++) {
      if ((w >> j & 1) == 0) {
        a[x][j] = 2;
        a[y][j] = 2;
      }
    }
  }

  for (int i = 0; i < m; i++) {
    auto [x, y, w] = q[i];
    for (int j = 0; j < 30; j++) {
      if (w >> j & 1) {
        if (x == y) {
          a[x][j] = 1;
          a[y][j] = 1;
        } else if (a[x][j] == 2) {
          a[y][j] = 1;
        } else if (a[y][j] == 2) {
          a[x][j] = 1;
        }
      }
    }
  }

  for (int i = 0; i < m; i++) {
    auto [x, y, w] = q[i];
    for (int j = 0; j < 30; j++) {
      if (w >> j & 1) {
        if (a[x][j] == 0 && a[y][j] == 0) {
          a[y][j] = 1;
        }
      }
    }
  }

  for (int i = 0; i < n; i++) {
    int res = 0;
    for (int j = 29; j >= 0; j--) {
      res *= 2;
      if (a[i][j] == 2) {
        a[i][j] = 0;
      }
      res += a[i][j];
    }
    cout << res << " \n"[i == n - 1];
  }

  return 0;
}

标签：那位,标记,int,Codeforces,对应,++,Div,operatorname,816
From： https://www.cnblogs.com/kiddingma/p/17069996.html