题解

18 条题解

  • 1
    @ 2019-05-22 23:38:08

    Orz IPIP2005 大佬太强了。

    3ms

    14ms

    2ms

    41ms
    42ms
    40ms

    #include <iostream>
    #include <cstring>
    #include <cmath>
    
    using namespace std;
    
    typedef struct
    {
        int x;
        int y;
        int r;
        int w;
    }cir;
    
    int n,m;
    cir c[1000];
    int ans=0;
    int maxw=0;
    int ll[30001];
    int rr[30001];
    
    int abs(int x)
    {
        if(x<0)
        {
            return -x;
        }
        else
        {
            return x;
        }
    }
    
    int main()
    {
        int i,j,k;
        int l,r,d;
        int a;
        cin>>m>>n>>k;
        ans=n*m;
        for(i=0;i<k;i++)
        {
            cin>>c[i].x>>c[i].y>>c[i].r>>c[i].w;
        }
        for(i=1;i<=n;i++)
        {
            memset(ll,0,sizeof(ll));
            memset(rr,0,sizeof(rr));
            for(j=0;j<k;j++)
            {
                if(abs(i-c[j].x)<=c[j].r)
                {
                    d=sqrt(c[j].r*c[j].r-(i-c[j].x)*(i-c[j].x));
                    l=c[j].y-d;
                    r=c[j].y+d;
                    l=max(1,l);
                    r=min(m,r);
                    ll[l]+=c[j].w;
                    rr[r]+=c[j].w;
                }
            }
            a=0;
            for(j=1;j<=m;j++)
            {
                a+=ll[j];
                if(a>maxw)
                {
                    ans=1;
                    maxw=a;
                }
                else if(a==maxw)
                {
                    ans++;
                }
                a-=rr[j];
            }
        }
        cout<<maxw<<endl<<ans<<endl;
        return 0;
    }
    
  • 1
    @ 2009-03-31 21:44:41

    根据一道线段树题目想到O(NM)的

    把K个圆在每一行的截区间求出来,(c,d),在c处放b[i]左括号,d处放b[i]个右括号,

    即求L[i]-R[i]的最大值,每一行O(M)枚举,总复杂度O(NM);

    只是想到了怕忘记,一定赶上做

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

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

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

    A掉了,MN是有点慢,有N^2的就可以秒杀了

    PS:只处理左边一格有右括号的点,复杂度是O(nk)

  • 0
    @ 2016-05-04 13:08:47

    测试数据 #0: Accepted, time = 0 ms, mem = 756 KiB, score = 10
    测试数据 #1: Accepted, time = 0 ms, mem = 752 KiB, score = 15
    测试数据 #2: Accepted, time = 0 ms, mem = 756 KiB, score = 15
    测试数据 #3: Accepted, time = 125 ms, mem = 756 KiB, score = 20
    测试数据 #4: Accepted, time = 125 ms, mem = 756 KiB, score = 20
    测试数据 #5: Accepted, time = 62 ms, mem = 756 KiB, score = 20

    那个算法好像是O(nklogk)的。。因为要排序。

  • 0
    @ 2009-10-25 16:55:47

    编译通过...

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

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

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

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

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

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

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

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

    扫描法 Orz

  • 0
    @ 2009-06-19 11:59:48

    编译通过...

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

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

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

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

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

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

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

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

    好慢!

  • 0
    @ 2009-06-23 22:54:40

    编译通过...

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

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

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

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

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

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

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

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

    用O(2NM+NLogM)

  • 0
    @ 2009-05-01 15:30:54

    Orz gnaggnoyil 神牛,线段树算法太神了!

    这个题可以枚举每一个横条

    并求出该横条与每个圆的交点横坐标s和t

    开一个数组,把该圆的权值加到a中,

    并从a[t+1]中减去该圆的权值

    然后扫一遍就行了

  • 0
    @ 2009-04-19 23:15:53

    orz curimit神牛

    原来还有O(NK)的方法呀

  • 0
    @ 2009-04-19 18:15:49

    编译通过...

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

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

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

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

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

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

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

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

    奇怪,O(NK)怎么秒不掉呢?

  • 0
    @ 2009-04-16 17:04:20

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

    事实证明ipip2005大牛的方法的确很好,线段树复杂度是O(NMlgM)的,而这个方法只是O(NM)的。

  • 0
    @ 2009-04-06 19:53:40

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

    我的速度怎么这么慢啊?

    正如楼上大牛们所说的:一行一行处理,但是会超时,需要用到线段树。

  • 0
    @ 2009-04-06 00:30:33

    为了防止这题内存爆掉,最好一行一行地做.每次用k个圆来更新这行.然后一行行地处理.

    千万别学我这样,开个a,b:array[1..1000,1..30000]of longint;的数组.

  • 0
    @ 2009-03-31 18:57:17

    按IPIP2005大牛的方法,这题用不着高级数据结构

  • 0
    @ 2009-03-31 09:18:47

    线段树只开30000长的区间

    又不是二维线段树,显然能开出来

  • 0
    @ 2009-03-31 09:48:03

    ...

  • 0
    @ 2009-03-30 18:20:23

    对n离散化,对n个长m的长条做线段树来计算多次对某个区间添加bi后最大值和最大值数.

  • 0
    @ 2009-03-30 14:01:03

    事实证明,模拟只能40分

  • 0
    @ 2009-03-30 13:17:40

    弱弱地问..

    可不可以模拟..

    300亿..

  • 1

信息

ID
1528
难度
5
分类
数据结构 | 线段树组合数学 | 差分 点击显示
标签
(无)
递交数
321
已通过
101
通过率
31%
被复制
2
上传者