CodeForces-1715D 2+ doors

2+ doors

贪心

位与位之间互不一向，因此考虑每个位进行考虑就行

因为是或的关系，先考虑 \(0\) 的情况，如果出现 \(0\)，则两个数字的该位必然是 \(0\)

如果是 \(1\) 的情况，就考虑贪心，从第一个数字开始往后考虑：

如果另一个数字的当前位是 \(0\)，则将当前数字的当前位置为 \(1\)，剩下的数字都是 \(0\)

因此可以考虑直接用位运算，一开始假设所有数字的所有位都是 \(1\)，然后赋予 \(0\) 的情况，最后再贪心的计算 \(1\) 的情况，防止冲突

#include <iostream>
#include <cstdio>
#include <string>
#include <vector>
using namespace std;
const int maxn = 1e5 + 10;
#define pii pair<int, int>
vector<pii>gra[maxn];

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n, m;
    cin >> n >> m;
    vector<int>ans(n + 1, (1 << 30) - 1);
    for(int i=0; i<m; i++)
    {
        int a, b, c;
        cin >> a >> b >> c;
        if(b > a) swap(a, b);
        gra[a].push_back({b, c});
        gra[b].push_back({a, c});
        ans[a] &= c;
        ans[b] &= c;
    }
    for(int i=1; i<=n; i++)
    {
        int now = 0;
        for(auto [nex, val] : gra[i])
        {
            now |= val & ~ans[nex];
            if(nex == i) now = val;
        }
        ans[i] &= now;
    }
    for(int i=1; i<=n; i++)
        cout << ans[i] << " ";
    cout << endl;
    return 0;
}