题解 - Vijos

1

Lifi LV 10 @ 2019-09-06 17:15:31

贪心+树状数组
1.将区间按区间尾升序排序。
2.逐个遍历区间，用树状数组查询区间内元素数目。
3.当前区间元素<2时，在区间尾从后向前加元素，并更新树状数组，直至满足要求为止。

#include <bits/stdc++.h>

using namespace std;

typedef struct
{
    int a,b;
}qj;

int n;
qj jl[10000];
bool vis[10005]={0};
int tr[10005]={0};

int lowbit(int x)
{
    return x&(-x);
}

void add(int x,int a)
{
    while(x<10005)
    {
        tr[x]+=a;
        x+=lowbit(x);
    }
}

int sum(int x)
{
    int ans=0;
    while(x>0)
    {
        ans+=tr[x];
        x-=lowbit(x);
    }
    return ans;
}

bool comp(qj a,qj b)
{
    if(a.b==b.b)
    {
        return a.a<b.a;
    }
    else
    {
        return a.b<b.b;
    }
}

int main()
{
    cin>>n;
    int i,j,k,ans=0;
    for(i=0;i<n;i++)
    {
        cin>>jl[i].a>>jl[i].b;
        jl[i].a++;
        jl[i].b++;
    }
    sort(jl,jl+n,comp);
    for(i=0;i<n;i++)
    {
        k=sum(jl[i].b)-sum(jl[i].a-1);
        for(j=jl[i].b;k<2;j--)
        {
            if(!vis[j])
            {
                vis[j]=true;
                k++;
                add(j,1);
                ans++;
            }
        }
    }
    cout<<ans<<endl;
    return 0;
}

1

timer LV 8 @ 2017-02-25 21:53:30

var i,j,m,n,k,l,o,p,q,t,x,y,sum:longint;
a,b:array[0..100000] of longint;
c:array[0..100000] of boolean;
begin
readln(n);
for i:=1 to n do read(a[i],b[i]);
for i:=1 to n-1 do
for j:=1 to n-i do
if a[j]>a[j+1] then begin t:=a[j];a[j]:=a[j+1];a[j+1]:=t;end;
x:=-1;
y:=-2;
for i:=1 to n do
begin
if (x>=a[i]) and (y>=a[i]) then continue;
if x>=a[i] then begin y:=b[i];inc(sum);end
else if y>=a[i] then begin x:=b[i];inc(sum);end
else begin x:=b[i];y:=b[i]-1;inc(sum);inc(sum);end;
end;
writeln(sum);
end .
为什么AC4

1

PowderHan LV 10 @ 2016-08-18 21:30:45

AC99题纪念
/*
简单贪心即可
对于所有的区间按右端点从小到大排序，然后先判断是否覆盖了足够多的数
如果还未覆盖到两个数，那么我们就从右往左扫描(即是先考虑选择右端点的数)，
此贪心策略同区间选点覆盖问题，容易证明
直到选择该区间选择到了两个数为止
则继续考虑下一个区间
嗯就这么简单
                                                        Powder
*/
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;

struct node
{
    int x,y;
}a[10005];
bool used[10005];
int n;
int ans;

int cmp(node a,node b)
{
    return a.y<b.y;
}

int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>a[i].x>>a[i].y;
    sort(a+1,a+n+1,cmp);
    for(int i=1;i<=n;i++)
    {
        int k=0;
        for(int j=a[i].x;j<=a[i].y;j++)
            if(used[j])
                k++;
        for(int j=a[i].y;j>=a[i].x&&k<2;j--)
            if(!used[j])
            {
                used[j]=1;
                k++;
                ans++;
            }
    }
    cout<<ans<<endl;
    return 0;
}

0

z20c12h LV 9 @ 2017-11-03 16:57:29

区间覆盖问题的贪心思路，加上一点点的数据结构优化。

#include <map>
#include <cmath>
#include <ctime>
#include <queue>
#include <stack>
#include <cstdio>
#include <vector>
#include <bitset>
#include <cstring>
#include <iostream>
#include <algorithm>
#define QU queue
#define ST stack
#define VC vector
#define PQ priority_queue
#define IT int
#define CR char
#define VD void
#define BL bool
#define DB double
#define LL long long
#define LINF (1LL<<60)
#define INF (0x3f3f3f3f)
#define IOS ios::sync_with_stdio(0)
#define F(x, y, z) for(int x=y; x<=z; x++)
#define D(x, y, z) for(int x=z; x>=y; x--)
#define MM(x, y) memset(x, y, sizeof(x))
#define PW2(t) ((t)*(t))
#define PB push_back
#define GC getchar
#define LE length
#define PF printf
#define SF scanf
#define FT front
#define CL clear
#define EM empty
#define SZ size
#define PT puts
#define PS push
#define MX max
#define MI min
#define PP pop
#define TP top
using namespace std;
#define N (10000)
struct SP
{
    IT l,r;
    BL operator < (const SP & t) const {return r<t.r;}
};
struct BIT 
{
    #define Z (N<<1)
    IT nm[Z];
    VD CL () {MM(nm,0);}
    VD AD (IT x,IT y) {while(x<=Z) nm[x]+=y,x+=x&-x;}
    IT QY (IT x) {IT cl=0;while(x>0) cl+=nm[x],x-=x&-x;return cl;}
};
BIT bit;
SP sp[N<<1];
IT n,ans,pt[N<<1];
VD RD (IT & t)
{
    IT sg=1;CR cc=GC();t=0;
    while(cc<'0'||cc>'9') {if (cc=='-') sg=-1;cc=GC();}
    while(cc>='0'&&cc<='9') {t=t*10+cc-'0';cc=GC();}
    t*=sg;
}
IT main ()
{
    IT t;
    RD(n);
    F(i,1,n) RD(sp[i].l),RD(sp[i].r),sp[i].l++,sp[i].r++;
    sort(sp+1,sp+n+1);
    bit.CL();   
    F(i,1,n)
    {
        t=bit.QY(sp[i].r)-bit.QY(sp[i].l-1);
        for(IT j=sp[i].r;j>=sp[i].l&&t<2;j--) if (!pt[j]) 
        {
            ans++,t++;
            pt[j]=1,bit.AD(j,1);    
        }
    }
    PF("%d\n",ans);
    return 0;   
}

0

aciffar LV 10 @ 2016-08-15 13:46:37

敲暴力AC，而且时间还不错...
编译成功

测试数据 #0: Accepted, time = 0 ms, mem = 668 KiB, score = 9

测试数据 #1: Accepted, time = 0 ms, mem = 668 KiB, score = 9

测试数据 #2: Accepted, time = 0 ms, mem = 668 KiB, score = 9

测试数据 #3: Accepted, time = 0 ms, mem = 672 KiB, score = 9

测试数据 #4: Accepted, time = 15 ms, mem = 672 KiB, score = 9

测试数据 #5: Accepted, time = 0 ms, mem = 672 KiB, score = 9

测试数据 #6: Accepted, time = 15 ms, mem = 672 KiB, score = 9

测试数据 #7: Accepted, time = 31 ms, mem = 672 KiB, score = 9

测试数据 #8: Accepted, time = 15 ms, mem = 668 KiB, score = 9

测试数据 #9: Accepted, time = 0 ms, mem = 672 KiB, score = 9

测试数据 #10: Accepted, time = 0 ms, mem = 672 KiB, score = 10

Accepted, time = 76 ms, mem = 672 KiB, score = 100

0

zhuchenglong LV 8 @ 2015-08-04 15:45:56

尽量往右边放。。。。

program exam;
var i,j,m,n,k,l,o,p,q:longint;
a,b:array[0..100000] of longint;
c:array[0..100000] of boolean;
procedure qt(l,r:longint);
var i,j,m1,p,m2:longint;
begin
i:=l; j:=r;
m1:=a[(l+r) div 2];
m2:=b[(l+r) div 2];
repeat
while (b[i]<m2) or ((b[i]=m2) and (a[i]<m1)) do inc(i);
while (b[j]>m2) or ((b[j]=m2) and (a[j]>m1)) do dec(j);
if i<=j then
begin
p:=b[i]; b[i]:=b[j]; b[j]:=p;
p:=a[i]; a[i]:=a[j]; a[j]:=p;
inc(i); dec(j);
end;
until i>j;
if i<r then qt(i,r);
if l<j then qt(l,j);
end;
begin
fillchar(c,sizeof(c),true);
readln(n);
p:=maxlongint;
q:=-10000;
for i:=1 to n do
begin
readln(a[i],b[i]);
if a[i]<p then p:=a[i];
if b[i]>q then q:=b[i];
end;
qt(1,n);
for i:=1 to n do
begin
k:=0;
for j:=b[i] downto a[i] do
begin
if c[j]=false then
inc(k);
if k=2 then break;
end;
if k<2 then
for j:=b[i] downto a[i] do
begin
c[j]:=false;
inc(k);
if k=2 then break;
end;
end;
for i:=p to q do
if c[i]=false then inc(o);
writeln(o);
end.

0

wangqihang LV 8 @ 2015-08-04 14:59:58

program watermelon;
var n,m,i,j,k,s,tot:longint;
a,b,w:array[0..10000] of longint;
v:array[0..10000] of boolean;
procedure qsort(l,r:longint);
var i,j,t,mid:longint;
begin
i:=l;j:=r;mid:=b[(i+j) shr 1];
repeat
while (b[i]<mid) do inc(i);
while (b[j]>mid) do dec(j);
if i<=j then
begin
t:=a[i];a[i]:=a[j];a[j]:=t;
t:=b[i];b[i]:=b[j];b[j]:=t;
inc(i);dec(j);
end;
until i>j;
if i<r then qsort(i,r);
if j>l then qsort(l,j);
end;

begin
readln(m);
for i:=1 to m do
begin
readln(a[i],b[i]);
w[i]:=2;
end;
qsort(1,m);

for i:=1 to m do
begin
s:=0;
for j:=a[i] to b[i] do
if v[j] then
inc(s);
if s<w[i] then begin
w[i]:=w[i]-s;
for j:=b[i] downto a[i] do
begin
if w[i]<=0 then break;
if not v[j] then
begin
v[j]:=true;
inc(tot);
w[i]:=w[i]-1;
end;
end;
end;
end;

writeln(tot);
end.

0

913027135 LV 8 @ 2015-08-04 14:20:40

怎么会RuntimeError 啊啊啊啊啊啊啊

0

dkfleet LV 10 @ 2015-02-03 21:04:03

求的是|Z|!而不是Z的可能方案数....
于是直接拿1532过来改一下就A了......

0

308454 LV 10 @ 2014-07-16 16:20:27

不会用贪心只会差分约束系统暴力怎么办

0

hncsyjc LV 7 @ 2013-06-13 15:53:14

依旧WA了四个点。。。无力了交了6次，Compiling 4次（卡住了）

0

hncsyjc LV 7 @ 2013-06-13 15:04:24

求解为什么这份代码依然不对：
var
n,i,j,g,max,ans:longint;
l,r:array [1..10000] of longint;
v:array [0..10000] of boolean;
procedure sort(s,e:longint);
var
i,j,x,y:longint;
begin
i:=s;j:=e;x:=l[(s+e)>>1];
repeat
while (l[i]<x) do inc(i);
while (x<l[j]) do dec(j);
if not(i>j) then begin
y:=l[i];l[i]:=l[j];l[j]:=y;
y:=r[i];r[i]:=r[j];r[j]:=y;
inc(i);dec(j);
end;
until i>j;
if s<j then sort(s,j);
if i<e then sort(i,e);
end;
begin
readln(n);
for i:=1 to n do begin
readln(l[i],r[i]);
if r[i]>max then max:=r[i];
end;
sort(1,n);
for i:=1 to n do
begin
g:=0;
for j:=l[i] to r[i] do if v[j] then inc(g);
if (g>=2) then continue;
inc(ans);v[r[i]]:=true;
if g=0 then begin inc(ans);v[r[i]-1]:=true;end;
end;
writeln(ans);
end.

0

hncsyjc LV 7 @ 2013-06-13 12:51:09

我要疯了，方向对了（排序+贪心），但不知道如何求已经交了多少个点。。。。
然后WA了3次。。。。
用了线段树乱搞。。。

0

如彼泉流 LV 8 @ 2009-11-11 18:40:50

按左端点由小到大排序，从后往前扫描填左边，无需去重。

0

song19931218 LV 9 @ 2009-11-07 11:30:41

编译通过...

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

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

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

├ 测试数据 04：答案正确... 431ms

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

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

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

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

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

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

├ 测试数据 11：答案正确... 0ms

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

Accepted 有效得分：100 有效耗时：431ms

试着用SPFA写了一个差分约束，结果失败了（大脑温度越来越高）；

我个人对于差分约束的看法是：

貌似和各种最短路算法只是形式上相似，因为二者都符合三角不等式。。

可能这个看法是错的

0

royo LV 10 @ 2009-10-30 19:13:36

用的贪心...

输出的到底是什么琢磨了很久..

哪位牛讲一下差分约束啊~

0

LV 0 @ 2009-10-26 12:48:08

其实这道题可以优化到O(n)。

首先是去重，发现区间的范围也是[0..n]，那么我们像计数排序那样使b[i]=以i为左坐标的最小右坐标，然后我们从数组右边扫到左边，边扫边更新当前右坐标的最小值min,每到一个新区间，看看他的右坐标是否比min大，如果比它大就是包含它了，去掉。

然后就是贪心，贪心时最耗时间就是扫描看当前区间的部分和了是吧。由于在我们的贪心算法中，必然放1的坐标必然是递增的，所以我们可以边放1边维护部分和数组。

程序看我空间吧。

http://hi.baidu.com/cloudygoose/blog/item/52f0e23560904644241f14f2.html

0

瀑布飞鹰 LV 8 @ 2009-10-24 22:54:37

话说...差分约束到底怎么回事，麻烦大牛贴一个！

0

陈亮宇 LV 10 @ 2009-10-20 14:16:25

编译通过...

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

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

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

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

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

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

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

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

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

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

├ 测试数据 11：答案正确... 0ms

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

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

1532 C=2

0

prince_hao LV 10 @ 2009-10-08 16:29:58

编译通过...

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

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

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

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

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

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

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

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

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

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

├ 测试数据 11：答案正确... 0ms

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

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

贪心伟大

题解

60 条题解

区间

信息

状态

开发

支持

题解

60 条题解

区间

信息

状态

开发

支持

还没有账户？

登录