标签：P4148BitwiseAnd const int rep cin cnt return

贪心

考虑什么样的数的集合满足条件，发现同一个二进制位不能有超过 \(2\) 个数为 \(1\)

加入第 \(i\) 个数要满足的条件为:

• 这个数与前面的每个数的 \(and\) 不为 \(0\) ，即每次占用一个前面的数的 \(1\) ，这个 \(1\) 必须是这个数仅有的
• 这个数必须有 \(n-i\) 个仅有的 \(1\)，给后面的数连接

贪心的选择最小的，用 queue 维护

// Author: xiaruize
const int INF = 0x3f3f3f3f3f3f3f3f;
const int MOD = 1000000007;
const int N = 50 + 10;

int n, m;
int a[N];
int deg[N];
deque<int> vec;
queue<int> g[N];

void solve()
{
    cin >> n;
    rep(i, 1, n) cin >> a[i];
    cin >> m;
    rep(i, 1, n)
    {
        rep(j, 1, n)
        {
            if (!(a[i] & a[j]))
                return;
        }
        rep(j, 0, 59)
        {
            if ((a[i] >> j) & 1)
            {
                int cnt = 0;
                rep(k, 1, n)
                {
                    if (k != i)
                        cnt += ((a[k] >> j) & 1);
                }
                if (!cnt)
                {
                    deg[i]++;
                    g[i].push(j);
                }
                if (cnt >= 2)
                    return;
            }
        }
    }
    per(i, 59, 0)
    {
        bool flag = false;
        rep(j, 1, n)
        {
            flag |= ((a[j] >> i) & 1);
        }
        if (!flag)
            vec.push_back(i);
    }
    rep(i, n + 1, m)
    {
        rep(j, 1, i - 1)
        {
            if (g[j].empty())
                return;
            a[i] |= (1ll << g[j].front());
            g[j].pop();
        }
        rep(j, i + 1, m)
        {
            if (vec.empty())
                return;
            a[i] |= (1ll << vec.back());
            g[i].push(vec.back());
            vec.pop_back();
        }
    }
    sort(a + 1, a + m + 1);
    rep(i, 1, m) cout << a[i] << ' ';
}

#ifndef ONLINE_JUDGE
bool end_of_memory_use;
#endif

signed main()
{
    // freopen(".in","r",stdin);
    // freopen(".out","w",stdout);
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int testcase = 1;
    // cin >> testcase;
    while (testcase--)
        solve();
#ifndef ONLINE_JUDGE
    cerr << "Memory use:" << (&end_of_memory_use - &start_of_memory_use) / 1024.0 / 1024.0 << "MiB" << endl;
    cerr << "Time use:" << (double)clock() / CLOCKS_PER_SEC * 1000.0 << "ms" << endl;
#endif
    return 0;
}

标签：P4148BitwiseAnd,const,int,rep,cin,cnt,return
From： https://www.cnblogs.com/xiaruize/p/18121249