考试策略

这个里面的花,我看了一下,啊,T2和T3是比较简单的原题啊,匆匆写完过了对拍,看了一下T4,T4有思路但是这个离散太恶心了有点思考不清楚,怕写错就打了暴力。T1完全没思路就打了暴力。

T1

期望得分:20 实际得分:0
题目描述
我们生活的星球对于整个宇宙来说,只不过是沧海一粟,宇宙到底有多大,到现在还没人知道,其实我们无时无刻不在面临着来自外太空的威胁,当然你也不会知道在我们的身边,有很多人自愿参加了一个叫 FLYIOI 的秘密组织,QZC 就是其中一员,公元 2007 年 4 月 21日早上 8:00,他截获了一份来自外太空的信息,这份信息是一大串毫无规律的数字,在众多大牛的努力帮助之下,QZC终于发现这是来自OIBH星球的一份密文,由于QZC经常去OIBH星球参观访问,附带潜水旅游,所以很快知道了他的加密格式。
密文的格式如下:
在第一行有两个数,不妨设为 N,M。
第二行有 N 个数,设为 a1,a2,……,an。
接下来有 M 行,每行有三个数字设为 x,y,z。
如果对于 M 行的每一行 x,y,z,得到一个数字 Q,Q 代表有多少个不同的数字,在 ax…ay和 ay+1…az 中都不得出现过,将这 M 个数字顺次连起来,就是解密后的信息。保卫世界和平的任务就落在你的肩上了,请你编写一个数字统计程序来解开来自 OIBH 星球的密文。
数据范围
对于 20%的数据,N<=1000,M<=1000;
对于 100%的数据,N<=200000,M<=40000;0<=ai<=Maxlongint。
题目分析
感谢pyh大佬的帮助。
pyh大佬说,假如某一元素在序列里出现了若干次,位置为a1,a2...an,我们就在平面上建立点(a1,a2),(a2,a3),(a3,a4)....[我的思路是离散出现的数字]
然后对于每一个询问(x,y,z),建立一个左上角坐标为(x,z),右下角坐标为(y,y+1)的矩形,然后求里面的点的数量即可。
为什么呢?因为我们要求相同元素的两个区间是相邻的,所以我们从左区间拿一个该元素,右区间拿一个,如果他们中间还有一个该元素,就不会被计算,如果没有,才会被计算。这就皆大欢喜了,不会重复计算元素呢。
那么我们要怎么求呢?pyh大佬提供的思路是扫描线。对于每一个矩形,我们可以看作是在其右边界限以前的所有点数-在其左边界限以前的所有点数。这样我们把点和矩形的线从小到大排个序后,加点进一个树状数组,加的位置是其y坐标的位置,然后看矩形的界限上下y坐标统计点的个数,即可很快的求出答案。
最后%%%pyh大佬。
代码

T2

期望得分:100 实际得分:100
题目描述
由于你即将参加选拔赛,会有麻烦的问题等你解决,不过之前,我们还是请你先解决下面的问题,问题很简单:
有一个长度为 L 的长木板,将其均匀的分成 L 段,从 1...L 标号,可以对木板进行下列两种操作
C(A, B, C) 将第 A 段到第 B 段全部涂成颜色 C
P(A, B) 计算第 A 段到第 B 段间不同的颜色数(包含 A 和 B 段)
颜色从 1..T 开始顺次表示,最开始的时候整个木板被涂成颜色 1。
数据范围
第一行 L(1≤L≤100000), T(1≤T≤30), O(1≤O≤10000)表示木板的段数,颜色总数和
操作的个数。接下来 O 行,每行包含上述两种操作之一。
题目分析
状态压缩,用一个二进制数来表示一段区间内颜色的集合,最后求出颜色集合,并统计其中颜色个数即可。
有一个坑点,就是数据里有右区间大于左区间的情况,要注意特判。
代码

T3

期望得分:100 实际得分:100
题目描述
XXX 最近的旅游计划,是到 XXXX 湖畔,享受那里的湖光山色,以及明媚的阳光。你作为整个旅游的策划者和负责人,选择在湖边的一家著名的旅馆住宿。这个巨大的旅馆一共有N (1 <= N <= 50000)间客房,它们在同一层楼中顺次一字排开,在任何一个房间里,只需要拉开窗帘,就能见到波光粼粼的湖面。
所有的旅游者,都是一批批地来到旅馆的服务台,希望能订到 Di (1 <= Di <= N)间连续的房间。服务台的接待工作也很简单:如果存在 r 满足编号为 r..r+Di-1 的房间均空着,他就将这一批顾客安排到这些房间入住;如果没有满足条件的 r,他会道歉说没有足够的空房间,请顾客们另找一家宾馆。如果有多个满足条件的 r,服务员会选择其中最小的一个。
旅馆中的退房服务也是批量进行的。每一个退房请求由 2 个数字 Xi、Di 描述,表示编号为 Xi..Xi+Di-1 (1 <= Xi <= N-Di+1)房间中的客人全部离开。退房前,请求退掉的房间中的一些,甚至是所有,可能本来就无人入住。
你的工作,就是写一个程序,帮服务员为旅客安排房间。你的程序一共需要处理 M (1 <=M <=50000)个按输入次序到来的住店或退房的请求。第一个请求到来前,旅店中所有房间都是空闲的。
题目分析
区间线段树,维护一个区间从左边开始数最多连续空房数量和从右边开始数的,那么对于一个区间[x,y],将其分为[x,mid]和[mid+1,y]后,最多连续空房数是左边区间最多连续空房数,右边区间最多连续空房数,跨越两个子区间的最多连续空房数的最大值。
这样就easy了,退房很简单,入住的花只要左区间房间苟去左区间找,否则看跨越两个子区间的区间,否则看右区间这样的顺序寻找即可。注意寻找的时候如果找到了一个s==t(意思看代码),要return否则会RE
代码

T4

期望得分:50 实际得分:52
题目描述
Mountain Amusement公园新添了一台过山车,模拟轨道由n个首尾相连的铁轨构成,第一根铁轨的首端的高度为0。操作员Byteman可以随意调整一些铁轨两端的高度差,而其他铁轨两端的高度差不受影响。每当一根铁轨的高度差被调整后,与它相连的下一根铁轨将相应地被抬高或被降低,而其首端与前一根铁轨的尾端高度差仍然为0。下一页的图示说明了轨道调整的两个例子。
过山车的每次运行都被赋予能达到高度h的能量。这就是说,只要高度不超过h,过山车就将一直前进,直至终点。给出每天过山车运行和轨道调整的记录,计算出每次过山车在停止前通过的轨道的长度。
在内部,模拟器将轨道表示为n段铁轨两端高度差的序列。第i个数di表示第i段铁轨两端的高度差(单位为厘米)。假定在通过第i−1段铁轨后的过山车的高度为 h厘米,在经过第i段铁轨后,其高度将达到h+di厘米。
开始时所有的铁轨都是水平的,也就是说,对所有的i, di = 0。过山车的运行和轨道的调整在一天之中交错进行。每次轨道调整由三个数描述,a、b、和D。被调整的区间包含
从a到b的所有铁轨(a和b都包括在内)。区间内的每根铁轨两端的高度差都被设置为D。这也就是说,对于所有的a<= i<= b , di = D 。
每一次过山车的运行用一个数h来表示过山车所能到达的最大高度。
任务
写出程序
从标准输入上读入交错输入的轨道调整和过山车运行的数据。
对过山车的每一次运行,计算它所能通过的铁轨的数量。
将结果写到标准输出上。
数据范围
输入第一列包含一个正整数n,1 <= n <=1,000,000,000,表示过山车的运行次数。以
下各行交错包含着轨道调整和过山车运行的数据,以及结束符。每一行可以是下列情况之一:
- 轨道的调整:单个字符 “I” 以及整数a, b和D,及由单个空格符分隔(1 <= a <= b
<= n, −1,000,000,000 <= D <= 1,000,000,000)。
- 过山车的运行:单个字符 “Q” 和整数h (0 <= h <= 1,000,000,000)由单个空格
符分隔。
- 单个字符 “E”:结束符。说明输入数据结束。
你可以假定在任何时候,任何点的高度都在[0, 1,000,000,000]厘米之内。输入数据不超
过100,000行。
50%的数据保证1 <=n <=20,000,以及输入数据不超过1,000行。


题目分析
一开始虽然想到了线段树解法,但奈何离散使我面目全非,最后只打了暴力......
那么这个里面的花,离散要怎么搞呢?
离开了代码根本不好讲,大约是首先将所有修改区间弄成左闭右开区间(为什么之后就知道了),然后离散要用到的区间节点,离散数组a,线段树中[s,t]表示[a[s],a[t]-1]这一段(明白为什么是左闭右开了吧),这样线段树左右子树应该是[s,mid]和[mid,t]而不是我们常用的[s,mid]和[mid+1,t]。
然后线段树维护的是表明每一个铁轨左右高度差的数组,需要维护:sum区间和,ma区间高度最大值。注意,如果我们只考虑[s,t]区间,我们可以运用物理里常说的”转换参考系“的技巧,即把最左端的铁轨的左端看作高度为0.这样的花在pushup这个ma的时候应该是:ma[i]=max(ma[左子树],sum[左子树]+ma[右子树]),以此类推。
然后查询时,如果左边区间的ma要比h高的花,车在左边区间就停下来了,就去左边区间找,否则去右边找,并根据参考系的调整对一些参数进行相应的调整(具体看代码)
这题在实现上有很多值得注意的细节,都在代码里打出注释表明了。


代码: