2022.11.30 杭州集训Day2 考试记录

2022秋 2022杭州集训

考场得分：

T1 Max Tree

考点：树形DP

用时：$8:00$ to $10:00$

得分：$100pts$

Description

给定一棵 $n$ 个点的树，点有点权，定义路径的权值为路径上点的权值和，请在其中选择 $k$ 个点 $a_{1\dots k}$，使得两两之间的路径权值和最大。$n,k\leq 4\times 10^3$。

Solution

签到题，但调了很久。

树形背包再也不要滚动了！！！

统计一堆路径点权和，容易想到拆成每个点对答案的贡献，也就是这个点被经过了几次。

那么设：$f[i][j][0/1]$ 表示 $i$ 这棵子树中，选了 $j$ 个点，根选或不选。

转移可以随便转移，注意树形背包的复杂度别写假，注意别滚动。

Summary

树形背包再也不要滚动了！！！

Code

//The Code Is From Dawn
#include<bits/stdc++.h>
#define int long long
using namespace std;
inline int read() {
    int x = 0;
    char c = getchar();
    bool f = 0;
    while(!isdigit(c)) f |= (c == '-'), c = getchar();
    while(isdigit(c)) x = (x * 10) + (c ^ 48), c = getchar();
    return f ? -x : x;
}
inline void write(int x){
    if(x<0){putchar('-');x=-x;}
    if(x>9)write(x/10);
    putchar(x%10+'0');
}
inline void writeln(int x){write(x); puts("");}
inline void writepl(int x){write(x); putchar(' ');}
const int maxn = 4005, INF = 1e18 + 7;
int n, K;    
int a[maxn];
struct node {
    int v, nex;
}edge[maxn << 1];
int head[maxn], len, Siz[maxn], f[maxn][maxn][2], Cnt[maxn][2];
inline void make_map(int u, int v) {
    len++;
    edge[len].nex = head[u];
    edge[len].v = v;
    head[u] = len;
}
inline void Search(int x, int fa) {
    Siz[x] = 1, f[x][0][0] = f[x][1][1] = 0;
    for(register int i = head[x]; i; i = edge[i].nex) {
        int y = edge[i].v;
        if(y == fa) continue;
        Search(y, x);
    }
    for(register int i = head[x]; i; i = edge[i].nex) {
        int y = edge[i].v;
        if(y == fa) continue;
        for(register int j = 0; j <= min(K, Siz[x] + Siz[y]); ++j) Cnt[j][0] = Cnt[j][1] = -INF;
        for(register int j = 0; j <= min(K, Siz[x]); ++j)
            for(register int k = 0; k <= min(K - j, Siz[y]); ++k) 
                for(register int op = 0; op < 2; ++op) Cnt[j + k][op] = max(Cnt[j + k][op], f[x][j][op] + f[y][k][0] + j * k * a[x]);
        Siz[x] += Siz[y];
        for(register int j = 0; j <= min(K, Siz[x]); ++j)
            for(register int op = 0; op < 2; ++op) f[x][j][op] = Cnt[j][op];
    }
    for(register int i = 0; i <= min(K, Siz[x]); ++i) {
        for(register int op = 0; op < 2; ++op) f[x][i][op] += i * (K - i) * a[x];
        f[x][i][0] = max(f[x][i][0], f[x][i][1]);
    }
}
signed main() {
    freopen("tree.in", "r", stdin);
    freopen("tree.out", "w", stdout);
    n = read(), K = read();
    for(register int i = 1; i <= n; ++i) a[i] = read();
    for(register int i = 1; i <= n; ++i) { 
        for(register int j = 0; j <= K; ++j) f[i][j][0] = f[i][j][1] = -INF;
        f[i][0][0] = f[i][1][1] = 0;
    }
    for(register int i = 1; i < n; ++i) {
        int u = read(), v = read();
        make_map(u, v), make_map(v, u);
    }    
    Search(1, 0);
    printf("%lld\n", f[1][K][0]);
    return 0;
}

T2 排列

考点：DP，观察性质

用时：$10:10$ to $12:30$

Description

给定一个 $n\times n$ 的矩阵 $c$，你需要构造出一个排列 $p$，定义它的生成区间集合 $S(p)=\{[p_i,p_{i+1}],p_i\le p_{i+1}\}$，生成序列 $a(p)_i=\sum_{[l,r]\in S(p)}[l\le i\le r]$，价值为 $v(p)=\sum_{i=1}^nc_{i,a(p)_i+1}$，最大化价值。$n\le 3\times 10^3$。

Solution

问题最大的一道题，不应该没做出来。

一开始就想到了差分，发现他每次从第 $i$ 行转到 第 $i + 1$ 行只能往左下，正下，右下三个位置走。

考虑 DP，但是发现有一些不合法的走法，想了很久。

后来二又告诉我这个做法是能做的，但是要把状态改一改，计入一个提前量，不是很会。

我们舍弃差分，但是仍然用到推出来的一些性质。

我们还是DP，考虑到这个生成序列由很多线段组成，我们尝试往这些线段加点，我们称一个线段封闭，代表他不再加点。

我们设：$f[i][j]$ 表示前 $i$ 个点，有 $j$ 个未封闭的线段的答案，四种转移：

• 封闭一个线段，不开新线段：$f[i + 1][j - 1] = f[i][j] + c[i][j]$
• 不封闭线段，新开一个线段：$f[i + 1][j + 1] = f[i][j] + c[i][j + 1]$
• 封闭一个线段，开一个新线段：$f[i + 1][j] = f[i][j] + c[i][j + 1]$
• 不封闭线段，也不新开新线段：$f[i + 1][j] = f[i][j] + c[i][j]$

第 $1,3$ 个操作需要有未封闭的线段。

Summary

一直在想那个差分，没想到可以直接DP

Code

//The Code Is From Dawn
#include<bits/stdc++.h>
#define int long long
using namespace std;
inline int read() {
    int x = 0;
    char c = getchar();
    bool f = 0;
    while(!isdigit(c)) f |= (c == '-'), c = getchar();
    while(isdigit(c)) x = (x * 10) + (c ^ 48), c = getchar();
    return f ? -x : x;
}
const int maxn = 3005, INF = 1e18 + 7;
int n;
int a[maxn][maxn], f[maxn][maxn], Answer = -INF;
inline int Search(int x, int y) {
    if(f[x][y] != -1) return f[x][y];
    if(y < 1) return -INF;
    if(x > n && y > 1) return -INF;
    if(x > n && y <= 1) return 0;
    int Cnt = -INF;
    Cnt = max(Cnt, a[x][y] + Search(x + 1, y));
    Cnt = max(Cnt, a[x][y] + Search(x + 1, y - 1));
    if(y > 1) Cnt = max(Cnt, a[x][y + 1] + Search(x + 1, y));
    Cnt = max(Cnt, a[x][y + 1] + Search(x + 1, y + 1));
    return f[x][y] = Cnt;
}
signed main() {
    freopen("permutation.in", "r", stdin);
    freopen("permutation.out", "w", stdout);
    n = read();
    for(register int i = 1; i <= n; ++i)
        for(register int j = 1; j <= n; ++j) a[i][j] = read();
    memset(f, -1, sizeof(f));
    printf("%lld\n", Search(1, 1));
    return 0;
}

T3 圆

考点：平面图，分治，三角剖分，最短路，双指针

用时：$\varnothing$

得分：$0pts$

Description

给定一张 $n$ 个点的环图，边有边权，还有 $m$ 条额外边，也有边权。保证图是一张平面图。找到所有点对之间的最短路之和。
$n,m\leq 2\times 10^5$。

Solution

毒瘤分治题。

统计两两之间的答案，考虑分治。

我们考虑取一条边的两个点做分治中心，拿这条边将图割成两半，两边单独计算，我们现在只考虑跨过中线的答案。

由于是一个平面图，所以这两半的点之间的最短路一定经过这两个分治中心之一。

令分治中心为 $x,y$，一组跨过两半的点对为 $u,v$ 则 它们的最短路为 $\min(dis(u,x) + dis(v, x), dis(u, y) + dis(v, y))$

其中 $dis(u,x), dis(u,y)$ 可以直接以 $x, y$ 暴力跑最短路得到。

这个贡献两边都与 $u, v$ 两点有关，我们套路的希望将他们分开。

我们假设：$dis(u, x) + dis(v, x) < dis(u, y) + dis(v, y)$

则有：$dis(u, x) - dis(u, y) > dis(v, x) - dis(v, y)$

我们将每个点按照这个关键字从大到小排序。

也就是说，对于每个 $u$，我们考虑他前面和后面有多少个与他在不同半区的 $v$，假设后面有 $cnt$ 个，共有 $sum$ 个，那么 $u$ 的贡献为 $cnt \times dis(u,x) + (sum - cnt) \times dis(u, y)$

那么双指针扫一遍就行，接着就是分治下去。

但我们发现直接分治下去是不行的，因为有可能，同一个半区的两点间距离仍跨过了 $x,y$ 这样的最短距离你就统计不到了。

怎么办呢，我们考虑把 $x,y$ 这条边拆成两条，分给左部和右部，并把这条边的距离改成另一个半圈的距离。

然后我们就要考虑如何选取分治中心，以及如何保证复杂度了。

理论上分治中心怎么选算的答案都是对的，但为了降低复杂度，我们希望把两边的点分得尽量平均，即我们选取 $max(|L|,|R|)$ 最小的。

但这样还不够，我们需要进行一个神奇的操作——三角剖分。

这样是为了保证，我们找到的这个分治中心，他一定能找到一对点，满足 $\frac{n}{3} < |L| < \frac{n}{2}$，以保证复杂度正确。

复杂度证明可参考 hzk的blog。（懒得写了）

然后来简述一下三角剖分的大概过程。

我们找到所有度数为 $0$ 的点，注意在这里度数只记录非环边，把他们丢进一个队列中。

我们建一个链表，保存每个点的前驱与后继，每次拿出一个点，将其弹出，若他的前驱后继没非环边，则连一条长度为 $\text{INF}$ 的边，否则将前驱后继的度数都减 $1$，重新检查是否度数为 $0$，若为 $0$ 则加入队列。

这样做之后每个点都能在一个三角形内，这样无论怎么划分，都可以保证子集为很多个三角形组成，以保证复杂度。

Summary

分治的思想很经典，三角剖分完全没听过，贡献的计算可以积累。

Code

//The Code Is From Dawn
#include<bits/stdc++.h>
#define int long long
using namespace std;
inline int read() {
    int x = 0;0
    char c = getchar();
    bool f = 0;
    while(!isdigit(c)) f |= (c == '-'), c = getchar();
    while(isdigit(c)) x = (x * 10) + (c ^ 48), c = getchar();
    return f ? -x : x;
}
const int maxn = 2 * 1e5 + 5, INF = 1e18 + 7;
int n, m;
int Val[maxn], Du[maxn], L[maxn], R[maxn];
struct node {
    int u, v, w;
};
namespace Init {
    vector <node> E;
    vector <int> V;
    set <int> Point[maxn];
    inline void Trangle() {
        queue <int> Q;
        for(register int i = 1; i <= n; ++i) L[i] = i - 1, R[i] = i % n + 1;
        L[1] = n;
        for(register int i = 1; i <= n; ++i)
            if(!Du[i]) Q.emplace(i);
        while(!Q.empty()) {
            int x = Q.front(); Q.pop();
            int Left = L[x], Right = R[x];
            L[Right] = Left, R[Left] = Right;
            if(Left == Right || Right % n + 1 == Left) continue;
            if(!Point[Left].count(Right)) {
                Point[Left].insert(Right);
                E.emplace_back((node){Left, Right, INF});
            }
            else {
                Du[Left]--, Du[Right]--;
                if(!Du[Left]) Q.emplace(Left);
                if(!Du[Right]) Q.emplace(Right);
            }
        }
    }
    inline void Work() {
        n = read(), m = read();
        for(register int i = 1; i <= n; ++i) Val[i] = read();
        for(register int i = 1; i <= n; ++i) {
            int u = i, v = i % n + 1;
            E.emplace_back((node){u, v, Val[i]});
        }
        for(register int i = 1; i <= m; ++i) {
            int u = read(), v = read(), w = read();
            Point[u].emplace(v), Point[v].emplace(u);
            Du[u]++, Du[v]++, E.emplace_back((node){u, v, w});
        }
        Trangle();
        for(register int i = 1; i <= n; ++i) V.emplace_back(i);
    }
}
namespace Divide {
    vector < pair<int, int> > G[maxn];
    int Pos[maxn], Col[maxn], Dis1[maxn], Dis2[maxn], Vst[maxn], Sum[2], Num[2];
    inline bool cmp(int x, int y) { return Dis1[x] - Dis2[x] < Dis1[y] - Dis2[y]; }
    inline void Constr(vector <int> V, vector <node> E) {
        for(int i : V) G[i].clear();
        for(node i : E) G[i.u].emplace_back(make_pair(i.v, i.w)), G[i.v].emplace_back(make_pair(i.u, i.w));
    }
    inline void Dijstra(int S, int Dist[], vector <int> V) {
        priority_queue < pair<int, int> > Q;
        for(int i : V) Dist[i] = INF, Vst[i] = 0;
        Q.emplace(make_pair(0, S)), Dist[S] = 0;
        while(!Q.empty()) {
            int x = Q.top().second; Q.pop();
            if(Vst[x]) continue;
            Vst[x] = 1;
            for(pair<int, int> i : G[x]) {
                int y = i.first, z = i.second;
                if(Dist[y] > Dist[x] + z) {
                    Dist[y] = Dist[x] + z;
                    Q.emplace(make_pair(-Dist[y], y));
                }
            }
        }
    }
    inline int Solve(vector <int> V, vector <node> E) {
        if(V.size() == 1) return 0;
        if(V.size() == 2) return E[0].w;
        if(V.size() == 3) {
            int Answer = 0;
            Answer += min(E[0].w, E[1].w + E[2].w);
            Answer += min(E[1].w, E[0].w + E[2].w);
            Answer += min(E[2].w, E[0].w + E[1].w);
            return Answer;
        }
        int Answer = 0, maxx = -INF;
        node Mid = (node){0, 0, 0};
        for(register int i = 0; i < V.size(); ++i) Pos[V[i]] = i;
        for(node i : E) {
            int u = Pos[i.u], v = Pos[i.v];
            if(v < u) swap(u, v);
            int Cnt = min(v - u, (int)V.size() - (v - u));
            if(Cnt > maxx) maxx = Cnt, Mid = i;
        }
        if(Pos[Mid.u] > Pos[Mid.v]) swap(Mid.u, Mid.v);
        for(int i : V) Col[i] = 0;
        Col[Mid.u] = Col[Mid.v] = 2;
        for(register int i = Pos[Mid.u] + 1; i < Pos[Mid.v]; ++i) Col[V[i]] = 1;
        Constr(V, E), Dijstra(Mid.u, Dis1, V), Dijstra(Mid.v, Dis2, V); 
        vector <int> CntV = V;
        sort(V.begin(), V.end(), cmp);
        memset(Sum, 0, sizeof(Sum)), memset(Num, 0, sizeof(Num));
        for(int i : V) if(Col[i] < 2) Sum[Col[i]]++;
        for(register int i = 0, j = V.size() - 1; i < V.size(); ++i) {
            while(j >= 0 && Dis1[V[i]] + Dis1[V[j]] >= Dis2[V[i]] + Dis2[V[j]]) {
                if(Col[V[j]] < 2) Num[Col[V[j]]]++;
                j--;
            }
            int op = (Col[V[i]] ^ 1);
            if(Col[V[i]] < 2) Answer += Dis1[V[i]] * (Sum[op] - Num[op]) + Dis2[V[i]] * Num[op];
        }
        V = CntV;
        vector <int> LV, RV;
        vector <node> LE, RE;
        for(auto &i : E) {
            if(i.u == Mid.u) i.w = Dis1[i.v];
            if(i.u == Mid.v) i.w = Dis2[i.v];
            if(i.v == Mid.u) i.w = Dis1[i.u];
            if(i.v == Mid.v) i.w = Dis2[i.u];
        }
        for(int i : V) {
            if(Col[i] == 0 || Col[i] == 2) LV.emplace_back(i);
            if(Col[i] == 1 || Col[i] == 2) RV.emplace_back(i);
        }
        for(node i : E) {
            if((Col[i.u] == 0 || Col[i.u] == 2) && (Col[i.v] == 0 || Col[i.v] == 2)) LE.emplace_back(i);
            if((Col[i.u] == 1 || Col[i.u] == 2) && (Col[i.v] == 1 || Col[i.v] == 2)) RE.emplace_back(i); 
        }
        return Answer - Dis1[Mid.v] + Solve(LV, LE) + Solve(RV, RE);
    }
    inline void Work() { 
        printf("%lld\n", Solve(Init::V, Init::E)); 
    }
}
signed main() {
    freopen("circle.in", "r", stdin);
    freopen("circle.out", "w", stdout);
    Init::Work(), Divide::Work();
    return 0;
}