题目:
现在有一个长度为n的序列待构造,给出m对关系\(i, j,x\),表示\(a_i|a_j=x\),请在满足这m对关系的情况下构造出的最小字典序的序列。
分析:
每当我们看到最小字典序的时候,基本都是贪心的思想。本题可以知道,我们要让序列前面的数尽可能的小。对于他给出的关系,需要按位来考虑,但是有一些麻烦的就是你确定一个数的一位的时候,他会影响到与他有关系的数,感觉就是一个二分图的思想。我们可以用\(f0[i][j]\)表示第\(i\)个数在第\(j\)位必定填0,\(f1[i][j]\)同理必定填1。顺序遍历序列,枚举位,能填0就填0。
实现:
对于给出的关系 若x在第\(k\)位上为0,那么\(i\)和\(j\)在第k位上都必须填0,若x在第\(k\)位上为1,那么\(i\)和\(j\)在第k位上至少要有一个人是1。同时不能忽略\(i=j\)的情况,若\(i==j\)且x在第\(k\)位上为1,那么\(i\)在第k位上必须填1。那么现在我们预处理出了必须填的情况,但是还有一种情况我们是不能确定的,就是当某位可以填0或者填1的时候,怎么办?基于贪心的思想,肯定是填0最好,但是不一定能填上。为什么?因为如果你这一位填0,那么和他有关的那个数的这一位必须就填1,所以要在合法的情况下,才能填上0。这就是用到了二分图的思想,实现上我们将这种模糊的关系连一条边,对于当前\(a_i\)决定要填0的时候,遍历一下,若目标数在该位上必须填0,那么我当前\(a_i\)就只能填1了,因为模糊的优先级是不如必定的。
#include <bits/stdc++.h>
using namespace std;
#define rep(i, a, n) for(int i = a; i < n; i++)
#define all(x) x.begin(), x.end()
#define pb push_back
#define ios ios::sync_with_stdio(false);cin.tie(0);
#define debug(x) cout << x << endl;
#define SZ(x) (int)x.size()
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int, int> PII;
const int inf = 0x3f3f3f3f;
void read(int &x) {int s = 0, f = 1; char ch = getchar(); while(!isdigit(ch)) {f = (ch == '-' ? -1 : f); ch = getchar();} while(isdigit(ch)) {s = s * 10 + ch - '0'; ch = getchar();} x = s * f;}
const int N = 100005;
int n, m;
vector<int> g[N][30];
int f0[N][30], f1[N][30]; //第i个数的第j位必须填0或者必须填1
signed main()
{
cin >> n >> m;
rep(i, 1, m + 1)
{
int u, v, c;
cin >> u >> v >> c;
if(u > v) swap(u, v);
for(int j = 29; j >= 0; j --)
{
if(c >> j & 1)
{
if(u == v)
f1[u][j] = f1[v][j] = 1;
else
g[u][j].push_back(v);
}
else
f0[u][j] = f0[v][j] = 1;
}
}
rep(i, 1, n + 1)
{
int res = 0;
for(int j = 29; j >= 0; j --)
{
bool can0 = 1;
if(f1[i][j])
can0 = 0;
else if(!f1[i][j] && !f0[i][j])
{
for(int v : g[i][j])
if(f0[v][j])
can0 = 0;
}
if(can0) //这位填0
for(int v : g[i][j])
f1[v][j] = 1;
else
res += 1 << j;
}
cout << res << ' ';
}
cout << '\n';
}
标签:f0,f1,ch,1715D,int,CF,位上,doors,define
From: https://www.cnblogs.com/DM11/p/16649209.html