43 条题解

  • 3
    @ 2017-05-30 16:16:05

    正解应该是差分约束,但是因为题目数据特殊性,可以用贪心

    #include<stdio.h>
    #include<algorithm>
    struct dx{ int b,e,v; } s[3010]; bool v[5010];
    inline bool c1(dx a,dx b){ return a.e==b.e?a.b<b.b:a.e<b.e; }
    int main(){
        int n,m,a=0;
        scanf("%d%d",&n,&m);
        for(int i=0;i<m;++i)
            scanf("%d%d%d",&s[i].b,&s[i].e,&s[i].v);
        std::sort(s,s+m,c1);
        for(int i=0;i<m;++i){
            for(int j=s[i].b;j<=s[i].e;++j) s[i].v-=v[j];
            for(int j=s[i].e;s[i].v>0;--j)
                if(!v[j]) { v[j]=1; s[i].v--; ++a; }
        }
        printf("%d\n",a);
    }
    

    查分约束:

  • 1
    @ 2020-11-13 08:55:17

    題解(差分約束系統)
    設從第0格到第i格一共種植X(i)個🍉

    X(i-1)<=Xi<=X(i-1)+1(1<=i<=n),
    0<=X(i)<=i(0<=i<=n),
    對任意B,E,T有X(E)-X(B-1)>=T
    求X(n)的最小值,將不等式轉化為
    -X(n+1)<=-X(i)+i(0<=i<=n),
    -X(i)<=-X(n+2)+0(0<=i<=n),
    X(n+1)=X(n+2)=0,
    -X(i)<=-X(i-1)+0(1<=i<=n),
    -X(i-1)<=-X(i)+1(1<=i<=n),
    對任意B,E,T有-X(E)<=-X(B-1)-T

    #include <cmath>
    #include <cstdio>
    #include <cstdlib>
    #include <cstring>
    #include <algorithm>
    #include <vector>
    #include <deque>
    using namespace std;
    
    namespace dts
    {
        const int oo_min=0xcfcfcfcf,oo_max=0x3f3f3f3f;
        
        int n,m;
        vector<int> vis;
        vector<int> dist;
        vector<vector<int>> e;
        vector<vector<int>> l;
        deque<int> q;
        
        void clear()
        {
            e.resize(n+3),l.resize(e.size());
            for (int i=0;i<e.size();i++)
                e[i].clear(),l[i].clear();
        }
        void add_edge(int x,int y,int d)
        {
            e[x].push_back(y);
            l[x].push_back(d);
        }
        int bfs()
        {
            vis.resize(e.size());
            dist.resize(e.size(),oo_max);
            dist[n+1]=dist[n+2]=0;
            for (q.clear(),vis[n+1]=vis[n+2]=1,q.push_back(n+1),q.push_back(n+2);!q.empty();vis[q.front()]=0,q.pop_front())
            {
                int now=q.front();
                for (int i=0;i<e[now].size();i++)
                    if (dist[now]+l[now][i]<dist[e[now][i]])
                    {
                        dist[e[now][i]]=dist[now]+l[now][i];
                        if (vis[e[now][i]]==0)
                            vis[e[now][i]]=1,q.push_back(e[now][i]);
                    }
            }
            return dist[n];
        }
        
        void main()
        {
            scanf("%d%d",&n,&m);
            clear();
            for (int i=0;i<=n;i++)
            {
                add_edge(i,n+1,i);
                add_edge(n+2,i,0);
                if (i>0)
                {
                    add_edge(i-1,i,0);
                    add_edge(i,i-1,1);
                }
            }
            for (int i=1;i<=m;i++)
            {
                int B,E,T;
                scanf("%d%d%d",&B,&E,&T);
                add_edge(B-1,E,-T);
            }
            printf("%d\n",-bfs());
        }
    }
    
    int main()
    {
        dts::main();
    }
    
  • 0
    @ 2018-06-15 21:51:32

    Accepted

    状态 耗时 内存占用

    #1 Accepted 4ms 384.0 KiB
    #2 Accepted 7ms 256.0 KiB
    #3 Accepted 3ms 340.0 KiB
    #4 Accepted 9ms 360.0 KiB
    #5 Accepted 7ms 352.0 KiB
    #6 Accepted 5ms 352.0 KiB
    #7 Accepted 10ms 256.0 KiB
    #8 Accepted 3ms 364.0 KiB
    #9 Accepted 8ms 372.0 KiB
    #10 Accepted 9ms 380.0 KiB

    #include<cstdio>
    #include<algorithm>
    using namespace std;
    bool b[5005];
    struct xigua
    {
    int x,y,t;
    }a[3005];
    bool cmp(xigua a,xigua b)
    {
    return a.y<b.y;
    }
    int main()
    {
    int n,m;
    scanf("%d %d",&n,&m);
    for(int i=1;i<=m;i++)
    scanf("%d %d %d",&a[i].x,&a[i].y,&a[i].t);
    sort(a+1,a+1+m,cmp);
    for(int i=1;i<=m;i++)
    {
    int t=0;
    for(int j=a[i].y;j>=a[i].x;j--)
    if(b[j])
    t++;
    int sum=0;
    for(int j=a[i].y;sum<(a[i].t-t);j--)
    {
    if(!b[j])
    {
    b[j]=1;
    sum++;
    }
    }
    }
    int ans=0;
    for(int i=1;i<=n;i++)
    if(b[i])
    ans++;
    printf("%d",ans);
    return 0;
    }

  • 0
    @ 2017-04-08 10:50:57

    #include <iostream>
    #include <iomanip>
    #include <cstdlib>
    #include <cmath>
    #include <string>
    #include <cstdio>
    #include <algorithm>
    using namespace std;
    struct wa
    {
    int b,e,t;
    bool operator<(const wa & a) const
    {
    if(e!=a.e) return e<a.e;
    return b<a.b;
    }
    }w[3005];
    int m,n,i,b,e,t,ans,j;
    bool f[5005];
    int main()
    {
    scanf("%d%d",&n,&m);
    for(i=1;i<=m;i++) scanf("%d%d%d",&w[i].b,&w[i].e,&w[i].t);
    sort(w,w+m);
    for(i=1;i<=m;i++)
    {
    for(j=w[i].b;j<=w[i].e&&w[i].t>0;j++)
    {
    if(f[j]) w[i].t--;

    }
    for(j=w[i].e;j>=w[i].b&&w[i].t>0;j--)
    {
    if(!f[j])
    {
    f[j]=1;
    ans++;
    w[i].t--;
    }
    }
    }
    printf("%d\n",ans);
    system("pause");
    return 0;
    }

  • 0
    @ 2017-03-31 10:28:44

    #include<iostream>
    #include<memory.h>
    #include<cstdio>
    #include<cmath>
    #include<queue>
    #include<algorithm>
    #include<stack>
    #include<cstring>
    #include<vector>
    #include<list>
    #include<set>
    using namespace std;

    struct node
    {
    int s,e,t;
    bool operator < (const node & t) const
    {
    if(e != t.e) return e < t.e;
    return s < t.s;
    }
    };
    node p[3005];
    int n,m,b,e,t,i,j,ans;
    bool f[5005];

    int main()
    {
    cin >> n >> m;
    for( i = 0; i < m; ++i) cin >> p[i].s >> p[i].e >> p[i].t ;
    sort(p,p+m);
    for( i = 0; i < m; ++i)
    {
    for( j = p[i].s; j <= p[i].e && p[i].t; ++j)
    {
    if(f[j]) p[i].t--;
    }
    for( j = p[i].e; j >= p[i].s && p[i].t; --j)
    {
    if(!f[j])
    {
    p[i].t--;
    f[j] = 1;
    ans++;
    }
    }
    }
    cout << ans << endl;
    //while(1);
    return 0;
    }

  • 0
    @ 2016-11-26 10:49:46
    #include<cstdio>
    #include<algorithm>
    struct node{
     int b,e,t;
    };
    node melon[3010];
    bool f[5010]={0};
    inline int read()
    {
     char ch=getchar();int ans=0;
     while (ch<'0'||ch>'9') ch=getchar();
     while (ch>='0'&&ch<='9') {ans*=10;ans+=ch-'0';ch=getchar();}
     return ans;
    }
    int my_comp(const node &a,const node &b)
    {
     if (a.e<b.e) return 1;
     if (a.e>b.e) return 0;
     return a.b<b.b;
    }
    int main()
    {
     int n=read(),m=read(),ans=0;
     for (int i=1;i<=m;++i)
      {
       melon[i].b=read();
       melon[i].e=read();
       melon[i].t=read();
      }
     std::sort(melon+1,melon+m+1,my_comp);
     for (int i=1;i<=m;++i)
      {
       int q=melon[i].b;
       while (q<=melon[i].e&&melon[i].t)
        {if (f[q])
          --melon[i].t;
         ++q;
        } 
       int j=1;
       while (melon[i].t>0)
        {
         if (!f[melon[i].e-j+1])
          {f[melon[i].e-j+1]=1;melon[i].t--;++ans;}
         ++j;
        }
      }
     printf("%d\n",ans);
     return 0;
    }
    
  • 0
    @ 2010-03-26 19:54:16

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

    还是差分约束好~

    SPFA秒。。。

    (PS.树状数组优化的贪心竟然会WA,不解。。。)

  • 0
    @ 2009-11-07 16:12:38

    记录号 Flag 得分 记录信息 环境 评测机 程序提交时间

    R1715495 Accepted 100 From song19931218-

      P1589 FPC Vijos Easy 2009-11-7 16:04:44

    From maa04

    笨笨的西瓜种植(赛) 笨笨工作室系列 系列

    编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

    dfs版的spfa写丑了,没能秒杀

  • 0
    @ 2009-11-04 16:01:40

    典型的差分约束系统,经典的模型

    编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

    program vijos_1589;

    const

    maxV=5000;

    maxM=3000;

    maxE=maxM+(maxV+1)2);

    dist[0]:=0;

    fillChar(v,sizeof(v),false);

    v[0]:=true;

    num:=1;

    repeat

    i:=head[q[r]];

    while i0 do begin

    if dist[e[i]]

  • 0
    @ 2009-11-01 14:56:32

    还是查分约束稳~~~~~~

  • 0
    @ 2009-10-24 20:19:12

    大西瓜大西瓜!!

  • 0
    @ 2009-10-21 18:18:50

    水题

    由于是1444的程序拿来,所以有点问题没改。。。超时好几次....

  • 0
    @ 2009-10-13 20:12:03

    编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

  • 0
    @ 2009-10-09 16:46:19

    给按头区间排序,

    再从后往前枚举

    快排写错

    交了3次..

  • 0
    @ 2009-10-04 16:10:56

    差分约束

  • 0
    @ 2009-10-03 18:23:59

    Vivid Puppy:

    编译通过...

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

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

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

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

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

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

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

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

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

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

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

    Vijos Dragon:

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

    编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

    评测机不同程序AC用时不同啊!

  • 0
    @ 2009-08-27 22:27:18

    希望有些同学尊重他人劳动成果,不要盗用他人题解和代码,就算盗用了也别说是你做的

    马甲虽然穿在身,我心依然是中国心

  • 0
    @ 2009-08-26 21:28:41

    program p1589;

    var f,b,e:array[0..5001]of integer;

    use:array[0..5001]of boolean;

    con:array[0..3000,1..3]of integer;

    sum,i,j,k,n,m:longint;

    procedure swap(a,b:integer);

    var k:integer;

    begin

    k:=con[a,1];con[a,1]:=con;con:=k;

    k:=con[a,2];con[a,2]:=con;con:=k;

    k:=con[a,3];con[a,3]:=con;con:=k;

    end;

    procedure cal(x:integer);

    var k,i,j:integer;

    begin

    for i:=con[x,1] to con[x,2] do

    if use[i] then dec(con[x,3]);

    for i:=1 to con[x,3] do

    begin

    k:=0;

    for j:=con[x,1] to con[x,2] do

    if not use[j] then

    if f[j]>=f[k] then k:=j;

    use[k]:=true;

    end;

    for i:=con[x,1] to con[x,2] do

    dec(f[i]);

    end;

    begin

    readln(n,m);

    for i:=1 to m do

    begin

    readln(con,con,con);

    inc(b[con]);

    inc(e[con+1]);

    end;

    for i:=1 to m-1 do

    for j:=i+1 to m do

    if con

  • 0
    @ 2009-08-14 19:24:38

    编译通过...

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

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

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

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

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

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

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

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

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

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

    差分约束系统

    1次ac

  • 0
    @ 2009-08-14 16:20:46

    编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

    没有秒杀是因为我偷懒了,在对右端点排序时我没有快排,用了冒泡!

    感谢1s的题解

信息

ID
1589
难度
6
分类
贪心 点击显示
标签
递交数
2000
已通过
538
通过率
27%
被复制
1
上传者