codeforcesRound#275(div2)D解題報告

來源：懂視網責編：小采時間：2020-11-09 08:01:59

codeforcesRound#275(div2)D解題報告

codeforcesRound#275(div2)D解題報告:D. Interesting Array time limit per test 1 second memory limit per test 256 megabytes input standard input output standard output We'll call an array of n non-negative integers a [1]， a [2]。.。 a [ n ] interesting , if it meets m const

推薦度：

點擊下載本文 文檔為doc格式

導讀codeforcesRound#275(div2)D解題報告:D. Interesting Array time limit per test 1 second memory limit per test 256 megabytes input standard input output standard output We'll call an array of n non-negative integers a [1]， a [2]。.。 a [ n ] interesting , if it meets m const

解法：

我們先挖掘題意，弄清楚題目給的已知條件和要我們輸出什么。

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();
}

聲明：本網頁內容旨在傳播知識，若有侵權等問題請及時與本網聯系，我們將在第一時間刪除處理。TEL:177 7030 7066 E-MAIL:11247931@qq.com