国产99久久精品_欧美日本韩国一区二区_激情小说综合网_欧美一级二级视频_午夜av电影_日本久久精品视频

最新文章專題視頻專題問答1問答10問答100問答1000問答2000關(guān)鍵字專題1關(guān)鍵字專題50關(guān)鍵字專題500關(guān)鍵字專題1500TAG最新視頻文章推薦1 推薦3 推薦5 推薦7 推薦9 推薦11 推薦13 推薦15 推薦17 推薦19 推薦21 推薦23 推薦25 推薦27 推薦29 推薦31 推薦33 推薦35 推薦37視頻文章20視頻文章30視頻文章40視頻文章50視頻文章60 視頻文章70視頻文章80視頻文章90視頻文章100視頻文章120視頻文章140 視頻2關(guān)鍵字專題關(guān)鍵字專題tag2tag3文章專題文章專題2文章索引1文章索引2文章索引3文章索引4文章索引5123456789101112131415文章專題3
問答文章1 問答文章501 問答文章1001 問答文章1501 問答文章2001 問答文章2501 問答文章3001 問答文章3501 問答文章4001 問答文章4501 問答文章5001 問答文章5501 問答文章6001 問答文章6501 問答文章7001 問答文章7501 問答文章8001 問答文章8501 問答文章9001 問答文章9501
當(dāng)前位置: 首頁 - 科技 - 知識百科 - 正文

codeforcesRound#275(div2)D解題報告

來源:懂視網(wǎng) 責(zé)編:小采 時間: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
推薦度:
導(dǎo)讀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。這個條件看似是限制,現(xiàn)在通過轉(zhuǎn)化,似乎可以成為我們的已知條件,即每一個a[i]中的必須要為1的bit。

通過上述可知,我們得到每個a[i]的基本值,然后每一個限制是一個區(qū)間,很容易就想到了線段樹,對每一條限制進行查詢,看是否沖突,如若沖突則為"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();
}

聲明:本網(wǎng)頁內(nèi)容旨在傳播知識,若有侵權(quán)等問題請及時與本網(wǎng)聯(lián)系,我們將在第一時間刪除處理。TEL:177 7030 7066 E-MAIL:11247931@qq.com

文檔

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
推薦度:
標(biāo)簽: 解題 round Codeforces
  • 熱門焦點

最新推薦

猜你喜歡

熱門推薦

專題
Top
主站蜘蛛池模板: 一级毛片免费视频 | 久久国产成人精品国产成人亚洲 | 狠狠色狠狠色综合日日不卡 | 成人无码一区二区片 | 99精品高清视频一区二区 | 综合久久综合 | 人人爽天天碰天天躁夜夜躁 | 欧美第一页 | 国产精品久久久久国产精品 | 国内精品一区二区 | 日韩高清在线观看 | 特黄一级毛片 | 国产免费观看网站 | 国产高清一区二区三区 | 久久精品成人一区二区三区 | 高清在线一区二区 | 欧美国产第一页 | 欧美日批 | 国产青草 | 久久精品国产国产精品四凭 | 99久久一区 | 欧美1区二区三区公司 | 亚洲视频一区二区三区 | 国产日韩欧美精品在线 | 久久久久久久岛国免费播放 | 永久在线毛片免费观看 | 亚洲欧美日韩中文字幕一区二区三区 | 乌克兰性欧美精品高清bd | 欧美日韩91 | 99视频都是精品热在线播放 | 欧美日韩亚洲电影天堂 | 国产高清免费不卡观看 | 日本不卡视频一区二区三区 | 午夜视频免费在线观看 | 99久久精品国产国产毛片 | 欧美日韩国产va另类 | 手机国产精品一区二区 | 国产欧美一区二区精品性色 | 亚洲欧美在线综合 | 亚洲欧美日韩成人一区在线 | 亚洲国产精品久久久久 |