视频1 视频21 视频41 视频61 视频文章1 视频文章21 视频文章41 视频文章61 推荐1 推荐3 推荐5 推荐7 推荐9 推荐11 推荐13 推荐15 推荐17 推荐19 推荐21 推荐23 推荐25 推荐27 推荐29 推荐31 推荐33 推荐35 推荐37 推荐39 推荐41 推荐43 推荐45 推荐47 推荐49 关键词1 关键词101 关键词201 关键词301 关键词401 关键词501 关键词601 关键词701 关键词801 关键词901 关键词1001 关键词1101 关键词1201 关键词1301 关键词1401 关键词1501 关键词1601 关键词1701 关键词1801 关键词1901 视频扩展1 视频扩展6 视频扩展11 视频扩展16 文章1 文章201 文章401 文章601 文章801 文章1001 资讯1 资讯501 资讯1001 资讯1501 标签1 标签501 标签1001 关键词1 关键词501 关键词1001 关键词1501 专题2001
codeforcesRound#275(div2)D解题报告
2020-11-09 08:01:59 责编:小采
文档

解法:

我们先挖掘题意,弄清楚题目给的已知条件和要我们输出什么。

a[l] & a[l+1] & a[l+2] ... & a[r] = q,这是每个的基本形式,由“&”我们可以得知,如若q中的某一个bit是1的话,则要求a[l]~a[r]中的那个bit位都为1。这个条件看似是,现在通过转化,似乎可以成为我们的已知条件,即每一个a[i]中的必须要为1的bit。

通过上述可知,我们得到每个a[i]的基本值,然后每一个是一个区间,很容易就想到了线段树,对每一条进行查询,看是否冲突,如若冲突则为"NO“,如若不冲突,则就按照a[i]的必须值来输出即可。

代码:

#include 
#include 
#define Maxbit 29
#define M_max 123456
#define N_max 123456
#define root 1, 1, n

using namespace std;

const int noth = (1<<30)-1;

int n, m;
int l[M_max], r[M_max], q[M_max], a[N_max];
int sum[N_max], tree[N_max*3];

void build(int v, int l, int r) {
	if (l == r) {
	tree[v] = a[l];
	return;
	}

	int ls = v<<1, rs = ls+1, mid = (l+r)>>1;

	build(ls, l, mid);
	build(rs, mid+1, r);

	tree[v] = tree[ls] & tree[rs];
}

int query(int v, int l, int r, int ql, int qr) {
	if (r < ql || l > qr) return noth;

	if (ql <= l && r <= qr) return tree[v];

	int ls = v<<1, rs = ls+1, mid = (l+r)>>1;

	return query(ls, l, mid, ql, qr) & query(rs, mid+1, r, ql, qr);
}

void init() {
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= m; i++)
	scanf("%d%d%d", &l[i], &r[i], &q[i]);

	for (int i = 0; i <= Maxbit; i++) {
	memset(sum, 0, sizeof(sum));

	for (int j = 1; j <= m; j++)
	if ((q[j] >> i) & 1) {
	sum[l[j]]++;
	sum[r[j]+1]--;
	}

	for (int j = 1; j <= n; j++) {
	sum[j] += sum[j-1];
	if (sum[j] > 0) a[j] |= 1 << i;
	}
	}

	build(root);
}

void solve() {
	for (int i = 1; i <= m; i++)
	if (query(root, l[i], r[i]) != q[i]) {
	printf("NO\n");
	return;
	}

	printf("YES\n");
	for (int i = 1; i <= n; i++) printf("%d ", a[i]);
	printf("\n");
}

int main() {
	init();
	solve();
}

下载本文
显示全文
专题