Codeforces Round #220 (Div. 2) D 树状数组 && 二分_html/css_WEB-ITnose
题意:给了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 0) { sum += c[i]; i -= lowbit(i); } return sum;}void binary_find(int pos,int id) { int l = 1; int r = n; while(l >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 >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
上一篇: 小强的HTML5移动开发之路(45)——汇率计算器【1】
下一篇: 简单演示procedure
推荐阅读
-
Codeforces Round #256 (Div. 2)D 二分答案_html/css_WEB-ITnose
-
Codeforces Round #132 (Div. 2) D. Hot Days_html/css_WEB-ITnose
-
Codeforces Round #274 (Div. 2) D. Long Jumps_html/css_WEB-ITnose
-
Codeforces Round #277 (Div. 2)D(树形DP计数类)_html/css_WEB-ITnose
-
Codeforces Round #281 (Div. 2) (A、B、C、D题)_html/css_WEB-ITnose
-
Codeforces Round #277.5 (Div. 2) D??Unbearable Controversy of Being_html/css_WEB-ITnose
-
Codeforces Round #262 (Div. 2)-A,B,C,D_html/css_WEB-ITnose
-
Codeforces Round #279 (Div. 2) d_html/css_WEB-ITnose
-
Codeforces Round #245 (Div. 2)D(树的性质+状压+dfs)_html/css_WEB-ITnose
-
Codeforces Round #245 (Div. 2)D(树的性质+状压+dfs)_html/css_WEB-ITnose