NOIP 2018 Day1

简介

第一天题目总体来说是这些年中比较简单的。
三个题目都被说是原题。
牛客版的数据

T1 铺设道路

题目背景

本题主要考察了数学。
本题和NOIP2013第一天第一题一模一样，数据范围，输入输出格式，标程做法，题目主人公。
只是题意有微小的差别。

题目大意

输入一个数组$a_i$，每次可以选择一个区间，使区间内的数字都减少$1$。
希望把所有数字都变成$0$，问最少需要几次操作。

题目做法

求差分，考虑差分中所有正数的和。（同时也是所有负数和的相反数）

参考代码

#include <bits/stdc++.h>
using namespace std;
int n, z, x, l;
int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%d", &x);
        z += max(x - l, 0);
        l = x;
    }
    printf("%d\n", z);
    return 0;
}

T2 货币系统

题目背景

本题主要考察了完全背包和动态规划。
这个题被说BZOJ 2914一样，我觉得这个题比BZOJ 2914简单许多。

题目大意

输入$n$个面值$a_i$这些面值可以凑出一些金额。
问能凑出这样的金额至少需要几个面值。
$n \leq 100, a_i \leq 25000$

题目做法

将所有面值排序。
面值最小的一定要选。
如果用面值最小的凑不出面值第二小的，那么要选第二小的。（如果凑的出，就不用选）
对于面值$x$，如果用比$x$小的面值凑不出$x$，就需要选$x$（如果凑的出，就不用选）
凑得出凑不出，这是一个完全背包问题，时间复杂度是$O(n \times a_i)$。

还有另一个做法，直接完全背包DP出凑出每个金额的方案数，判断每个面值的方案数是否为1，方案数要取模，或者是自由越界。这个方法应该是可以被卡掉的，但是出题人放过去了。

参考代码

排序DP的做法。

#include <bits/stdc++.h>
using namespace std;
int f[25020];
int a[120];
int t, n;
int main() {
    scanf("%d", &t);
    for (int tt = 0; tt < t; tt++) {
        scanf("%d", &n);
        for (int i = 0; i < n; i++) {
            scanf("%d", &a[i]);
        }
        sort(a, a + n);
        memset(f, 0, sizeof f);
        f[0] = 1;
        int z = 0;
        for (int i = 0; i < n; i++) {
            if (f[a[i]] == 0) {
                z++;
                for (int j = a[i]; j <= a[n - 1]; j++) {
                    f[j] |= f[j - a[i]];
                }
            }
        }
        printf("%d\n", z);
    }
    return 0;
}

方案数的做法

#include <bits/stdc++.h>
using namespace std;
int f[25020];
int a[120];
int t, n;
int main() {
    scanf("%d", &t);
    for (int tt = 0; tt < t; tt++) {
        scanf("%d", &n);
        for (int i = 0; i < n; i++) {
            scanf("%d", &a[i]);
        }
        sort(a, a + n);
        memset(f, 0, sizeof f);
        f[0] = 1;
        int z = 0;
        for (int i = 0; i < n; i++) {
            for (int j = a[i]; j <= a[n - 1]; j++) {
                f[j] = (f[j] + f[j - a[i]]) % 10007;
            }
        }
        for (int i = 0; i < n; i++) {
            if (f[a[i]] == 1) {
                z++;
            }
        }
        printf("%d\n", z);
    }
    return 0;
}

T3 赛道修建

题目背景

本题主要考察了二分和树形动态规划。
这个题被说BZOJ 2067一样，我觉得这个题比BZOJ 2067非常类似。
都是先二分，再树形DP，每个点再需要二分更新。

题目大意

输入一棵$n$个点的树，有边权，从中找出$m$个边不相交的链（点可以相交），使得最短的链最长。
$n \leq 50000, m < n$

题目做法

首先看到最短的链最长，显然想到是一个二分。
然后看到$n$的范围，每个点应该只有常数个状态。
这个题目在DFS中有一个排序，之后的部分一个比较简答的写法是二分
（因为已经有排序了，并不增加复杂度）
另一个想法就是参考代码中的直接扫两遍。

参考代码

#include <bits/stdc++.h>
using namespace std;
int n, m, x, y, z, M, cnt;
vector<pair<int, int> > a[50020];

int dfs(int x, int y) {
    vector<int> b;
    for (int i = 0; i < a[x].size(); i++) {
        if (a[x][i].first != y) {
            int l = dfs(a[x][i].first, x) + a[x][i].second;
            if (l >= M) {
                cnt++;
            } else {
                b.push_back(l);
            }
        }
    }
    b.push_back(0);
    sort(b.begin(), b.end(), greater<int>());
    int res = 0, ret = -1;
    int L = 0, R = b.size() - 1;
    while (L < R) {
        if (b[L] + b[R] >= M) {
            L++;
            R--;
            res++;
        } else {
            R--;
        }
    }
    cnt += res;
    L = res;
    R = res + 1;
    int tmp = 0;
    while (R <= 2 * res) {
        if (b[L] + b[R] >= M) {
            L--;
            R++;
        } else {
            if (tmp == 0) {
                tmp++;
                ret = b[L];
                L--;
            } else if (tmp == 1) {
                tmp++;
                break;
            }
        }
    }
    if (tmp == 0) {
        return b[0];
    } else if (tmp == 1) {
        return ret;
    }
    L = 0;
    R = 2 * res;
    while (L < R) {
        if (b[L] + b[R] >= M) {
            L++;
            R--;
        } else {
            return b[R];
        }
    }
    return b[R];
}
bool ok() {
    cnt = 0;
    dfs(1, 0);
    return cnt >= m;
}
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i < n; i++) {
        scanf("%d%d%d", &x, &y, &z);
        a[x].push_back(make_pair(y, z));
        a[y].push_back(make_pair(x, z));
    }
    int L = 0, R = 1e9;
    while (L < R - 1) {
        M = (L + R) / 2;
        if (ok()) {
            L = M;
        } else {
            R = M;
        }
    }
    printf("%d\n", L);
    return 0;
}