- 浏览: 381252 次
- 性别:
- 来自: 北京
文章分类
- 全部博客 (229)
- java编程 (4)
- java实用程序 (2)
- 算法设计 (34)
- 数据库 (8)
- ACM模板 (12)
- 技术术语 (1)
- java_web (3)
- php (22)
- eclipse (3)
- linux (25)
- linux命令使用心得 (3)
- web服务器 (8)
- IT知识 (2)
- 前端技术 (17)
- 开源软件 (5)
- vim (3)
- linux多线程 (9)
- web开发经验 (3)
- lua (5)
- linux编程 (3)
- smarty (1)
- mysql (4)
- Hive (2)
- 数据挖掘 (9)
- python (2)
- 生活 (1)
- C++ (2)
- 计算机 (1)
- objective-c (11)
- css (2)
- 游戏 (1)
- Mac (1)
最新评论
-
lr544463316:
我的怎么不行呀.....
Mysql Access denied for user ''@'localhost' to database 的一种解决方法 -
babaoqi:
使用时需要注意group_concat函数返回值的最大长度=g ...
mysql中的group_concat函数 -
代码能力弱成渣:
可以帮我看下我的代码么?我自己写的sam,也有ac过题的,但是 ...
求两个字符串的最长公共连续子序列(SAM实现) -
atgoingguoat:
有1000个?不过还是收藏下。
jquery常用的插件1000收集(转载)
线段树即可解决这个题。向线段树插入一个车阵的时候,只需要插入车阵的最左边的点p(姑且称这些点为黑点)即可,
len[p]记录这个车阵的长度(len数组的作用不仅仅是这些,当p这个位置为空白时,len[p]
表示从p位置开始往右的一段空白的长度)。seg结构里的lp,rp,表示区间[l, r]的黑点的位置的最小值和最小值,
sum表示黑点的总和。而minPos有点不一样,minPos表示的是长度在[l, r]之间的连续的空白段的左端点的最小值
(理解这个很重要)。
#include <iostream> #include <stdio.h> #include <set> using namespace std; const int N = 50005; const int INF = 0X7FFFFFFF; struct seg{ int l, r; int lp, rp, minPos; int sum; bool leaf(){ return l == r; } int mid(){ return (l+r)>>1; } }segs[N<<2]; set<int> pos[N]; int len[N]; int n, q; template <typename T> void getNum(T& a){ a = 0; char ch; while(true){ ch = getchar(); if(ch >= '0' && ch <= '9') break; } a = ch - '0'; while(true){ ch = getchar(); if(ch < '0' || ch > '9') break; a = a * 10 + ch - '0'; } } bool input(){ scanf("%d%d", &n, &q); return true; } inline bool check(int i){ return i >= 1 && i <= n; } inline int ls(int id){ return (id<<1)+1; } inline int rs(int id){ return (id<<1)+2; } void build(int id, int l, int r){ segs[id].l = l; segs[id].r = r; segs[id].lp = n+1; segs[id].rp = 0; segs[id].minPos = INF; segs[id].sum = 0; if(l < r){ int mid = segs[id].mid(); build(ls(id), l, mid); build(rs(id), mid+1, r); }else{ pos[l].clear(); } } void insBlank(int id, int p, int tlen, bool flag){ //flag为true表示添加,为false表示删除 //在p位置插入(删除)一段长度为tlen的空白段。 if(segs[id].leaf()){ if(flag){ pos[tlen].insert(p); len[p] = tlen; }else{ pos[tlen].erase(p); } if(pos[tlen].size() > 0){ segs[id].minPos = *pos[tlen].begin(); }else{ segs[id].minPos = INF; } return ; } if(tlen <= segs[id].mid()){ insBlank(ls(id), p, tlen, flag); }else{ insBlank(rs(id), p, tlen, flag); } segs[id].minPos = min(segs[ls(id)].minPos, segs[rs(id)].minPos); } void insCars(int id, int p, bool flag){ //flag为true表示添加,为false表示删除 //在位置p插入(或删除)一个黑点 if(segs[id].leaf()){ if(flag){ segs[id].sum++; }else{ segs[id].sum--; } if(segs[id].sum == 0){ segs[id].lp = n+1; segs[id].rp = 0; }else{ segs[id].lp = segs[id].l; segs[id].rp = segs[id].l; } return ; } if(p <= segs[id].mid()){ insCars(ls(id), p, flag); }else{ insCars(rs(id), p, flag); } segs[id].sum = segs[ls(id)].sum + segs[rs(id)].sum; segs[id].lp = min(segs[ls(id)].lp, segs[rs(id)].lp); segs[id].rp = max(segs[ls(id)].rp, segs[rs(id)].rp); } int qryBlank(int id, int l, int r){ //查询长度在[l, r]之间的空白段的起点的最小值 if(l <= segs[id].l && segs[id].r <= r){ return segs[id].minPos; } if(segs[id].leaf()) return INF; int mid = segs[id].mid(); if(r <= mid) return qryBlank(ls(id), l, r); else if(l > mid) return qryBlank(rs(id), l, r); else{ return min(qryBlank(ls(id), l, r), qryBlank(rs(id), l, r)); } } int getl(int id, int l, int r){ //获取区间[l,r]最左的黑点的位置 if(l <= segs[id].l && segs[id].r <= r){ return segs[id].lp; } if(segs[id].leaf()) return n+1; int mid = segs[id].mid(); if(r <= mid) return getl(ls(id), l, r); else if(l > mid) return getl(rs(id), l, r); else return min(getl(ls(id), l, r), getl(rs(id), l, r)); } int getr(int id, int l, int r){ //取区间[l,r]最右的黑点的位置 if(l <= segs[id].l && segs[id].r <= r){ return segs[id].rp; } if(segs[id].leaf()) return 0; int mid = segs[id].mid(); if(r <= mid) return getr(ls(id), l, r); else if(l > mid) return getr(rs(id), l, r); else return max(getr(ls(id), l, r), getr(rs(id), l, r)); } int getPos(int m, int l, int r){ if(m > n) return INF; if(segs[0].sum == 0){ return 1; } int pos; pos = segs[0].lp; if(pos - 1 >= m){ return max(pos - r - m, 1); } pos = qryBlank(0, m, m+l+r); if(pos <= n){ int tr = getl(0, pos, n); if(tr < 1) tr = n + 1; if(tr < n+1){ //右边还有车阵 pos = max(pos, tr-r-m); } return pos; } pos = segs[0].rp + len[segs[0].rp] - 1; if(n - pos >= m){ return pos+1; } return INF; } void ins(int p, int m, bool flag){ //flag为true表示插入一排车,为false表示离开 int l, r; if(p == 1){ l = 0; }else{ l = getr(0, 1, p - 1); if(!check(l)) l = 0; else{ l = l + len[l] - 1; } } if(p+m-1 == n){ r = n+1; }else{ r = getl(0, p+m, n); if(!check(r)) r = n+1; } if(r-l-1 > 0){ insBlank(0, l+1, r-l-1, !flag); } if(p-l-1 > 0){ insBlank(0, l+1, p-l-1, flag); } if(r-p-m > 0){ insBlank(0, p+m, r-p-m, flag); } } int qrykth(int id, int k){ //查询第k个黑点的位置 if(segs[id].leaf()) return segs[id].l; if(segs[ls(id)].sum >= k) return qrykth(ls(id), k); return qrykth(rs(id), k-segs[ls(id)].sum); } int cnt = 0; void solve(){ build(0, 1, n); insBlank(0, 1, n, true); int i, m, l, r, k; char op[3]; printf("Case #%d:\n", ++cnt); for(i = 1; i <= q; i++){ scanf("%s", op); if(op[0] == 'A'){ getNum(m); getNum(l); getNum(r); int p; p = getPos(m, l, r); if(p <= n){ printf("%d\n", p); ins(p, m, true); insCars(0, p, true); len[p] = m; }else{ printf("-1\n"); } }else{ getNum(k); if(k <= segs[0].sum){ int p = qrykth(0, k); ins(p, len[p], false); insCars(0, p, false); } } } } int main() { //freopen("in.txt", "r", stdin); int t; scanf("%d", &t); while(t--){ input(); solve(); } return 0; }
发表评论
-
升序数组中求一个key出现的次数
2013-01-09 23:08 1072算法思路: 在排好序的数组,相同的数字是排列在一起的,所以只需 ... -
判断单链表是否有环
2013-01-08 19:07 892算法思路: 指针p1和p2的起始值均为链表的表头,指针p1每次 ... -
hdu3684
2011-11-15 20:11 900/* 刚开始打了个记录上下左右四个点的,一直tle。 ... -
hdu3686
2011-11-14 20:43 1011/* 无向图边的双连通分量,在同一个连通分量里的边之间 ... -
poj3968
2011-11-14 04:45 1385source: http://poj.org/problem ... -
uva2819
2011-11-13 02:20 867source: http://livearchive.onli ... -
manacher算法
2011-11-11 00:06 2413const int LEN=110005; const ... -
hdu4118
2011-11-09 21:53 1167枚举每条边最多被经过的次数即可 #include ... -
hdu4115
2011-11-09 16:27 1005source: http://acm.hdu.edu.cn/ ... -
uva(Transitive Closure)
2011-11-08 14:45 889source: http://livearchive.onli ... -
zoj3500
2011-11-07 17:41 930求两个球的体积交或者并 #include <cs ... -
zoj3545
2011-11-04 18:18 846/* AC自动机 相当暴力的 解法: mark[i ... -
zoj3190
2011-11-04 17:34 1262/* * AC自动机,先对资源串和病毒串构成的字符串 ... -
zoj3228
2011-11-04 16:12 930/* * AC自动机,每个节点 添加一个d表示节点代 ... -
poj3691(DNA Repair)
2011-11-04 13:18 1456/* AC自动机,增设虚拟节点,求长度为n的字符串中包 ... -
hdu2825
2011-11-04 11:53 963/* AC自动机,增设虚拟节点,求长度为n的字符 ... -
hdu4095
2011-11-03 13:19 993/* 第一步,构建BST,用第一个数作为bst的 ... -
zoj3540
2011-11-02 21:33 897/* 其实就是把总共的 放置次数减去不能放置的那些就行 ... -
poj1741(树的分治,基于边的 分治)
2011-11-02 20:25 3329/* 树基于边的分治算法,计算树中距离小于等于k的点 ... -
hdu2939
2011-10-29 18:36 830source: http://acm.hdu.edu.cn/s ...
相关推荐
HDU的1250,主要是利用高精度加法,但是代码有点繁琐,效率不是很高
HDU1059的代码
杭电ACMhdu1163
hdu1001解题报告
hdu 1574 passed sorce
HDU的一题........HDU DP动态规
hdu acm 教案 搜索入门 hdu acm 教案 搜索入门
hdu2101AC代码
搜索 dfs 解题代码 hdu1241
hdu acm 教案 动态规划(1) hdu acm 教案 动态规划(1)
ACM HDU题目分类,我自己总结的大概只有十来个吧
hdu 5007 Post Robot 字符串枚举。 暴力一下就可以了。
hdu1290 解题报告 献给杭电五十周年校庆的礼物 (切西瓜问题,即平面分割空间)
HDU最全ac代码
hdu 1166线段树代码
hdu动态规划算法集锦
hdu-acm源代码(上百题)hdu-acm源代码、hdu-acm源代码hdu-acm源代码
hdu题目分类
自己做的HDU ACM已经AC的题目
HDU图论题目分类