题解

noip半年集训day7

写在前面

这一阶段的最后一次考试,再一次考崩了,这六轮考试第二次考崩,说明自己还是不够强啊,不过没关系,有的题做不出来还是有原因的,反思一下,补足短板才能继续走下去呐。

A.Suqare

日常一道送分题,怎么做都能过系列,我也不浪费时间给大家解释人人都会的水题了,直接贴代码吧。

代码

#include <cstdio>
#include <algorithm>
#include <climits>
const int MAXN = 100;
int main(int argc, char *argv[]) {
    int n;
    scanf("%d", &n);
    int x, y;
    int maxX = 0, maxY = 0;
    int minX = 101, minY = 101;
    for (int i = 1; i <= n; i++) {
        scanf("%d %d", &x, &y);
        maxX = std::max(x, maxX);
        maxY = std::max(y, maxY);
        minX = std::min(x, minX);
        minY = std::min(y, minY);
    }
    int weight = maxX - minX;
    int height = maxY - minY;
    int ans = std::max(height, weight) * std::max(height, weight);
    printf("%d\n", ans);
    return 0;
}

B.Game

题意就是说求基环树森林的最大点独立集。
然而我考场上并没有看出来这是基环树森林,甚至yy除了一个按照度数排序的假做法。
看不出来是基环树森林也只能说自己水平低,见得少啊,下次要加油啊。
如果看出来的话绝对是能写出来的,毕竟都写过带权的ZJOI2008骑士,但是看不出来是基环树确实很窒息了……
具体做法见我写的带权升级版的题解。
那就贴代码吧。

代码

#include <cstdio>
#include <climits>
#include <cmath>
#include <algorithm>
#include <iostream>
const int MAXN = 5e5 + 7;
struct Edge {
    int t, next;
} edge[MAXN];
int n, ans;
int head[MAXN], cnt;
int f[MAXN][2];
int fa[MAXN];
bool vis[MAXN];
inline int max(int a, int b) {
    return a > b ? a : b;
}
inline void read(int &x) {
    int flag = 1, ret = 0;
    char ch = getchar();
    while (!isdigit(ch)) {
        if (ch == '-') flag = -1;
        ch = getchar();
    }
    while (isdigit(ch)) {
        ret = ret * 10 + ch - '0';
        ch = getchar();
    }
    x = flag * ret;
}
void add(int u, int v) {
    edge[++cnt] = (Edge){v, head[u]}; head[u] = cnt;
}
void dfs(int u, int root) {
    f[u][1] = 1;
    f[u][0] = 0;
    vis[u] = true;
    for (register int e = head[u]; e; e = edge[e].next) {
        int v = edge[e].t;
        if (v == root) {
            f[v][1] = INT_MIN;
            continue;
        }
        dfs(v, root);
        f[u][1] += f[v][0];
        f[u][0] += max(f[v][1], f[v][0]);
    }
}
void find(int u) {
    while (!vis[u]) {
        vis[u] = true;
        u = fa[u];
    }
    dfs(u, u);
    register int tmp = max(f[u][1], f[u][0]);
    u = fa[u];
    dfs(u, u);
    ans += max(tmp, max(f[u][1], f[u][0]));
}
int main(int argc, char *argv[]) {
    read(n);
    int v;
    for (register int i = 1; i <= n; i++) {
        read(v);
        add(v, i);
        fa[i] = v;
    }
    for (register int i = 1; i <= n; i++) {
        if (!vis[i]) find(i);
    }
    printf("%d\n", ans);
    return 0;
}

C.Dorm

很容易看出来每一栋楼都是独立的,没什么相互之间没有任何关系,所以我们只需要分配每一栋楼清空多少次就可以了。

以下为我考场上的假做法

然而,已经看出来这么多的我在考场又双叒叕写了假的贪心,写了发按照总人数的贪心,维护一个堆,每次把人最多这栋楼从中间这个时间点切成两半,再把这两半插进堆里。
这个贪心仔细想一想,错的很显然,因为这样每次切一半对于每一栋楼来说甚至不是最优的。

正解开始

设 $f_{i,j}$ 表示前 $i$ 栋楼共清空 $j$ 次的最小噪声。
那么转移很显然:
$$f_{i,j} = \min \lbrace f_{i-1,j-k}+cost(i,\ k)$$
现在问题在于 $cost$ 如何计算,其实很显然,对于一栋楼分固定的次数 $k$ 的话,最优的方案数一定是尽可能地平均分,所以 $cost$ 可以 $O(1)$ 地算出来。
转移的时间复杂度是 $O(1)$,总状态也很少,这样就可以通过了。

代码

#include <cstdio>
#include <climits>
#include <algorithm>
#include <cstring>
#include <cctype>
typedef long long ll;
const int MAXN = 500 + 7;
ll f[MAXN][MAXN];
int t[MAXN];
int n, m, k;
ll c(int a) {
    return 1ll * a * (a + 1ll) / 2ll;
}
ll cal(int n, int k) {
    k++;
    int small = n / k, big = small + 1;
    int cbig = n % k, csmall = k - n % k;
    return 1ll * c(small) * csmall + 1ll * c(big) * cbig;
}
inline int read() {
    int f = 1, r = 0;
    char c = getchar();
    while (!isdigit(c)) {
        if (c == '-') f = -1;
        c = getchar();
    }
    while (isdigit(c)) {
        r = r * 10 + c - '0';
        c = getchar();
    }
    return r * f;
}
int main(int argc, char *argv[]) {
    n = read(), m = read(), k = read();
    for (int i = 1; i <= n; i++) {
        t[read()]++;
    }
    for (int i = 1; i <= m; i++) {
        for (int j = 0; j <= k; j++) {
            f[i][j] = f[i - 1][j] + c(t[i]);
            for (int j2 = 1; j2 <= std::min(j, t[i]); j2++) {
                f[i][j] = std::min(f[i][j], 1ll * f[i - 1][j - j2] + 1ll * cal(t[i], j2));
            }
        }
    }
    printf("%lld\n", f[m][k]);
    return 0;
}

D.Truck

题面的意思就是说给你一棵边有边权的数,和若干特定的点,求从所有点开始,按照任意顺序经过这些特定的点的最小边权和。
首先,树上的边最多走两次,再走多了显然是在做无用功,然后我们不必回到起点,所以有一条路径我们可以只走一次,既然只有一条可以少走一次,那肯定是最长的那条少走。对于要走的总边权和,子树内的可以一遍 $dfs$ 求出来,子树外的可以运用 $up\ and\ down$ 的做法求出;对于最长的那条路径,也是可以 $up\ and\ down$ 求出来的。
总的来说就是道有点麻烦的树形 $dp$。
$zyb$ 讲的虚树做法看起来很难写的样子,他给的代码我看得也有点云里雾里,所以就在这里不丢人了,最后还是参考了 $\text{Akoasm}$ 聚聚的代码。
对于每个点,通过一遍 $dfs$ 预处理出两个数组 $furthest_i$ 和 $dis_i$, 分别表示表示点 $i$ 到其子树内的某一特定点的最长的路径(如果子树内有的话),以及到子树内所有点的边权和。
然后再一遍 $dfs$ 把信息都推下去,$dfs$ 的时候需要记录如下信息:

  1. 当前点 $u$;
  2. 父节点 $pre$;
  3. 子树的特定点外到该点的距离和 $sum$;
  4. 子树外特定点到该点的最长路就 $maxBranch$;
  5. 子树外到该点的路径条数$num$,最大为 $1$,(因为一个树上的点只有一个父亲);

然后对于当前点 $u$,$ans_u = 2 \times (dis_u+sum) – maxBranch$。
代码细节非常多,写错一点就会 $gg$。
主要是需要讨论第二遍 $dfs$ 的时候,如何传 $maxBranch$ 和 $sum$ 这两个参数。
首先,从 $u$ 往 $v$ 传$maxBranch$的时候, 可以从父亲过来,也可以从其他子树过来。如果是从父亲过来的话,就是点 $u$ 的 $maxBranch$,否则就是子树内最长链,即 $furthest_u$,但是如果最长链在 $v$ 的子树里就出现错误了,所以还需要计算子树内不相交的次长链。
其次,一定要注意记录 $num$,如果为 $0$ 的话。就要清空 $sum$,不然一定会出事。
最后,注意子树内没有特定点的地方,记得加上边权 $(u,\ v)$。

代码

#include <cstdio>
#include <climits>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <iostream>
typedef long long ll;
const int MAXN = 5e5 + 7;
struct Edge {
    int t, w, next;
} edge[MAXN << 1];
int n, k;
int head[MAXN], cnt;
ll dis[MAXN], ans[MAXN], max[MAXN];
bool col[MAXN];
void add(int u, int v, int w) {
    edge[++cnt] = (Edge){v, w, head[u]}; head[u] = cnt;
}
void dfs(int u, int pre) {
    for (int e = head[u]; e; e = edge[e].next) {
        int v = edge[e].t;
        if (v == pre) continue;
        dfs(v, u);
        if (col[v]) {
            dis[u] += edge[e].w + dis[v];
            max[u] = std::max(max[u], 1ll * edge[e].w + max[v]);
            col[u] = true;
        }
    }
}
void dfs(int u, int pre, ll sum, ll maxBranch, int num) {
    ans[u] = (dis[u] + sum) * 2 - std::max(max[u], maxBranch);
    ll subMax = LLONG_MIN;
    for (int e = head[u]; e; e = edge[e].next) {
        int v = edge[e].t;
        if (v == pre) continue;
        if (!col[v]) continue;
        sum += edge[e].w + dis[v];
        ll tmp = edge[e].w + max[v];
        subMax = std::max(subMax, tmp);
        if (subMax > maxBranch) std::swap(subMax, maxBranch);
        num++;
    }
    for (int e = head[u]; e; e = edge[e].next) {
        int v = edge[e].t;
        if (v == pre) continue;
        if (col[v]) {
            ll sumOfsubTree = sum - dis[v];
            if (num == 1) {
                sumOfsubTree = 0;
            }
            if (edge[e].w + max[v] == maxBranch) {
                dfs(v, u, sumOfsubTree, subMax + edge[e].w, std::min(1, num));
            } else {
                dfs(v, u, sumOfsubTree, maxBranch + edge[e].w, std::min(1, num));
            }
        } else {
            dfs(v, u, sum + edge[e].w, maxBranch + edge[e].w, std::min(1, num));
        }
    }
}
int main(int argc, char *argv[]) {
    scanf("%d %d", &n, &k);
    int u, v, w;
    for (int i = 1; i < n; i++) {
        scanf("%d %d %d", &u, &v, &w);
        add(u, v, w);
        add(v, u, w);
    }
    for (int i = 1; i <= k; i++) {
        scanf("%d", &u);
        col[u] = true;
    }
    dfs(1, 0);
    dfs(1, 0, 0ll, LLONG_MIN, 0);
    for (int i = 1; i <= n; i++) {
        printf("%lld\n", ans[i]);
    }
    return 0;
}

写在最后

终于写完惹 $\text{QAQ}$

发表评论

电子邮件地址不会被公开。 必填项已用*标注