40 条题解
-
0
sdsxsz LV 8 @ 2009-06-10 21:43:59
编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
├ 测试数据 06：答案正确... 0ms
├ 测试数据 07：答案正确... 0ms
├ 测试数据 08：答案正确... 0ms
├ 测试数据 09：答案正确... 0ms
├ 测试数据 10：答案正确... 0ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分：100 有效耗时：0ms哈哈哈，第19人。。。。
-
0
编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
├ 测试数据 06：答案正确... 0ms
├ 测试数据 07：答案正确... 0ms
├ 测试数据 08：答案正确... 0ms
├ 测试数据 09：答案正确... 0ms
├ 测试数据 10：答案正确... 0ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分：100 有效耗时：0ms须要那么复杂吗？完全可以根据数据的特性朴素一点。
核心代码：
a[n+1]:=0;
tot:=0;
for i:=n downto 1 do
if a[i]>=a then {直接剪了}
begin
j:=i-1;
min:=maxlongint;
k:=i;
while (j>0) and (a[j] -
0
编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
├ 测试数据 06：答案正确... 0ms
├ 测试数据 07：答案正确... 0ms
├ 测试数据 08：答案正确... 0ms
├ 测试数据 09：答案正确... 0ms
├ 测试数据 10：答案正确... 0ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分：100 有效耗时：0ms这才是我的小号！
-
0
编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
├ 测试数据 06：答案正确... 0ms
├ 测试数据 07：答案正确... 0ms
├ 测试数据 08：答案正确... 0ms
├ 测试数据 09：答案正确... 0ms
├ 测试数据 10：答案正确... 0ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分：100 有效耗时：0ms回复hitman47(s)：是吗？那咱们比比谁的题解写得清楚：
首先，将数列分成连续的若干单调上升的段，这样的每一段都是一个合法的解（长度为1的除外）。
比如：1 10 2 3 5 6 3 7 7 6 5 4
可以分成1 10、2 3 5 6、3 7、7、6、5、4等7段。每个段看作一个元素，每个元素记录四个值：最小高度，最大高度，最左边的编号，最右边的编号。
如上例，7个元素的四个值依次为：
1：1 10 1 2
2：2 6 3 6
3：3 7 7 8
4：7 7 9 9
5：6 6 10 10
6：5 5 11 11
7：4 4 12 12预处理完成后，我们用一个栈维护。
首先，初始化栈，将第一个元素放入栈中。然后依次处理后面的元素。
while栈不为空，弹出栈顶元素。
case1 当弹出的栈顶元素的最小高度大于等于新元素的最小高度时，就用弹出的栈顶元素的最右边的编号－最左边的编号＋1更新答案，前提是最右边的编号>最左边的编号。然后舍弃弹出的栈顶元素。
case2 当弹出的栈顶元素的最小高度小于新元素的最小高度
case2.1 当弹出的栈顶元素的最大高度大于等于新元素的最大高度，将新元素压入栈中，退出while循环。
case2.2 当弹出的栈顶元素的最大高度小于新元素的最大高度，将这两个元素合并成一个元素A，A的最小高度为弹出的栈顶元素的最小高度，A的最大高度为新元素的最大高度，A的最左边编号为弹出的栈顶元素的最左边编号，A的最右边编号为新元素的最右边编号。
如果栈为空了，则新元素无条件压入。处理完所有元素后，将栈中的剩余元素依次弹出，弹出的元素的最右边的编号－最左边的编号＋1更新答案，前提是最右边的编号>最左边的编号。
输出最优解。
-
0
编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
├ 测试数据 06：答案正确... 0ms
├ 测试数据 07：答案正确... 0ms
├ 测试数据 08：答案正确... 0ms
├ 测试数据 09：答案正确... 0ms
├ 测试数据 10：答案正确... 0ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分：100 有效耗时：0ms我就啥也不说了，优先队列。
TSOI又一个！
-
0
Zero.MEGAMAN LV 6 @ 2009-06-06 22:15:55
一个基于路径压缩的方法:
设Next[i]为 Ai之后第一个大于 Ai 的数的下标,特别地,Next[N]=N+1.
Lim[i]为Ai之后第一个不大于Ai的数的下标,特别地,Next[N]=N+1.
这两个序列都可以用路径压缩的方法预处理到
然后枚举左端点i,右端点j从i+1开始,按j=Next[j]的方式步进,并且j -
0
编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
├ 测试数据 06：答案正确... 0ms
├ 测试数据 07：答案正确... 0ms
├ 测试数据 08：答案正确... 0ms
├ 测试数据 09：答案正确... 0ms
├ 测试数据 10：答案正确... 0ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分：100 有效耗时：0ms上帝告诉我们:做事要有恒心!
这道题我终于赶上前五了,从昨天晚上到现在一直都是在想这题.先来说说我的做法:
我是用枚举过的,不过加了许多强力优化.
按左端点枚举,再逐次枚举右端点:优化1:最明显的一个优化:当前枚举的点小于当前序列的左端点时,立刻停止当前序列的枚举,枚举下一个点作为序列的左端点;
(因为这个序列中间的数一定要大于左端点,小于右端点)优化2:也是明显的一个优化:设当前左端点的位置为i,当n-i+1小于当前最优值时直接退出,输出结果;
(越往后的左端点的序列长度不可能超过当前最优值,所以没必要枚举下去,因此直接退出)优化3:不太明显的优化:枚举完当前序列后,可以直接取这个合法序列的右端点的右边的点作为下一个要枚举的序列的右端点;
(因为左端点和右端点中间的数全都大于左端点,小于右端点,所以以这些点作为
左端点得出来的序列一定要小于当前枚举的序列的最大长度)优化4:最不易想到的优化:设当前枚举的序列的左端点为i,max(i..n)为第i个数到第n个数的最大值,那么当枚举到第j个数作为右端点时,若第j个数的值=max(i,n),则直接得出以i为左端点的序列的最长长度为j-i+1
(因为如果再往后枚举右端点,那么往后的右端点的值必定会小于等于max(i,n),但又因为左端点和
右端点中间的数全都大于左端点,小于右端点(不能等于右端点),所以以第i个数为右端点的最大序列长度必定为j-i+1).[怎样快速的得出max(i,n)自己想]至此为止,原来普通枚举的O(n^2)的复杂度已经降了又降,且本人程序只有38行,故能秒杀这道题.
这就是不用线段树等高级数据结构和RMQ等算法的解法,欢迎各位大牛拍砖! -
0
分治
第9个点是极端情况
Ps:我的线段树怎么这么龟速..
过了就好...
编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 103ms
├ 测试数据 05：答案正确... 103ms
├ 测试数据 06：答案正确... 134ms
├ 测试数据 07：答案正确... 87ms
├ 测试数据 08：答案正确... 87ms
├ 测试数据 09：答案正确... 243ms
├ 测试数据 10：答案正确... 446ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分：100 有效耗时：1203ms -
0
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
├ 测试数据 06：答案正确... 0ms
├ 测试数据 07：答案正确... 0ms
├ 测试数据 08：答案正确... 0ms
├ 测试数据 09：答案正确... 0ms
├ 测试数据 10：答案正确... 0ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分：100 有效耗时：0ms
恩，是第七个通过的，本来能成为第二，但是昨天晚上的代码写得很丑，改了一下后就不对了，刚找出错误，用的线性复杂度的方法，好有成就感……
写一下我的题解吧，这道题很多大牛使用了高级数据结构线段树之类的处理方法，其实就用一个优先队列就可以完美AC。数据中的数列，只有单调上升序列才是有用的，所以在读取的时候把数据中所有单调上升序列都找出来，记录四个参数：序列最小值；序列最大值；序列在原数列中的起点；序列在原数列中的终点。每个序列和他的前一个序列谁去谁留呢，这就要用到单调队列，如果后面的序列的最小值小于等于前面序列的最小值，前面的序列就“永无出头之日”——无法和后面的其他序列进行“合并（关于这个“合并”，我是这样定义的：当前一个序列的最小值小于后一个序列的最小值，且后一个序列的最大值大于前一个数据的最大值时，两个序列可以“合并“成一个新序列，这个新序列最小值是前一个序列的最小值，起点是前一个序列的起点，最大值和终点事后一个的，在此题中，这个新序列符合所有已求严格单增序列的”合并“性质，可以把它叫做”伪单增序列“。”合并“就是将两个合法的序列变成一个”伪单增序列“的过程）”，后面的序列就可以取代前面序列在单调队列中的位置，当然在这之前，要先记录一下前面一个（伪）单增序列的长度，更新最大值。如果后面序列的最小值大于前面序列的最小值，那么又分三种情况：1.后面序列的最大值大于前面序列的最大值，这样就可以进行“合并”；2.后大>=前大，前面的序列就可能可以连带着后面的序列，和再后面的序列“合并”，所以，必须将两个序列皆保存下来。
最后要注意，这个方法对整体单调递减数据没有判断，所以返回值是1的话记得要输出0
额……没有队首指针移动，我智商清零了，这是栈……不是优先队列………… -
0
爆 搜 ：
编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
├ 测试数据 06：答案正确... 0ms
├ 测试数据 07：答案正确... 0ms
├ 测试数据 08：答案正确... 0ms
├ 测试数据 09：运行超时...
├ 测试数据 10：运行时错误...| 错误号: 202 | 堆栈溢出错
---|---|---|---|---|---|---|---|-
Unaccepted 有效得分：80 有效耗时：0ms最后 两个点 一个超 时间 一个超 空间 …… 囧
牺牲 解 的最优性 进行 剪枝 后：
├ 测试数据 09：运行超时...
├ 测试数据 10：答案正确... 0ms
---|---|---|---|---|---|---|---|-
Unaccepted 有效得分：80 有效耗时：0ms空间上没问题了 不过 又 WA 了 一个 囧……
TL 一个 WA 一个 其他 秒杀 ……
果然 20 行 的代码 过不 了 难度3 啊 ………… -
0
昨天一直没AC，我以为我方法错了
今天一看，原来线段树写挫了。
我的方法：找最小的和最大的，然后头到最小的和最大的到尾再分别递归处理。
用线段树和人工栈优化
编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
├ 测试数据 06：答案正确... 0ms
├ 测试数据 07：答案正确... 0ms
├ 测试数据 08：答案正确... 0ms
├ 测试数据 09：答案正确... 0ms
├ 测试数据 10：答案正确... 0ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分：100 有效耗时：0ms -
0
hhdllhflower LV 10 @ 2009-06-05 22:55:09
6%的通过率就2个通过？？
我看我还是==再做吧。。。。。
sdsxsz
LV 8
@ 2009-06-10 21:43:59
信息
- ID
- 1548
- 难度
- 7
- 分类
- 数据结构 | 单调队列 点击显示
- 标签
- (无)
- 递交数
- 960
- 已通过
- 161
- 通过率
- 17%
- 被复制
- 3
- 上传者
-
tangkunjie
