NOIP 2018 提高组题解

发表于 | | 阅读次数:
字数统计: 3k 字
退役选手的 NOIP 2018 提高组题解 QAQ

题面

Day1

Day2

数据

下载地址：NOIP 2018 提高组测试数据

铺设道路

Description

有 $n$ 个连续的区域，第 $i$ 个区域下陷的深度为 $d_i$。你每次可以选择一段连续的区间 $[L,R]$，使这段区间内每个区域的深度减少 $1$，但是必须保证任何时刻 $d_i\geqslant 0$。求将所有区域的深度都变为 $0$ 的最短时间。

数据范围：$1\le n\le 10^5$，$0\le d_i\le 10^4$

Solution

我在考场上的第一个反应就是分治，对于当前区间找到最小值，这个最小值一定把区间拆成了若干段，对这些段递归计算。

时间复杂度：$O(n\log n)$

其实此题还有另一个结论：$\sum_{i=1}^n \max(0,d_i-d_{i-1})$，其中 $d_0=0$。

这个结论可以用递推证明，令 $f_i$ 表示填好前 $i$ 个区域所需的最短时间。那么我们对当前的 $d_i$ 分类讨论。

  • 如果 $d_i\le d_{i-1}$，那么我们可以在填 $d_{i-1}$ 时顺便把 $d_i$ 填好，即 $f_i=f_{i-1}$。
  • 如果 $d_i>d_{i-1}$，那么我们需要单独把 $d_i$ 高出的部分填上，即 $f_i=f_{i-1}+(d_i-d_{i-1})$。

由于我们需要的只是 $f_n$，所以就是上面那个式子了！

时间复杂度：$O(n)$

Code

第一种做法：

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 <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>

const int N=1e5+5,D=1e4+5;
int n,a[N],st[N][20],Log[N],ans;
std::vector<int> b[D];

void init() {
    memset(st,0x3f,sizeof(st));
    for(int i=1;i<=n;++i) st[i][0]=a[i],b[a[i]].push_back(i);
    for(int i=0;(1<<i)<=n;++i) Log[1<<i]=i;
    for(int i=1;i<=n;++i) Log[i]=std::max(Log[i-1],Log[i]);
    for(int j=1;(1<<j)<=n;++j) for(int i=1;i+(1<<j)-1<=n;++i) {
        st[i][j]=std::min(st[i][j-1],st[i+(1<<(j-1))][j-1]);
    }
}
int query(int l,int r) {
    int k=Log[r-l+1];
    return std::min(st[l][k],st[r-(1<<k)+1][k]);
}
void solve(int l,int r,int lst) {
    if(l>r) return;
    int mn=query(l,r);
    ans+=mn-lst;
    int st=std::lower_bound(b[mn].begin(),b[mn].end(),l)-b[mn].begin();
    int ed=std::upper_bound(b[mn].begin(),b[mn].end(),r)-b[mn].begin();
    int p=l-1;
    for(int i=st;i<ed;++i) solve(p+1,b[mn][i]-1,mn),p=b[mn][i];
    solve(p+1,r,mn);
}
int main() {
    scanf("%d",&n);
    for(int i=1;i<=n;++i) scanf("%d",&a[i]);
    init();
    solve(1,n,0);
    printf("%d\n",ans);
    return 0;
}

第二种做法：

1
2
3
4
5
6
7
8
9
 
#include <cstdio>

int main() {
    int n,ans=0;
    scanf("%d",&n);
    for(int x,p=0;n--;p=x) scanf("%d",&x),x>p&&(ans+=x-p);
    printf("%d\n",ans);
    return 0;
}

货币系统

Description

有 $n$ 种不同面额的货币，第 $i$ 种货币的面额为 $a_i$，每种货币都有无限张，我们把这个货币系统记作 $(n,a)$。两个货币系统 $(n,a)$ 和 $(m,b)$ 是等价的，当且仅当对于任意的非负整数 $x$，要么能被两个货币系统都表示出来，要么两者都无法表示。

现在给出一个货币系统 $(n,a)$，你需要求出一个货币系统 $(m,b)$ 使得两者等价并最小化 $m$。

本题 $T$ 组数据。

数据范围：$1\le T\le 20$，$1\le n\le 100$，$1\le a_i\le 25000$

Solution

通过感性证明可以得到：新的货币系统内的货币一定属于原来的货币系统。

那么我们把货币从小到大排序，如果某个货币 $a_i$ 能被之前的货币表示出来，那么这个 $a_i$ 一定是多余的；否则 $a_i$ 一定属于新的货币系统。这个过程显然用一个完全背包就能实现了！（我在考场竟然写了一个 $\text{bitset}$ 优化的多重背包 QAQ）

时间复杂度：$O(n\cdot a_i)$

Code

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
 
#include <cstdio>
#include <cstring>
#include <algorithm>

const int N=105;
int n,a[N];
bool f[25005];

int main() {
    int T;
    for(scanf("%d",&T);T--;) {
        scanf("%d",&n);
        int mx=0;
        for(int i=1;i<=n;++i) scanf("%d",&a[i]),mx=mx>a[i]?mx:a[i];
        std::sort(a+1,a+n+1);
        memset(f,0,sizeof(f));
        f[0]=1;
        int ans=0;
        for(int i=1;i<=n;++i) {
            if(!f[a[i]]) {
                ++ans;
                for(int j=a[i];j<=mx;++j) f[j]|=f[j-a[i]];
            }
        }
        printf("%d\n",ans);
    }
    return 0;
}

赛道修建

Description

C 城要举办赛车比赛，需要在城内修建 $m$ 条赛道。C 城有 $n$ 个路口和 $n-1$ 条适合修建赛道的双向通行的道路，第 $i$ 条道路的长度为 $l_i$，所有路口都直接或间接连通。一条赛道由一组互不相同的道路组成，满足从起点出发依次经过这些道路到达终点。一条赛道的长度等于经过的各道路的长度之和。为保证安全，要求每条道路至多被一条赛道经过。

你的任务是设计一种赛道修建的方案，使得修建的 $m$ 条赛道中长度最小的赛道长度最大。

数据范围：$2\le n\le 5\times 10^4$，$1\le m<n$，$1\le l_i\le 10^4$

Solution

首先，看到“最大化最小值”可以想到二分答案 $ans$，那么将问题转化为：是否可以选择 $m$ 条长度至少是 $ans$ 的链。

考虑以 $u$ 为根的子树，最优解中有一些链完全在子树内部，还可能有一条链经过 $u$ 向子树外扩展。在子树内部的链的数量相同的情况下，我们肯定要尽量使可以往上扩展的链尽可能长（如果没有，那么这个长度就是 $0$）。

我们用 $f(x)$ 表示子树 $x$ 内部最多有多少条链，$g(x)$ 表示当子树内部链最多时，剩下的以 $x$ 结尾的链最长是多少。

考虑怎么用这两个值进行转移。对于 $u$ 的每个孩子 $v$，它为 $u$ 提供了长度为 $len(v)=g(v)+w(u,v)$ 的可以用于拼接的链，以及 $f(v)$ 的答案。如果 $len(v)\geqslant ans$，那么可以直接选择这条链并使答案 $f(u)$ 增加 $1$。否则我们可以选择两条满足 $len(v_1)+len(v_2)\geqslant ans$ 的链进行匹配并使答案 $f(u)$ 增加 $1$，接下来我们分析选择两条链匹配的问题。

我们要使得 $len(v)$ 匹配的对数最多。这显然就是一个双指针贪心的过程。但是我们还要使剩下的一条链尽可能长。那我们稍微改变一下算法：每次考虑 $len$ 最小的 $v$，并找到最小的 $len(v’)$ 满足 $len(v)+len(v’)\geqslant ans$（如果不存在就不考虑 $v$ 这条链），把 $v$ 和 $v’$ 这两条链进行匹配。这样这样把所有的 $len(v)$ 匹配完之后，可以证明 $g(u)$ 就是未匹配的最长的链。

时间复杂度：$O(n\log n\log T)$（其中 $T$ 为二分答案的值域，上界为 $\sum l_i$）

Code

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
 
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <set>

const int N=5e4+5,M=1e5+5;
int n,m,len,tot,lnk[N],ter[M],nxt[M],val[M];
int f[N],g[N];

void add(int u,int v,int w) {
    ter[++tot]=v,nxt[tot]=lnk[u],val[tot]=w,lnk[u]=tot;
}
void dfs(int u,int fa) {
    std::vector<int> p;
    std::multiset<int> s;
    for(int i=lnk[u];i;i=nxt[i]) {
        int v=ter[i];
        if(v==fa) continue;
        dfs(v,u);
        f[u]+=f[v];
        int sum=g[v]+val[i];
        if(sum>=len) ++f[u];
        else s.insert(sum),p.push_back(sum);
    }
    std::sort(p.begin(),p.end());
    for(int i=0;i<(int)p.size()&&!s.empty();++i) {
        std::multiset<int>::iterator now=s.find(p[i]);
        if(now==s.end()) continue;
        std::multiset<int>::iterator nxt=s.lower_bound(len-p[i]);
        if(nxt==now) ++nxt;
        if(nxt==s.end()) continue;
        if(*now+*nxt>=len) {
            s.erase(now),s.erase(nxt);
            ++f[u];
        }
    }
    if(!s.empty()) g[u]=*s.rbegin();
}
bool check() {
    memset(f,0,sizeof(f));
    memset(g,0,sizeof(g));
    dfs(1,0);
    return f[1]>=m;
}
int main() {
    scanf("%d%d",&n,&m);
    int l=0,r=0;
    for(int i=1;i<n;++i) {
        int u,v,w;
        scanf("%d%d%d",&u,&v,&w);
        add(u,v,w),add(v,u,w);
        r+=w;
    }
    int ans=0;
    while(l<=r) {
        len=(l+r)>>1;
        if(check()) ans=len,l=len+1; else r=len-1;
    }
    printf("%d\n",ans);
    return 0;
}

旅行

Description

X 国有 $n$ 个城市，之间有 $m$ 条双向道路（不存在重边和自环，保证所有城市直接或间接连通）。小 Y 的旅行方案如下：任意选定一个城市作为起点，然后从起点开始沿道路走向一个没有去过的城市，或者沿着第一次访问该城市时经过的道路后退到上一个城市。在小 Y 的旅行方案中，每个城市都要被访问到。

小 Y 在第一次访问某个城市时，会记录下这个城市的编号，这样会形成一个长度为 $n$ 的序列，你需要求出字典序最小的序列。

数据范围：$1\le n\le 5000$，$m=n-1$ 或 $m=n$

Solution

由于每次访问一个新的点（除了起点），一定会经过一条新的边。除了起点，我们一共要访问 $n-1$ 个点，那么会有 $n-1$ 条边，所以最终的路径会形成一棵生成树。

我们对 $m=n-1$ 和 $m=n$ 的情况分开考虑。

  • 当 $m=n-1$ 时

    我们一定选择编号为 $1$ 的点作为起点，可以发现题目中的限制等价于对原图进行 $\text{DFS}$，形成的序列就是 $\text{DFS}$ 序，我们要让 $\text{DFS}$ 序字典序最小，那么只需要对儿子节点排序，按照编号从小到大访问即可。

    时间复杂度：$O(n\log n)$

  • 当 $m=n$ 时

    根据之前证明的结论，我们可以知道一定有一条边不会被经过。那么我们只要枚举这条边。如果剩下的是一棵树，那么就按照树的方法进行 $\text{DFS}$，在所有情况中取字典序最小的作为答案。注意：并不是每次 $\text{DFS}$ 都需要进行排序，我们可以事先对每个节点的相邻节点排序。

    时间复杂度：$O(n^2)$

然而这题是可以优化到 $O(n\log n)$ 的！

如果我们把环单独考虑，那么在每棵树上肯定是正常走，走到环上之后肯定会走较小的那一条边。因此我们可以把环找出来，很容易确定下来在环上的走的方向，接下来就可以直接 $\text{DFS}$ 求解了！

Code

第一种做法：

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
 
#include <cstdio>
#include <cstring>
#include <algorithm>

const int N=5005;
int n,m,tot,sz[N],e[N][N],ans[N],now[N],du,dv;
bool vis[N],flg;

bool check(int u,int v) {
    return !((u==du&&v==dv)||(u==dv&&v==du));
}
bool cmp() {
    for(int i=1;i<=n;++i) {
        if(now[i]<ans[i]) return 1;
        if(now[i]>ans[i]) return 0;
    }
    return 0;
}
bool dfs(int u) {
    ++tot;
    if(u<ans[tot]) flg=1;
    if(u>ans[tot]&&!flg) return 1;
    now[tot]=u,vis[u]=1;
    for(int i=1;i<=sz[u];++i) {
        int v=e[u][i];
        if(!vis[v]&&check(u,v)) if(dfs(v)) return 1;
    }
    return 0;
}
int main() {
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;++i) {
        int u,v;
        scanf("%d%d",&u,&v);
        e[u][++sz[u]]=v,e[v][++sz[v]]=u;
    }
    for(int i=1;i<=n;++i) std::sort(e[i]+1,e[i]+sz[i]+1);
    ans[1]=5001;
    if(m==n-1) {
        dfs(1);
        memcpy(ans,now,sizeof(now));
    } else {
        for(int i=1;i<=n;++i) {
            du=i;
            for(int j=1;j<=sz[i];++j) {
                dv=e[i][j];
                if(dv>du) continue;
                memset(vis,0,sizeof(vis)),tot=flg=0;
                dfs(1);
                if(tot==n&&cmp()) memcpy(ans,now,sizeof(now));
            }
        }
    }
    for(int i=1;i<=n;++i) printf("%d%c",ans[i]," \n"[i==n]);
    return 0;
}

第二种做法：

1
 
// 我也不会写啊 QAQ

填数游戏

咕咕咕

保卫王国

咕咕咕

0%