Canadian Computing Olympiad 2020

发表于

链接

A B C D E F
$\color{gray}{\texttt{-}}$ $\color{green}{\texttt{+}}$ $\color{gray}{\texttt{-}}$ $\color{green}{\texttt{+6}}$ $\color{green}{\texttt{+}}$ $\color{red}{\texttt{+3}}$

A. A Game with Grundy

直接把每个朋友的视野在 $y=Y$ 上截得的整点区间求出，然后离散化之后扫一遍即可。

B. Exercise Deadlines

题目可以转化成：构造一个排列，满足 $p_i\leq d_i$，要求 $p_i$ 逆序对个数尽可能少。

直接贪心，从后往前贪心取没有被取的数且 $\leq d_i$ 中最大的。容易证明取更小的会使逆序对个数增加，并且更不容易合法。

最后再求一遍逆序对个数，复杂度 $O(n\log n)$。

代码 
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
#include<iostream>
#include<cstdio>
#include<cstring>
#include<set>
#define N 200010
using namespace std;
int f[N],d[N];
set<int>s;
int a[N],n;
void add(int x){for(;x;x-=x&-x) a[x]++;}
int qry(int x){int v=0;for(;x<=n;x+=x&-x) v+=a[x];return v;}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++) s.insert(i);
    for(int i=1;i<=n;i++) scanf("%d",&d[i]);
    for(int i=n;i;i--)
    {
        auto p=s.upper_bound(d[i]);
        if(p==s.begin()){puts("-1");return 0;}
        f[i]=*--p,s.erase(p);
    }
    long long ans=0;
    for(int i=1;i<=n;i++) ans+=qry(f[i]),add(f[i]);
    printf("%lld\n",ans);
    return 0;
}

C. Mountains and Valleys

如果没有非树边，答案是两倍边数减去直径边数。

结论：至多只会选一条非树边。这个比较好证，因为如果选了两条，答案至少为 $\frac{5n}{3}$，然而此时直径长度有 $\frac{n}{3}$，所以不如直接跑原树

加上树边之后的策略是：断掉对应路径上的一条树边，最大化直径。

分类讨论直径与环的关系即可。

D. Travelling Salesperson

挺妙的题。结论是：以任意点出发的最短路径合法长度都是 $n$。

考虑用增量法构造。假设当前有一条合法路径，要插入点 $u$，如果当前路径全部同色，那么直接将 $u$ 插入末尾一定合法。否则假设路径异色的分界点为 $v$，其前驱为 $v_L$ 后继为 $v_R$，如果 $(u,v_L)$ 与 $(u,v)$ 同色，那么直接将 $u$ 插入 $v_L$ 与 $v$ 直接，如果 $(u,v)$ 与 $(u,v_R)$ 同色那么插入 $v$ 与 $v_R$ 之间。如果都不满足那么 $(u,v_L),(u,v_R)$ 与 $(v_L,v),(v_R,v)$ 中的至少一条同色， 插入另一条边即可。

构造就是对结论的证明。

代码 
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
#include<iostream>
#include<cstdio>
#include<cstring>
#define N 2010
using namespace std;
int L[N],R[N];
bool g[N][N];char s[N];
void ins(int x,int y){L[R[x]]=y;L[y]=x;R[y]=R[x];R[x]=y;}
int main()
{
    int n;scanf("%d",&n);
    for(int i=2;i<=n;i++)
    {
        scanf("%s",s+1);
        for(int j=1;j<i;j++) if(s[j]=='R') g[i][j]=g[j][i]=1;
    }
    for(int i=1;i<=n;i++)
    {
        int j=i%n+1,t=j;bool hv=true;
        R[i]=j,R[j]=0,L[i]=0,L[j]=i;
        for(j=j%n+1;j!=i;j=j%n+1)
        {
            if(!R[t]){ins(t,j);if(g[t][j]!=g[L[t]][t]) hv=false;else t=j;}
            else if(g[L[t]][j]==g[t][j] || g[t][j]==g[t][R[t]])
            {
                ins(L[t],j);
                while(t!=i && g[L[t]][t]==g[t][R[t]]) t=L[t];
                if(t==i) while(R[t]) t=R[t];
            }
            else{ins(t,j);while(R[t] && g[L[t]][t]==g[t][R[t]]) t=R[t];}
        }
        printf("%d\n",n);
        for(int u=i;u;u=R[u]) printf("%d ",u);
        puts("");
    }
    return 0;
}

E. Interval Collection

首先容易证明，最优集合中一定只有至多两个区间。

分类讨论:

  • 如果不存在无交区间，那么最小的交一定是 $r$ 最小的区间与 $l$ 最大的区间。
    当然 $r$ 相同的区间可能有很多，根据题目要求选最大的即可。$l$ 同理。这部分可以用 multiset 解决。
  • 如果存在区间无交，不妨枚举分界点 $p$，相当于在 $p$ 左边找一个左端点最大的，右边找一个左端点最小的。
    如果每次取当前需要处理的区间 $[l,r]$ 的中点 $\text{mid}$，那么本质上是问右端点在 $[l,mid]$ 的区间中左端点最小值，$[ mid+1,r]$ 同理。可以发现这就是线段树的过程，直接用线段树维护即可。

复杂度 $O(n\log n)$。

代码 
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
#include<iostream>
#include<cstdio>
#include<cstring>
#include<set>
#include<algorithm>
using namespace std;
const int N=1000010,mx=1000000,inf=1000000000;
int max(multiset<int>&x){return x.empty()?-inf:*x.rbegin();}
int min(multiset<int>&x){return x.empty()?inf:*x.begin();}
multiset<int>sl[N],sr[N];
struct node{
    int l,r,s;
    node(int l=-inf,int r=inf):l(l),r(r),s(r-l){}
    node(int l,int r,int s):l(l),r(r),s(s){}
}t[N<<2];
node operator +(node a,node b){return node(max(a.l,b.l),min(a.r,b.r),min({a.s,b.s,b.r-a.l}));}
void update(int p,int u=1,int l=1,int r=mx)
{
    if(l==r){t[u]=node(max(sl[l]),min(sr[l]));return;}
    int mid=(l+r)>>1;
    if(p<=mid) update(p,u<<1,l,mid);
    else update(p,u<<1|1,mid+1,r);
    t[u]=t[u<<1]+t[u<<1|1];
}
inline void erase(multiset<int>&x,int y){x.erase(x.find(y));}
int main()
{
    int q;scanf("%d",&q);
    multiset<int>L,R;
    while(q --> 0)
    {
        char op[3];int l,r;scanf("%s%d%d",op,&l,&r);
        if(op[0]=='A') L.insert(l),R.insert(r),sl[r].insert(l),sr[l].insert(r);
        else erase(L,l),erase(R,r),erase(sl[r],l),erase(sr[l],r);
        update(l),update(r);
        if(max(L)<min(R)) printf("%d\n",min(sr[max(L)])-max(sl[min(R)]));
        else printf("%d\n",t[1].s);
    }
    return 0;
}

F. Shopping Plans

牛逼题。

首先当然组内排序。考虑先处理 $x_j=y_j=1$ 的部分，也就是说每个组只会选择一个数字。

一种很显然的做法是：维护每个序列指针和一个位置 $p$ 表示当前已经处理到 $p$ 对应组。每次从队列中取出最小值，将 $p$ 对应组往后移一位，或者选择一个 $p’>p$ 后移一维，容易证明是不重不漏的。复杂度 $O(n^2\log n)$。

可以发现这样非常浪费，因为每次都要枚举 $p’$，决策数量 $O(n)$。思考能不能一次只移动 $p’\leftarrow p+1$。

但是直接做是不行的，因为如果我们只让 $p’=p+1$，那么新状态实际上和原先相同。如果钦定 $p’$ 对应组移动一步，然而每一组不一定强制移动。

考虑增加一个“反悔”机制，即：如果 $p’=p+1$ 然而 $p$ 对应组只移动了恰好一步，我们可以认为这一步是为了转移“被迫的”，在令 $p’$ 移动一步的同时撤销 $p$ 的移动。

不过这样要求对于 $p’>p$，$p’$ 移动第一步一定要比 $p$ 移动第一步要优，因为我们无法在 $p$ 移动第一步之前将 $p’$ 放入堆。所以开始时将组按 $a_2-a_1$ 从小到大排序即可。复杂度 $O(k\log k)$。

考虑 $m=1$ 的部分，即需要对组内处理。首先枚举所有可行长度 $L\in[x_i,y_i]$，将前 $L$ 个字符加入初始队列。
队列中维护 $l,r,p$，表示当前在修改 $p$，其中 $p$ 从 $l$ 位置开始，不能超过 $r$。每次操作可以：将 $p$ 后移一位，或者将 $l$ 设置为 $l-1$，同时 r=p , p=l-1。这样每次只有两种决策，复杂度 $O(k\log k)$。

最后对于正解，将每个组当成一个黑箱子，可以发现黑箱子中的操作只有输出下一个的解，这恰好就是 $m=1$ 时求的东西，直接两层 $k$ 短路即可。复杂度 $O(k\log k)$。

代码 
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
#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#include<algorithm>
#include<queue>
#define N 200010
#define ll long long
#define inf 100000000000000
#define S(x) ((int)x.size())
using namespace std;
vector<int>f[N];int l[N],r[N];
struct sta{
    int l,r,p;ll s;
    sta(int l=0,int r=0,int p=0,ll s=0):l(l),r(r),p(p),s(s){}
    bool operator <(const sta a)const{return s>a.s;}
};
struct node{
    priority_queue<sta>q;
    vector<int>h;
    void init(int u)
    {
        h.swap(f[u]);
        ll s=0;r[u]=min(r[u],S(h));
        if(l[u]==0) q.push(sta());
        for(int i=0;i<r[u];i++)
        {
            s+=h[i];
            if(i+1>=l[u]) q.emplace(i,S(h),i,s);
        }
    }
    vector<ll>res;
    ll operator [](int x)
    {
        while(x>=S(res))
        {
            while(!q.empty() && x>=S(res))
            {
                sta u=q.top();q.pop();
                res.push_back(u.s);
                if(u.p+1<u.r) q.emplace(u.l,u.r,u.p+1,u.s+h[u.p+1]-h[u.p]);
                if(u.p!=u.l && u.l>0) q.emplace(u.l-1,u.p,u.l,u.s+h[u.l]-h[u.l-1]);
            }
            if(x>=S(res)) return inf;
        }
        return res[x];
    }
}g[N];
int id[N];
struct sta2{
    int p,x;ll s;
    sta2(int p=0,int x=0,ll s=0):p(p),x(x),s(s){}
    bool operator <(const sta2 a)const{return s>a.s;}
};
priority_queue<sta2>q;
int main()
{
    int n,m,k;
    scanf("%d%d%d",&n,&m,&k);
    for(int i=1,x,y;i<=n;i++) scanf("%d%d",&x,&y),f[x].push_back(y);
    for(int i=1;i<=m;i++) scanf("%d%d",&l[i],&r[i]),sort(f[i].begin(),f[i].end()),g[i].init(i),id[i]=i;
    cerr<<"start"<<endl;
    sort(id+1,id+m+1,[&](int x,int y){return g[x][1]-g[x][0]<g[y][1]-g[y][0];});
    ll s=0;
    for(int i=1;i<=m;i++) s+=g[i][0];
    if(s>=inf){while(k --> 0) puts("-1");return 0;}
    printf("%lld\n",s);k--;
    q.emplace(1,1,s+g[id[1]][1]-g[id[1]][0]);
    while(k --> 0)
    {
        sta2 u=q.top();q.pop();int i=id[u.p],j=id[u.p+1];
        if(u.s>=inf){puts("-1");while(k --> 0) puts("-1");return 0;}
        printf("%lld\n",u.s);
        q.emplace(u.p,u.x+1,u.s+g[i][u.x+1]-g[i][u.x]);
        if(u.p<m) q.emplace(u.p+1,1,u.s+g[j][1]-g[j][0]);
        if(u.p<m && u.x==1) q.emplace(u.p+1,1,u.s+g[j][1]-g[j][0]-(g[i][1]-g[i][0]));
    }
    return 0;
}