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

最新文章專題視頻專題問答1問答10問答100問答1000問答2000關鍵字專題1關鍵字專題50關鍵字專題500關鍵字專題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關鍵字專題關鍵字專題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
當前位置: 首頁 - 科技 - 知識百科 - 正文

CodeforcesRound#220(Div.2)D樹狀數組&&二分_html/css

來源:懂視網 責編:小采 時間:2020-11-27 15:59:05
文檔

CodeforcesRound#220(Div.2)D樹狀數組&&二分_html/css

CodeforcesRound#220(Div.2)D樹狀數組&&二分_html/css_WEB-ITnose:/*題目*/ 題意:給了n,m,然后一個包含m個數的數組nnum,數組默認從小到大排序,然后是 n個操作,輸入一個數x,若x為0,把0加到這個字符串的末尾,若x為1,把1加到這個字符串的末尾,若x為-1,那么把字符串里的 下標 與 nnum數組里的元素相等的 給刪除,
推薦度:
導讀CodeforcesRound#220(Div.2)D樹狀數組&&二分_html/css_WEB-ITnose:/*題目*/ 題意:給了n,m,然后一個包含m個數的數組nnum,數組默認從小到大排序,然后是 n個操作,輸入一個數x,若x為0,把0加到這個字符串的末尾,若x為1,把1加到這個字符串的末尾,若x為-1,那么把字符串里的 下標 與 nnum數組里的元素相等的 給刪除,

/*題目*/


題意:給了n,m,然后一個包含m個數的數組nnum,數組默認從小到大排序,然后是 n個操作,輸入一個數x,若x為0,把0加到這個字符串的末尾,若x為1,把1加到這個字符串的末尾,若x為-1,那么把字符串里的 下標 與 nnum數組里的元素相等的 給刪除,字符串一開始是空的,問你最后字符串里有什么,若為空 就輸出 POOR STACK

這題目看這操作一般都很容易聯想到線段樹,樹狀數組,一開始我建了個樹狀數組,但是超時了,畢竟操作很多,而且 在刪除操作里,若nnum數組很大,等同于10^12的復雜度,只能優化,一般來說是用二分了,直接以這個串的某個位置是否為空來建立樹狀數組,每一次加在最后就不用說了,直接加就可以,關鍵在于刪除,首先刪除,要第一步二分查找出 要刪除的最后一位,比如字符串長度為7,而nnum數組里 有個8,其實8這個位置不需要刪除的,但是這個還是超時,于是想到在樹狀數組里刪除的時候也需要二分,可是寫了一直錯,后來借鑒了杰哥的發現,原來WA在這里,比如 當前字符串為01010,需要刪除 1,3,4位置的字符,要輪著來,當你刪除1號位置的時候,字符串變成了1010,你在樹狀數組里也是要刪除1節點的狀態,所以原來的3號位置在當前變成了2號位置,當你刪了3號以后變成了110 ,原來的4號位置變成了2號位置,所以每刪除一次,下標會發生變化,但是沒事,發現前面操作了幾次而你原來的下標就比當前 減少了幾,所以 nnum[i] - i 其實就是 當前需要刪除的 元素 在 樹狀數組里的位置


int n,m;int c[1000000 + 55];int nnum[1000000 + 55];int aa[1000000 + 55];int sum[1000000 + 55];int len;void init() {	memset(c,0,sizeof(c));	memset(aa,-1,sizeof(aa));}bool input() {	while(cin>>n>>m) {	for(int i=0;i>nnum[i];	return false;	}	return true;}int lowbit(int x) {	return x&(-x);}void add(int i,int val) {	while(i <= n) {	c[i] += val;	i += lowbit(i);	}}int get_sum(int i) {	int sum = 0;	while(i > 0) {	sum += c[i];	i -= lowbit(i);	}	return sum;}void binary_find(int pos,int id) {	int l = 1;	int r = n;	while(l <= r) {	int mid = (l + r)>>1;	int ret = get_sum(mid);	if(aa[mid] == -1) {	if(ret >= nnum[pos] - id) r = mid - 1;	else l = mid + 1;	}	else if(ret == nnum[pos] - id) {	add(mid,-1);	aa[mid] = -1;	len--;	break;	}	else if(ret > nnum[pos] - id) r = mid - 1;	else if(ret < nnum[pos] - id) l = mid + 1;	}}void cal() {	int q = n;	len = 0;	int cnt = 1;	while(q--) {	int type;	cin>>type;	if(type == -1) {	if(len == 0)continue;	if(nnum[0] > len)continue;	int now = lower_bound(nnum,nnum + m,len) - nnum;	for(int i=0;i<=now;i++)	binary_find(i,i);	}	else {	aa[cnt] = type;	add(cnt,1);	cnt++;	len++;	}	}	if(len <= 0){puts("Poor stack!");return ;}	for(int i=1;i<=n;i++)	if(aa[i] != -1)	printf("%d",aa[i]);	puts("");}void output() {}int main() {	while(true) {	init();	if(input())return 0;	cal();	output();	}	return 0;}

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

文檔

CodeforcesRound#220(Div.2)D樹狀數組&&二分_html/css

CodeforcesRound#220(Div.2)D樹狀數組&&二分_html/css_WEB-ITnose:/*題目*/ 題意:給了n,m,然后一個包含m個數的數組nnum,數組默認從小到大排序,然后是 n個操作,輸入一個數x,若x為0,把0加到這個字符串的末尾,若x為1,把1加到這個字符串的末尾,若x為-1,那么把字符串里的 下標 與 nnum數組里的元素相等的 給刪除,
推薦度:
  • 熱門焦點

最新推薦

猜你喜歡

熱門推薦

專題
Top
主站蜘蛛池模板: 精品视频一区二区三区四区五区 | 国产成人精品日本亚洲专区6 | 亚洲三级电影网 | 亚洲视频欧洲视频 | 欧美成人伊人久久综合网 | 欧美第5页| 精品成人一区二区三区免费视频 | 欧美一级久久久久久久大片 | 国产区第一页 | 日韩综合在线 | 午夜视频久久久久一区 | 久久91精品国产91久久小草 | 日韩高清第一页 | 特级一级全黄毛片免费 | 日本国产最新一区二区三区 | 欧美a在线视频 | 国产精品系列在线观看 | 中文字幕va一区二区三区 | 国产91精品对白露脸全集观看 | 日韩精品第一 | 日本aⅴ精品一区二区三区久久 | 国产精品福利久久久久久小说 | 国产欧美日韩精品在钱 | 日韩aa在线观看 | 国内精品久久久久久久97牛牛 | 伊人久久中文字幕久久cm | 国产日韩欧美一区二区 | 欧美亚洲精品在线 | 国产成人精品三区 | 欧美啪啪网 | 欧美久久天天综合香蕉伊 | 亚洲视频在线免费播放 | 中文国产成人精品久久一 | 欧美成人视屏 | 91精品一区二区三区久久久久 | 欧美网址在线观看 | 国产精品久久新婚兰兰 | 久操精品在线观看 | 午夜看一级特黄a大片黑 | 欧美日本一区 | 日韩高清dvd|