NOIP 2018 提高组题解

浙江菜鸡选手的 NOIP 2018 提高组题解!


铺设道路

Description

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

数据范围:$1\le n\le 10^5$,$0\le d_i\le 10^4$。

Solution

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

时间复杂度:$\mathcal 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$,所以就是上面那个式子了!

时间复杂度:$\mathcal O(n)$。

Code

第一种做法:

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>

const int N = 1e5 + 5, M = 1e4 + 5, logN = 20;

int n, a[N], f[N][logN], lg[N], ans;
std::vector<int> b[M];

void build() {
    memset(f, 0x3f, sizeof(f));
    for (int i = 1; i <= n; i++) {
        f[i][0] = a[i];
        b[a[i]].push_back(i);
    }
    for (int i = 2; i <= n; i++) lg[i] = lg[i >> 1] + 1;
    for (int j = 1; (1 << j) <= n; j++) {
        for (int i = 1; i + (1 << j) - 1 <= n; i++) {
            f[i][j] = std::min(f[i][j - 1], f[i + (1 << (j - 1))][j - 1]);
        }
    }
}
int query(int l, int r) {
    int k = lg[r - l + 1];
    return std::min(f[l][k], f[r - (1 << k) + 1][k]);
}
void solve(int l, int r, int last) {
    if (l > r) return;
    int mn = query(l, r);
    ans += mn - last;
    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() - 1;
    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]);
    }
    build();
    solve(1, n, 0);
    printf("%d\n", ans);
    return 0;
}

第二种做法:

#include <cstdio>
#include <algorithm>

int main() {
    int n, ans = 0;
    scanf("%d", &n);
    for (int y = 0, i = 1; i <= n; i++) {
            int x;
        scanf("%d", &x);
        ans += std::max(x - y, 0);
        y = x;
    }
    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)

时间复杂度:$\mathcal O(n\cdot a_i)$。

Code

#include <cstdio>
#include <cstring>
#include <algorithm>

const int N = 105, M = 3e4 + 5;

int n, a[N];
bool f[M];

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 = std::max(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)\ge ans$,那么可以直接选择这条链并使答案 $f(u)$ 增加 $1$。否则我们可以选择两条满足 $len(v_1)+len(v_2)\ge ans$ 的链进行匹配并使答案 $f(u)$ 增加 $1$,接下来我们分析选择两条链匹配的问题。

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

时间复杂度:$\mathcal O(n\log n\log T)$,其中 $T$ 为二分答案的值域,上界为 $\sum l_i$。

Code

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <set>

const int N = 5e4 + 5, M = 1e5 + 5;

int n, m, tot, lnk[N], ter[M], nxt[M], val[M], f[N], g[N];

void add(int u, int v, int w) {
    ter[++tot] = v, nxt[tot] = lnk[u], lnk[u] = tot, val[tot] = w;
}
void dfs(int u, int p, int len) {
    std::vector<int> t;
    std::multiset<int> s;
    for (int i = lnk[u]; i; i = nxt[i]) {
        int v = ter[i];
        if (v == p) continue;
        dfs(v, u, len);
        int sum = g[v] + val[i];
        f[u] += f[v];
        if (sum >= len) {
            f[u]++;
        } else {
            s.insert(sum);
            t.push_back(sum);
        }
    }
    std::sort(t.begin(), t.end());
    for (int x: t) {
        if (s.empty()) break;
        std::multiset<int>::iterator l = s.find(x);
        if (l == s.end()) continue;
        std::multiset<int>::iterator r = s.lower_bound(len - x);
        if (l == r) r++;
        if (r == s.end()) continue;
        if (*l + *r >= len) {
            f[u]++, s.erase(l), s.erase(r);
        }
    }
    if(!s.empty()) g[u] = *s.rbegin();
}
bool check(int len) {
    memset(f, 0, sizeof(f));
    memset(g, 0, sizeof(g));
    dfs(1, 0, len);
    return f[1] >= m;
}
int main() {
    scanf("%d%d", &n, &m);
    int l = 0, r = 0, ans = 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;
    }
    while (l <= r) {
        int mid = (l + r) >> 1;
        if(check(mid)) {
            l = (ans = mid) + 1;
        } else {
            r = mid - 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}$ 序字典序最小,那么只需要对儿子节点排序,按照编号从小到大访问即可。
  • 当 $m=n$ 时
    根据之前证明的结论,我们可以知道一定有一条边不会被经过。那么我们只要枚举这条边。如果剩下的是一棵树,那么就按照树的方法进行 $\text{DFS}$,在所有情况中取字典序最小的作为答案。注意:并不是每次 $\text{DFS}$ 都需要进行排序,我们可以事先对每个节点的相邻节点排序。

时间复杂度:$\mathcal O(n^2)$。

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

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

时间复杂度:$\mathcal O(n\log n)$。

Code

第一种做法:

#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;
    vis[now[tot] = 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;
                tot = flg = 0;
                memset(vis, 0, sizeof(vis));
                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;
}

第二种做法:

// 我也不会写啊 QAQ

填数游戏

咕咕咕


保卫王国

咕咕咕

发表评论