发表更新16 分钟读完 (大约2463个字)0次访问

P7913 [CSP-S 2021] 廊桥分配 题解

首先我们需要对原来形象的实际问题进行抽象化。

以样例 1 的国内航班抵达、离开时刻信息为例，我们可以通过区间来表示每架飞机位于机场的时间：

不妨先假设廊桥数量没有限制，那么当一个新的飞机抵达时，显然需要使用一个空闲的廊桥。当飞机离开时，就可以释放出一个空闲的廊桥。因此，我们可以记下所需廊桥的数量。当一架飞机抵达时计数器 $+1$，离开时 $-1$：

具体流程如下：

时刻 航班序号 抵达/离开 当前正在使用的廊桥数量（计数器）
$1$ $1$ 抵达 $0+1=1$
$3$ $2$ 抵达 $1+1=2$
$5$ $1$ 离开 $2-1=1$
$6$ $3$ 抵达 $1+1=2$
$8$ $2$ 离开 $2-1=1$
$9$ $4$ 抵达 $1+1=2$
$10$ $3$ 离开 $2-1=1$
$13$ $5$ 抵达 $1+1=2$
$14$ $4$ 离开 $2-1=1$
$18$ $5$ 离开 $1-1=0$

显然，所需的廊桥数量为计数器在所有时刻内的最大值，在本例中为 $2$。

接下来考虑增加廊桥限制时的操作方法：

在进行计数器 $+1$ 操作时，如果计数器在操作之后超过廊桥限制数量，那么就让该飞机不进入廊桥，同时进行标记以防后面操作时对该航班进行 $-1$ 操作。

如果廊桥数量限制为 $1$，那么示意图将会变成这样（灰色表示无法进入廊桥）：

具体实现方法是先把读入的航班信息按照抵达时刻从小到大进行排序并对时刻进行离散化。然后在 $[0,n]$ 内枚举廊桥数量限制，并在限制条件下对每个离散化后的时刻进行 $+1/-1$ 处理，依次得到最大航班数量。最后进行统计即可：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
#include<bits/stdc++.h>
using namespace std;
int n,m_1,m_2,ld,li,ans,td[200005],ti[200005],posd[200005][2],posi[200005][2];
bool vis[100005];
struct flight
{
    int a,b;
    bool operator<(const flight &x)const
    {
        return a<x.a;
    }
}dom[100005],inter[100005]; // domestic: 国内，international: 国际
int solve(int a[][2],int len,int x)
{
    int cnt=0,ans=0; // cnt 为廊桥数量计数器，ans 记录能够进入廊桥的航班数量
    memset(vis,false,sizeof(vis)); // vis 数组存储每个航班是否能够进入廊桥
    for(int i=1;i<=len;++i)
    {
        if(a[i][1]) // 判断是否为抵达
        {
            if(cnt<x) // 判断是否还可进入廊桥
            {
                ++cnt; // 当前廊桥数量 +1
                ++ans; // 可进入廊桥的航班数 +1
                vis[a[i][0]]=true; // 标记该航班能进入廊桥
            }
        }
        else if(vis[a[i][0]])--cnt; // 如果当前时刻有飞机离开且该飞机原来在廊桥中，则当前廊桥数量 -1
    }
    return ans;
}
template<typename T>void read(T &x)
{
    char ch=getchar();
    while(!isdigit(ch))ch=getchar();
    while(isdigit(ch))
    {
        x=(x<<3)+(x<<1)+(ch^48);
        ch=getchar();
    }
}
int main()
{
    read(n),read(m_1),read(m_2);
    for(int i=1;i<=m_1;++i)
    {
        read(dom[i].a),read(dom[i].b);
        td[++ld]=dom[i].a;
        td[++ld]=dom[i].b;
        // 将时刻存入待离散化的数组中（国内、国际分开存储）
    }
    for(int i=1;i<=m_2;++i)
    {
        read(inter[i].a),read(inter[i].b);
        ti[++li]=inter[i].a;
        ti[++li]=inter[i].b;
    }
    sort(td+1,td+ld+1);
    sort(ti+1,ti+li+1);
    // 由于没有重复时刻，因此只需排序、无需去重
    sort(dom+1,dom+m_1+1);
    sort(inter+1,inter+m_2+1);
    // 按照抵达时刻从小到大进行排序（国内、国际分开）
    for(int i=1;i<=m_1;++i)
    {
        dom[i].a=lower_bound(td+1,td+ld+1,dom[i].a)-td;
        dom[i].b=lower_bound(td+1,td+ld+1,dom[i].b)-td;
        // 将航班的时刻修改为离散化后的数值，方便操作
        posd[dom[i].a][0]=posd[dom[i].b][0]=i;
        posd[dom[i].a][1]=1;
        // 第二维 0 下标存储航班序号、1 下标存储该时刻是否是飞机抵达
    }
    for(int i=1;i<=m_2;++i)
    {
        inter[i].a=lower_bound(ti+1,ti+li+1,inter[i].a)-ti;
        inter[i].b=lower_bound(ti+1,ti+li+1,inter[i].b)-ti;
        posi[inter[i].a][0]=posi[inter[i].b][0]=i;
        posi[inter[i].a][1]=1;
    }
    for(int i=0;i<=n;++i)ans=max(ans,solve(posd,ld,i)+solve(posi,li,n-i)); // [0,n] 枚举廊桥数量限制
    printf("%d",ans);
    return 0;
}

这样，我们便得到了一个 $\mathcal O(n(m_1+m_2)+m_1 \log m_1+m_2 \log m_2) \approx \mathcal O(n^2)$ 的做法，可以获得 $40$ 分的好成绩。

接着考虑如何对 $O(n^2)$ 做法进行优化。

原来的暴力程序采用先枚举限制再遍历时刻的方法。由于遍历时刻的操作不可优化，因此我们可以考虑先遍历时刻再枚举限制。

不妨用数组 ${\text{sum}_i}$ 来记录限制数量为 $i$ 时当前所需廊桥的数量，用数组 ${\text{ans}_i}$ 来记录限制数量为 $i$ 时当前可进入廊桥的航班数量。不难发现，这两个数组一定单调不递减。

在遍历时刻的过程中，对于每一个时刻，我们可以分两种情况讨论：

  • 该时刻有飞机抵达。此时我们可以在 ${\text{sum}_i}$ 中进行二分，找到一个最大的 $p$，使得 $\text{sum}_p \lt p$（即飞机还可进入廊桥）。紧接着，我们把 $[p,n]$ 内的 $\text{sum}$ 值和 $\text{ans}$ 值全部加上 $1$。和暴力程序类似，我们在该航班的对应位置标记 $p$，方便后续操作。如果所有的 $\text{sum}$ 值都不小于 $p$，那么就标记 $-1$。

  • 该时刻有飞机离开。由于该飞机的离开时刻一定晚于抵达时刻，因此我们可以查看之前所做的标记。如果标记 $\text{pos}$ 不为 $-1$，那么就把 $[\text{pos},n]$ 内的 $\text{sum}$ 全部减 $1$，完成还原操作。

如果每次进行暴力 $+1$ / $-1$，那么时间复杂度仍为 $\mathcal O(n^2)$。但考虑到修改都是区间性的，因此可以通过线段树、区修单查的树状数组或分块实现。

常数较大的 $\mathcal O(n \log^2n)$ 线段树代码：（最大时限 $\approx 200$ $\text{ms}$）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
#include<bits/stdc++.h>
using namespace std;
int n,m_1,m_2,ld,li,cn,ANS,td[200005],ti[200005],posd[200005][2],posi[200005][2],pos[100005],ansd[100005],ansi[100005];
struct flight
{
    int a,b;
    bool operator<(const flight &x)const
    {
        return a<x.a;
    }
}dom[100005],inter[100005];
struct node
{
    int l,r,ls,rs,sum,tag;
};
struct segtree
{
    node t[200005]; // 这种线段树写法只需开 2 倍空间
    void build(int p,int l,int r) // 线段树建树的复杂度为 O(n)
    {
        t[p].l=l,t[p].r=r;
        if(l==r)return;
        int mid=(t[p].l+t[p].r)>>1;
        build(t[p].ls=++cn,l,mid);
        build(t[p].rs=++cn,mid+1,r);
    }
    void init()
    {
        cn=1;
        build(1,1,n);
    }
    void reset()
    {
        for(int i=1;i<=n<<1;++i)
        {
            t[i].sum=0;
            t[i].tag=0;
        }
    }
    void push_up(int p)
    {
        if(!t[p].tag)return;
        int l=t[p].ls,r=t[p].rs;
        t[l].sum+=(t[l].r-t[l].l+1)*t[p].tag;
        t[r].sum+=(t[r].r-t[r].l+1)*t[p].tag;
        t[l].tag+=t[p].tag;
        t[r].tag+=t[p].tag;
        t[p].tag=0;
    }
    void update(int p,int l,int r,int k) // 线段树区间修改的复杂度为 O(log n)
    {
        if(l<=t[p].l&&t[p].r<=r)
        {
            t[p].sum+=(t[p].r-t[p].l+1)*k;
            t[p].tag+=k;
            return;
        }
        push_up(p);
        int mid=(t[p].l+t[p].r)>>1;
        if(l<=mid)update(t[p].ls,l,r,k);
        if(r>mid)update(t[p].rs,l,r,k);
        t[p].sum=t[t[p].ls].sum+t[t[p].rs].sum;
    }
    int query(int p,int l,int r) // 线段树单点 / 区间查询的复杂度均为 O(log n)
    {
        if(l<=t[p].l&&t[p].r<=r)return t[p].sum;
        push_up(p);
        int mid=(t[p].l+t[p].r)>>1;
        if(l>mid)return query(t[p].rs,l,r);
        if(r<=mid)return query(t[p].ls,l,r);
        return query(t[p].ls,l,r)+query(t[p].rs,l,r);
    }
}sum,ans;
void solve(int a[][2],int len,bool flag)
{
    memset(pos,0,sizeof(pos));
    if(flag)sum.reset(),ans.reset();
    else sum.init(),ans.init();
    // flag 表示是否为第一次进行 solve 操作；如果为 false 就进行建树，否则重新赋值
    for(int i=1;i<=len;++i)
    {
        if(a[i][1])
        {
            int l=1,r=n,p=-1;
            while(l<=r)
            {
                int mid=(l+r)>>1;
                if(sum.query(1,mid,mid)<mid)
                {
                    r=mid-1;
                    p=mid;
                }
                else l=mid+1;
            }
            // 二分查找最大的 p，使得 sum[p]<p
            pos[a[i][0]]=p;
            if(~p)
            {
                sum.update(1,p,n,1);
                ans.update(1,p,n,1);
                // +1 操作
            }
        }
        else if(~pos[a[i][0]])sum.update(1,pos[a[i][0]],n,-1); // -1 还原性操作
    }
    for(int i=1;i<=n;++i)
    {
        if(flag)ansi[i]=ans.query(1,i,i);
        else ansd[i]=ans.query(1,i,i);
        // 将答案存入对应数组中，方便后面进行 O(n) 统计
    }
}
template<typename T>void read(T &x)
{
    char ch=getchar();
    while(!isdigit(ch))ch=getchar();
    while(isdigit(ch))
    {
        x=(x<<3)+(x<<1)+(ch^48);
        ch=getchar();
    }
}
int main()
{
    read(n),read(m_1),read(m_2);
    for(int i=1;i<=m_1;++i)
    {
        read(dom[i].a),read(dom[i].b);
        td[++ld]=dom[i].a;
        td[++ld]=dom[i].b;
    }
    for(int i=1;i<=m_2;++i)
    {
        read(inter[i].a),read(inter[i].b);
        ti[++li]=inter[i].a;
        ti[++li]=inter[i].b;
    }
    sort(td+1,td+ld+1);
    sort(ti+1,ti+li+1);
    sort(dom+1,dom+m_1+1);
    sort(inter+1,inter+m_2+1);
    for(int i=1;i<=m_1;++i)
    {
        dom[i].a=lower_bound(td+1,td+ld+1,dom[i].a)-td;
        dom[i].b=lower_bound(td+1,td+ld+1,dom[i].b)-td;
        posd[dom[i].a][0]=posd[dom[i].b][0]=i;
        posd[dom[i].a][1]=1;
    }
    for(int i=1;i<=m_2;++i)
    {
        inter[i].a=lower_bound(ti+1,ti+li+1,inter[i].a)-ti;
        inter[i].b=lower_bound(ti+1,ti+li+1,inter[i].b)-ti;
        posi[inter[i].a][0]=posi[inter[i].b][0]=i;
        posi[inter[i].a][1]=1;
    }
    solve(posd,ld,false);
    solve(posi,li,true);
    for(int i=0;i<=n;++i)ANS=max(ANS,ansd[i]+ansi[n-i]);
    printf("%d",ANS);
    return 0;
}

$\mathcal O(n \log n + n \sqrt n)$ 的分块代码：（最大时限 $\approx 100$ $\text{ms}$）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
#include<bits/stdc++.h>
using namespace std;
int n,m_1,m_2,ld,li,len,ANS,td[200005],ti[200005],posd[200005][2],posi[200005][2],pos[100005],id[100005],ansd[100005],ansi[100005];
struct flight
{
    int a,b;
    bool operator<(const flight &x)const
    {
        return a<x.a;
    }
}dom[100005],inter[100005];
struct block
{
    int a[100005],b[325],block[325];
    void reset()
    {
        memset(a,0,sizeof(a));
        memset(b,0,sizeof(b));
        memset(block,0,sizeof(block));
    }
    void update(int l,int r,int k) // 分块区间修改的复杂度为 O(sqrt(n))
    {
        int x=id[l],y=id[r];
        if(x==y)
        {
            for(int i=l;i<=r;++i)
            {
                a[i]+=k;
                block[x]+=k;
            }
            return;
        }
        for(int i=l;i<=len*x;++i)
        {
            a[i]+=k;
            block[x]+=k;
        }
        for(int i=x+1;i<y;++i)
        {
            b[i]+=k;
            block[i]+=len*k;
        }
        for(int i=len*(y-1)+1;i<=r;++i)
        {
            a[i]+=k;
            block[y]+=k;
        }
    }
}sum,ans;
void solve(int a[][2],int len,bool flag)
{
    if(flag)
    {
        memset(pos,0,sizeof(pos));
        sum.reset(),ans.reset();
    }
    for(int i=1;i<=len;++i)
    {
        if(a[i][1])
        {
            int l=1,r=n,p=-1;
            while(l<=r)
            {
                int mid=(l+r)>>1;
                if(sum.a[mid]+sum.b[id[mid]]<mid)
                {
                    r=mid-1;
                    p=mid;
                }
                else l=mid+1;
                // 分块单点查询的复杂度为 O(1)
            }
            pos[a[i][0]]=p;
            if(~p)
            {
                sum.update(p,n,1);
                ans.update(p,n,1);
            }
        }
        else if(~pos[a[i][0]])sum.update(pos[a[i][0]],n,-1);
    }
    for(int i=1;i<=n;++i)
    {
        if(flag)ansi[i]=ans.a[i]+ans.b[id[i]];
        else ansd[i]=ans.a[i]+ans.b[id[i]];
    }
}
template<typename T>void read(T &x)
{
    char ch=getchar();
    while(!isdigit(ch))ch=getchar();
    while(isdigit(ch))
    {
        x=(x<<3)+(x<<1)+(ch^48);
        ch=getchar();
    }
}
int main()
{
    read(n),read(m_1),read(m_2);
    for(int i=1;i<=m_1;++i)
    {
        read(dom[i].a),read(dom[i].b);
        td[++ld]=dom[i].a;
        td[++ld]=dom[i].b;
    }
    for(int i=1;i<=m_2;++i)
    {
        read(inter[i].a),read(inter[i].b);
        ti[++li]=inter[i].a;
        ti[++li]=inter[i].b;
    }
    sort(td+1,td+ld+1);
    sort(ti+1,ti+li+1);
    sort(dom+1,dom+m_1+1);
    sort(inter+1,inter+m_2+1);
    for(int i=1;i<=m_1;++i)
    {
        dom[i].a=lower_bound(td+1,td+ld+1,dom[i].a)-td;
        dom[i].b=lower_bound(td+1,td+ld+1,dom[i].b)-td;
        posd[dom[i].a][0]=posd[dom[i].b][0]=i;
        posd[dom[i].a][1]=1;
    }
    for(int i=1;i<=m_2;++i)
    {
        inter[i].a=lower_bound(ti+1,ti+li+1,inter[i].a)-ti;
        inter[i].b=lower_bound(ti+1,ti+li+1,inter[i].b)-ti;
        posi[inter[i].a][0]=posi[inter[i].b][0]=i;
        posi[inter[i].a][1]=1;
    }
    len=sqrt(n);
    for(int i=1;i<=n;++i)id[i]=(i-1)/len+1;
    solve(posd,ld,false);
    solve(posi,li,true);
    for(int i=0;i<=n;++i)ANS=max(ANS,ansd[i]+ansi[n-i]);
    printf("%d",ANS);
    return 0;
}

常数较小的 $\mathcal O(n \log^2 n)$ 树状数组代码：（最大时限 $\approx 50$ $\text{ms}$）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
#include<bits/stdc++.h>
using namespace std;
int n,m_1,m_2,ld,li,ANS,td[200005],ti[200005],posd[200005][2],posi[200005][2],pos[100005],ansd[100005],ansi[100005];
struct flight
{
    int a,b;
    bool operator<(const flight &x)const
    {
        return a<x.a;
    }
}dom[100005],inter[100005];
struct BIT
{
    int t[100005];
    void update(int x,int k)
    {
        while(x<=n)
        {
            t[x]+=k;
            x+=x&-x;
        }
    }
    int query(int x)
    {
        int s=0;
        while(x)
        {
            s+=t[x];
            x-=x&-x;
        }
        return s;
    }
    // 这种树状数组的修改和查询复杂度均为 O(log n)
}sum,ans;
void solve(int a[][2],int len,bool flag)
{
    if(flag)
    {
        memset(pos,0,sizeof(pos));
        memset(sum.t,0,sizeof(sum.t));
        memset(ans.t,0,sizeof(ans.t));
    }
    for(int i=1;i<=len;++i)
    {
        if(a[i][1])
        {
            int l=1,r=n,p=-1;
            while(l<=r)
            {
                int mid=(l+r)>>1;
                if(sum.query(mid)<mid)
                {
                    r=mid-1;
                    p=mid;
                }
                else l=mid+1;
            }
            pos[a[i][0]]=p;
            if(~p)
            {
                sum.update(p,1);
                ans.update(p,1);
            }
        }
        else if(~pos[a[i][0]])sum.update(pos[a[i][0]],-1);
    }
    for(int i=1;i<=n;++i)
    {
        if(flag)ansi[i]=ans.query(i);
        else ansd[i]=ans.query(i);
    }
}
template<typename T>void read(T &x)
{
    char ch=getchar();
    while(!isdigit(ch))ch=getchar();
    while(isdigit(ch))
    {
        x=(x<<3)+(x<<1)+(ch^48);
        ch=getchar();
    }
}
int main()
{
    read(n),read(m_1),read(m_2);
    for(int i=1;i<=m_1;++i)
    {
        read(dom[i].a),read(dom[i].b);
        td[++ld]=dom[i].a;
        td[++ld]=dom[i].b;
    }
    for(int i=1;i<=m_2;++i)
    {
        read(inter[i].a),read(inter[i].b);
        ti[++li]=inter[i].a;
        ti[++li]=inter[i].b;
    }
    sort(td+1,td+ld+1);
    sort(ti+1,ti+li+1);
    sort(dom+1,dom+m_1+1);
    sort(inter+1,inter+m_2+1);
    for(int i=1;i<=m_1;++i)
    {
        dom[i].a=lower_bound(td+1,td+ld+1,dom[i].a)-td;
        dom[i].b=lower_bound(td+1,td+ld+1,dom[i].b)-td;
        posd[dom[i].a][0]=posd[dom[i].b][0]=i;
        posd[dom[i].a][1]=1;
    }
    for(int i=1;i<=m_2;++i)
    {
        inter[i].a=lower_bound(ti+1,ti+li+1,inter[i].a)-ti;
        inter[i].b=lower_bound(ti+1,ti+li+1,inter[i].b)-ti;
        posi[inter[i].a][0]=posi[inter[i].b][0]=i;
        posi[inter[i].a][1]=1;
    }
    solve(posd,ld,false);
    solve(posi,li,true);
    for(int i=0;i<=n;++i)ANS=max(ANS,ansd[i]+ansi[n-i]);
    printf("%d",ANS);
    return 0;
}

P7913 [CSP-S 2021] 廊桥分配 题解

https://hensier.github.io/OI/P7913/

作者

hensier

发布于

2021-10-24

更新于

2023-01-02

许可协议

#

评论

关注我

链接

最新文章

归档

标签

BFS1
CSP1
NOI Online1
NOIP1
OI1
二分答案1
元素周期律2
分块1
原子的构造原理4
字符串1
差分1
搜索1
数学2
树状数组1
模拟1
欧拉计划53
洛谷5
筛法1
线段树1
贪心1
递归1
队列1
题解6
×