题解

19 条题解

  • 1
    @ 2009-10-19 08:46:10

    这题要我用sunny过还是有难度啊

    首先题目没有描述清吧

    应该是找个最长的序列使其包含了1..s中的所有元素吧,当然没有重复的数出现

    然后其中必然包含1吧,抓住1这个元素

    假设最大值在右边则递增r,去除左边重复的点,维护l,如果r-l+1=max(其中最大的数)则更新ans

    同理假设最大值在左边递减l去除右边部行的点

    这题相当好,赞!!!

  • 0
    @ 2017-11-08 10:29:28

    这题目的样例数据没问题么?

  • 0
    @ 2010-03-10 02:43:16

    看了楼下的简短思路。。我自愧不如。我的方法不难写但是想起来很绕,不理清楚思路写不下去。。所以虽然比较短但是写了快2小时。。

    我的做法是这样的:

    如果一个序列最大值等于长度且没有重复元素,那么就是一个合法方案。

    首先求出每个点往右最远能到多少使得无重复的点,然后求出每个点i出发的这样一个序列:第一个元素是点i,第二个元素是i右边中最左边的>a[i]的元素j,第三个是j右边中最左边的>a[j]的元素k..以此类推。,然后如果在这个序列中存在某个元素q(q对应的实际上是下标,令队列中q的后面的一个元素是r)满足:i∈[q-a[q]+1,(r-1)-a[q]+1],则a[q]这个长度是可以取到的。但是枚举判断还是O(n^2),这里我们注意到一个冗余:当队列中元素后继以及本身不变时,对应的[q-a[q]+1,(r-1)-a[q]+1]是不变的,那么我们就可以考虑对于每一个区间,受他影响的i是哪些(显然能受这个区间影响的i一定是i所对应的序列中,q r依然是相邻的元素),可以注意到受区间影响的i一定是连续的,因此枚举判断区间对应的长度,考虑两个区间是否有交即可。O(n)

  • 0
    @ 2009-05-28 21:58:08

    我是先用最小表示法对数据分组

    使每一组内无重复数据

    再递归不断划分

    知道每组的长度=该组内的最大数

    可以用最优性剪枝

  • 0
    @ 2009-04-13 21:08:51

    ├ 测试数据 07:答案正确... 728ms

    ├ 测试数据 08:答案正确... 712ms

    ├ 测试数据 09:答案正确... 712ms

    ├ 测试数据 10:答案正确... 712ms

    ---|---|---|---|---|---|---|---|-

    Accepted 有效得分:100 有效耗时:2864ms

    写的貌似不怎么样

    不过还是过了

  • 0
    @ 2008-10-14 16:41:21

    一样的程序,一样的机子.不一样的分数..

  • 0
    @ 2008-09-27 22:08:10

    嘿嘿 原来的题解被delete了

  • 0
    @ 2008-08-17 13:40:50

    SPOJ原题...

  • 0
    @ 2008-08-11 07:50:58

    O(T*n^2),居然过了,而且表现很好(除了1个点0.9s-其他都0ms)

    数据太随机了。偶自己已经构造出来达到那个平方的数据了。

  • 0
    @ 2008-07-21 12:52:35

    O(N)的差不多都要2s..

    这题细节里挂了不少...自己总是懒得去静态调试(以后得改正)

  • 0
    @ 2008-07-21 11:17:42

    终于AC,20次提交啊

  • 0
    @ 2008-07-19 15:17:35

    我kao, 标程能能超...

  • 0
    @ 2008-07-19 11:12:12

    数据没错

    AC

    第一个

    编译通过...├ 测试数据 01:答案正确... 0ms├ 测试数据 02:答案正确... 0ms├ 测试数据 03:答案正确... 0ms├ 测试数据 04:答案正确... 0ms├ 测试数据 05:答案正确... 0ms├ 测试数据 06:答案正确... 0ms├ 测试数据 07:答案正确... 650ms├ 测试数据 08:答案正确... 619ms├ 测试数据 09:答案正确... 650ms├ 测试数据 10:答案正确... 0ms-------------------------Accepted 有效得分:100 有效耗时:1919ms

  • 0
    @ 2008-07-18 20:28:36

    汗..来晚了

  • 0
    @ 2008-10-14 21:26:34

    写写题解巩固下.

    在读入数据时可以搜索没两个卖一样的食物的店铺中间,如果不能则可以舍掉这个区间.,建一个a数组用来存第I个数在map数组中的第几个.

    当且仅当当前有J 个数,最大值=j时且无重复即为正解,与目前最佳比较下就行了.

    每次搜索从1开始往周围扩展..

    编译通过...

    ├ **测试数据 01:答案正确... 0ms**

    ├ **测试数据 02:答案正确... 0ms**

    ├ **测试数据 03:答案正确... 0ms**

    ├ **测试数据 04:答案正确... 0ms**

    ├ **测试数据 05:答案正确... 0ms**

    ├ **测试数据 06:答案正确... 0ms**

    ├ **测试数据 07:答案正确... 416ms**

    ├ **测试数据 08:答案正确... 525ms**

    ├ **测试数据 09:答案正确... 588ms**

    ├ **测试数据 10:答案正确... 478ms**

    ---|---|---|---|---|---|---|---|-

    Accepted 有效得分:100 有效耗时:2007**ms**

  • 0
    @ 2008-07-18 19:51:43

    地下室的地板

  • 0
    @ 2008-07-20 09:45:07

    ..数据范围我咋看不懂………………

  • -1
    @ 2009-10-09 22:02:55

    编译通过...

    ├ 测试数据 01:答案正确... 0ms

    ├ 测试数据 02:答案正确... 0ms

    ├ 测试数据 03:答案正确... 0ms

    ├ 测试数据 04:答案正确... 0ms

    ├ 测试数据 05:答案正确... 0ms

    ├ 测试数据 06:答案正确... 0ms

    ├ 测试数据 07:答案正确... 384ms

    ├ 测试数据 08:答案正确... 369ms

    ├ 测试数据 09:答案正确... 322ms

    ├ 测试数据 10:答案正确... 306ms

    ---|---|---|---|---|---|---|---|-

    Accepted 有效得分:100 有效耗时:1381ms

    mt orz

  • -1
    @ 2009-08-27 22:51:46

    编译通过...

    ├ 测试数据 01:答案正确... 0ms

    ├ 测试数据 02:答案正确... 0ms

    ├ 测试数据 03:答案正确... 0ms

    ├ 测试数据 04:答案正确... 0ms

    ├ 测试数据 05:答案正确... 0ms

    ├ 测试数据 06:答案正确... 0ms

    ├ 测试数据 07:答案正确... 869ms

    ├ 测试数据 08:答案正确... 916ms

    ├ 测试数据 09:答案正确... 916ms

    ├ 测试数据 10:答案正确... 916ms

    ---|---|---|---|---|---|---|---|-

    Accepted 有效得分:100 有效耗时:3617ms

    我好怕怕,好恐怖的时间。。。。。。

    乱七八糟的几个优化加几个弱弱的剪枝,发现自己原来只是一个菜鸟,5KB200行,强烈膜拜voyagec2神牛!!!!!!

  • 1

信息

ID
1381
难度
7
分类
其他 | 数学 点击显示
标签
(无)
递交数
137
已通过
23
通过率
17%
被复制
2
上传者