小明虽为�丝级码农,但非常活跃,女神们常常在小明网上的大段发言后热情回复“呵呵”,所以,小明的最爱就是和女神们约会。与此同时,也有很多基友找他开黑,由于数量实在过于巨大,怎么安排时间便成了小明的一大心事。
我们已知小明一共有T的空闲时间,期间会有很多女神或者基友来找小明。
作为一个操作系统曾经怒考71分的大神,小明想到了一个算法,即“首次适应算法”,根据操作系统课本的描述,就是找一段最靠前的符合要求的连续空间分配给每个请求,由此小明做出了一个决定:
当一个基友来找小明时,小明就根据“首次适应算法”来找一段空闲的时间来和基友约好,如果找到,就说“X,let’s fly”(此处,X为开始时间),否则就说“fly with yourself”;
当女神来找小明时,先使用一次“首次适应算法”,如果没有找到,小明就冒着木叽叽的风险无视所有�丝基友的约定,再次使用“无视基友首次适应算法”,两次只要有一次找到,就说“X,don’t put my gezi”(此处,X为开始时间),否则就说“wait for me”
当然,我们知道小明不是一个节操负无穷的人,如果和女神约会完,还有剩余时间,他还是会和原来约好的基友去dota的。(举个例子:小西(�丝)和小明约好在1~5这个时间单位段内打dota,这时候,女神来和小明预约长度为3的时间段,那么最终就是1~3小明去和女神约会,搞定后在4~5和小西打dota)
小明偶尔也会想要学习新知识,此时小明就会把某一个时间区间的所有已经预定的时间全部清空用来学习并且怒吼“I am the hope of chinese chengxuyuan!!”,不过小明一般都是三分钟热度,再有人来预定的话,小明就会按耐不住寂寞把学习新知识的时间分配出去。
Input
每组数据以两个整数T,N开始,T代表总共的时间,N表示预约请求的个数;
接着的N行,每行表示一个女神或者基友的预约,“NS QT”代表一个女神来找小明约一段长为QT的时间,“DS QT”则代表一个�丝的长为QT的请求,当然也有可能是小明想学知识了,“STUDY!! L R”代表清空L~R区间内的所有请求。
[Technical Specification]
1. 1 <= CASE <= 30
2. 1 <= T, N <= 100000
3. 1 <= QT <= 110000
4. 1 <= L <= R <=T
Output
输出样本(可复制此处):
“X,let's fly”,”fly with yourself”,”X,don't put my gezi”,”wait for me”,”I am the hope of chinese chengxuyuan!!”
Sample Input
1 5 6 DS 3 NS 2 NS 4 STUDY!! 1 5 DS 4 NS 2
Sample Output
Case 1: 1,let's fly 4,don't put my gezi wait for me I am the hope of chinese chengxuyuan!! 1,let's fly 1,don't put my gezi
#include<algorithm>
#include<stdio.h>
#include<stack>
#include<string.h>
using namespace std; #define lson r<<1
#define rson r<<1|1 const int maxn = 1e5+; struct segmentTree
{///bool操作分别代表 女神屌丝,学习
int L, R, lsum[], rsum[], sum[];///0是屌丝,1是女神
bool ns, ds, study; int mid(){return (L+R)>>;}
int len(){return R-L+;}
void clearPlan(int fstudy)
{///准备学习,清空所有计划
if(fstudy == true)
{
lsum[] = lsum[] = len();
rsum[] = rsum[] = len();
sum[] = sum[] = len();
study = true; ds = ns = false;
}
}
void Plmm(int fns)
{///女生占用时间,屌丝无法占用
if(fns == true)
{
lsum[] = lsum[] = ;
rsum[] = rsum[] = ;
sum[] = sum[] = ;
ns = true, ds = false;
}
}
void DiaoSi(int fds)
{///屌丝一起打游戏占用时间,可被女神再次占过来
if(fds == true)
{
lsum[] = rsum[] = sum[] = ;
ds = true;
}
}
}a[maxn<<]; void Build(int r, int L, int R)
{
a[r].L = L, a[r].R = R;
a[r].clearPlan();
a[r].study = a[r].ds = a[r].ns = false; if(L == R)return ; Build(lson, L, a[r].mid());
Build(rson, a[r].mid()+, R);
}
void pushDown(int r)
{
if( a[r].study )
{
a[lson].clearPlan(true);
a[rson].clearPlan(true);
a[r].study = false;
} if( a[r].ns )
{
a[lson].Plmm(true);
a[rson].Plmm(true);
a[r].ns = a[r].ds = false;
} if( a[r].ds )
{
a[lson].DiaoSi(true);
a[rson].DiaoSi(true);
a[r].ds = false;
}
}
void pushUp(int r, int k)
{///k等于 0 更新屌丝区间, 等于1更新女神区间
a[r].lsum[k] = a[lson].lsum[k], a[r].rsum[k] = a[rson].rsum[k]; if( a[lson].lsum[k] == a[lson].len() )
a[r].lsum[k] += a[rson].lsum[k];
if( a[rson].rsum[k] == a[rson].len() )
a[r].rsum[k] += a[lson].rsum[k]; a[r].sum[k] = max( a[lson].sum[k], max( a[rson].sum[k], a[lson].rsum[k] + a[rson].lsum[k] ) );
}
///op等于1时学习,2女神,3屌丝
void upDate(int r, int L, int R, int op)
{
if( a[r].L == L && a[r].R == R )
{
if(op == ) a[r].clearPlan(true);
if(op == ) a[r].Plmm(true);
if(op == ) a[r].DiaoSi(true); return ;
} pushDown(r); if(R <= a[r].mid())
upDate(lson, L, R, op);
else if(L > a[r].mid())
upDate(rson, L, R, op);
else
{
upDate(lson, L, a[r].mid(), op);
upDate(rson, a[r].mid()+, R, op);
} pushUp(r, );
pushUp(r, );
}
///查找女神或者屌丝是否有k时间,k等于0屌丝,1女神,有的话返回下标没有返回0
int Query(int r, int t, int k)
{
pushDown(r); if( a[r].sum[k] < t )return ; if( a[r].lsum[k] >= t)return a[r].L;
if( a[lson].sum[k] >= t ) return Query(lson, t, k);
if( a[lson].rsum[k] + a[rson].lsum[k] >= t )
return a[lson].R - a[lson].rsum[k] + ;
return Query(rson, t, k);
} int main()
{
int T, t=; scanf("%d", &T); while(T--)
{
int N, M, x, y; char s[]; scanf("%d%d", &N, &M); Build(, , N); printf("Case %d:\n", t++); while(M--)
{
scanf("%s%d", s, &x); if(s[] == 'S')
{
scanf("%d", &y);
upDate(, x, y, );
printf("I am the hope of chinese chengxuyuan!!\n");
}
else if(s[] == 'N')
{
y = Query(, x, );
if(!y) y = Query(, x, ); if(y)
{
upDate(, y, y+x-, );
printf("%d,don't put my gezi\n", y);
}
else
printf("wait for me\n");
}
else
{
y = Query(, x, ); if(y)
{
upDate(, y, y+x-, );
printf("%d,let's fly\n", y);
}
else
printf("fly with yourself\n");
}
}
} return ; }
M - 约会安排 - hdu 4553的更多相关文章
-
E - Tunnel Warfare HDU - 1540 F - Hotel G - 约会安排 HDU - 4553 区间合并
E - Tunnel Warfare HDU - 1540 对这个题目的思考:首先我们已经意识到这个是一个线段树,要利用线段树来解决问题,但是怎么解决呢,这个摧毁和重建的操作都很简单,但是这个查询怎么 ...
-
约会安排HDU - 4553
寒假来了,又到了小明和女神们约会的季节. 小明虽为屌丝级码农,但非常活跃,女神们常常在小明网上的大段发言后热情回复"呵呵",所以,小明的最爱就是和女神们约会.与此同时,也有很多基 ...
-
约会安排 HDU - 4553(线段树区间查询,区间修改,区间合并)
题目: 寒假来了,又到了小明和女神们约会的季节. 小明虽为屌丝级码农,但非常活跃,女神们常常在小明网上的大段发言后热情回复“呵呵”,所以,小明的最爱就是和女神们约会.与此同时,也有很多基友找他开黑, ...
-
M - 约会安排 HDU - 4553 线段树 (最长连续段)
中文题面 思路:维和两个区间 一个是女神区间 一个是基友区间 如果是基友要预约时间 直接在基友区间查询可满足的起点 (这里先判tree[1].m >=length也就是有没有这样的区间满足时 ...
-
hdu 4553 约会安排
约会安排 http://acm.hdu.edu.cn/showproblem.php?pid=4553 Time Limit: 2000/1000 MS (Java/Others) Memory ...
-
hdu 4453 约会安排(线段树区间合并)
约会安排 Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65535/32768 K (Java/Others)Total Submis ...
-
HDU 4553 约会安排(线段树区间合并+双重标记)
题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=4553 题目大意:就是有三种操作: ①DS x,安排一段长度为x的空闲时间跟屌丝一起,输出这段时间的起点 ...
-
HDU - 4553 约会安排(区间合并)
https://cn.vjudge.net/problem/HDU-4553 Description 寒假来了,又到了小明和女神们约会的季节. 小明虽为屌丝级码农,但非常活跃,女神们常常在小明网上的 ...
-
HDU 4553 约会安排 (区间合并)【线段树】
<题目链接> 寒假来了,又到了小明和女神们约会的季节. 小明虽为屌丝级码农,但非常活跃,女神们常常在小明网上的大段发言后热情回复“呵呵”,所以,小明的最爱就是和女神们约会.与此同时,也有 ...
随机推荐
-
C#解决界面不响应
在我们的程序中,经常会有一些耗时较长的运算,为了保证用户体验,不引起界面不响应,我们一般会采用多线程操作,让耗时操作在后台完成,完成后再进行处理或给出提示,在运行中,也会时时去刷新界面上的进度条等显示 ...
-
if语句解一元二次方程~
#include<stdio.h>#include<math.h> void main(){ double a,b,c,x1,x2; printf("请输入a&q ...
-
java EE 学习
http://blog.csdn.net/liushuijinger/article/category/1342030/1
-
vultr机房vps价格20%优惠,赶紧来抢!
vps服务商vultr全线优惠促销!价格降幅是20%,强烈推荐站长们留意. vps猫腻很多,我写过大量文章介绍vps的优点和几大厂商情况.友情提醒,千万不要采购国内所谓vps云主机,你的数据很不安全哟 ...
-
Java基础语法(一)---关键字、常量、变量、运算符
一.关键字 定义:被Java赋予了特殊含义的单词. 特点:体现上都是英文小写. 1. 用于定义数据类型的关键字 基本数据类型: 整数类型:byte short int long 浮点类型:f ...
-
Python递归函数
参考: https://pythonspot.com/recursion/ https://www.python-course.eu/recursive_functions.php 一.递归函数两大要 ...
-
20175204 张湲祯 2018-2019-2《Java程序设计》第七周学习总结
20175204 张湲祯 2018-2019-2<Java程序设计>第七周学习总结 教材学习内容总结 -第八章常用实用类要点: 一.String类: 1.String类所在的包:java. ...
-
Fiddler抓包使用教程-Https
转载请标明出处:http://blog.csdn.net/zhaoyanjun6/article/details/72956016 本文出自[赵彦军的博客] 开启 Https 抓包 Fiddler 默 ...
-
Groovy实现代码热载的机制和原理
前言: 真的很久没在博客园上更新博客了, 现在趁这段空闲的时间, 对之前接触的一些工程知识做下总结. 先来讲下借用Groovy如何来实现代码的热载, 以及其中涉及到的原理和需要注意的点. 总的来说, ...
-
谁说delphi没有IOCP库,delphi新的IOCP类库,开源中
DIOCP Demo说明 下载地址 https://code.google.com/p/diocp/ 特地为DIOCP开设了一个群:320641073,欢迎学习的IOCP的童鞋进入讨论. 核心作者: ...