CSP-S2022解题报告

A. 假期计划

题意：有一个无向图，点有点权。定义两个节点“可达”当且仅当这两个节点的最短路不超过 $k+1$。求一组互不相同的节点 $\{a,b,c,d\}$ 使得 $1\leftrightarrow a\leftrightarrow b\leftrightarrow c\leftrightarrow d\leftrightarrow 1$ 每步均可达且这四个点的点权和尽可能大。$n\le 2500$。

首先跑 $n$ 遍 BFS，预处理出每两个点的距离。然后我们可以考虑枚举中间两个节点 $b,c$，处理边上两个节点 $a,d$。首先中间两个节点必须是可达的，否则跳过；然后需要满足 $1\leftrightarrow a\leftrightarrow b$，$c\leftrightarrow d\leftrightarrow 1$。由于“可达”是双向的，我们可以对每个节点 $x$ 预处理出所有满足 $1\leftrightarrow y\leftrightarrow x$ 的节点 $y$ 的集合并按 $y$ 的点权从大到小排序。于是容易想到，当我们枚举了 $b,c$ 时，只需要独立地考虑最大的 $v[a]$ 满足 $1\leftrightarrow a\leftrightarrow b$ 和最大的 $v[d]$ 满足 $1\leftrightarrow d\leftrightarrow c$ 即可。但事实并非如此。有可能对于最大的 $v[a]$，$a=c$，或对于最大的 $v[a],v[d]$，$a=d$，这些都会产生冲突（因为要求互不相同），于是可能需要跳过一些节点。容易证明对于 $b,c$ 只需要考虑前三大的即可，所以乘一个 $9$ 的常数暴力判断。

#include<bits/stdc++.h>
using namespace std;
#define int long long
int v[2510];
vector<int> a[2510];
bool e[2510][2510];
vector<int> to[2510];
bool vis[2510];
signed main() {
    int n,m,kk;
    scanf("%lld%lld%lld",&n,&m,&kk);
    for(int i=2;i<=n;i++)
        scanf("%lld",&v[i]);
    for(int i=1;i<=m;i++) {
        int x,y;
        scanf("%lld%lld",&x,&y);
        a[x].push_back(y);
        a[y].push_back(x);
    }
    for(int i=1;i<=n;i++) {
        memset(vis,0,sizeof(vis));
        queue<pair<int,int> > q;
        q.push({i,0});
        while(!q.empty()) {
            auto u=q.front();q.pop();
            if(u.second>kk+1) break;
            if(vis[u.first]) continue;
            vis[u.first]=1,e[i][u.first]=1;
            for(int v:a[u.first])
                if(!vis[v]) q.push({v,u.second+1});
        }
    }
    for(int i=2;i<=n;i++) {
        for(int j=2;j<=n;j++)
            if(i!=j&&e[i][j]&&e[1][j])
                to[i].push_back(j);
        sort(to[i].begin(),to[i].end(),[&](int x,int y) {
            return v[x]>v[y];
        });
    }
    int ans=0;
    for(int i=2;i<=n;i++)
        for(int j=i+1;j<=n;j++) {
            if(!e[i][j]) continue;
            for(int k=0;k<min(3ll,(int)to[i].size());k++)
                for(int l=0;l<min(3ll,(int)to[j].size());l++)
                    if(to[i][k]!=j&&to[j][l]!=i&&to[i][k]!=to[j][l])
                        ans=max(ans,v[i]+v[j]+v[to[i][k]]+v[to[j][l]]);
        }
    printf("%lld\n",ans);
    return 0;
}

B. 策略游戏

题意：给你两个数组 $a(n),b(m)$，每次询问 $l_1,r_1,l_2,r_2$，进行如下博弈：第一个人先选一个 $i\in[l_1,r_1]$，第二个人再选一个 $j\in[l_2,r_2]$，其中第一个人想使 $a_i\cdot b_j$ 最大，第二个人相反。求最终结果。$n,m,q\le 10^5$。

容易发现，此题可以直接分类讨论正负后贪心。如果第一个人选正数，那么第二个人一定会选能选的最小的数。如果第二个人能选到负数则一定会选，此时第一个人选的正数越小越好，否则越大越好。如果第一个人选负数，那么第二个人一定会选最大值。如果第二个人能选到正数则一定会选，此时第一个人选的越大（即越接近 $0$）越好，否则越小越好。

实现上，可以使用线段树维护两个序列的正数最大值、最小值和负数最大值、最小值，每次区间询问合并区间信息即可。

#include<bits/stdc++.h>
using namespace std;
int a[2][100010];
#define mid (t[now].l+t[now].r)/2
#define lson now*2
#define rson now*2+1
struct node {
    int l,r,maxp,minp,maxn,minn;
    bool havep,haven;
    node():havep(0),haven(0){}
};
struct segtree {
    node t[400010];
    node merge(node x,node y) {
        node res;
        res.l=x.l,res.r=y.r;
        res.havep=(x.havep||y.havep);
        res.haven=(x.haven||y.haven);
        if(x.havep&&y.havep) {
            res.maxp=max(x.maxp,y.maxp);
            res.minp=min(x.minp,y.minp);
        }
        else if(x.havep||y.havep) {
            res.maxp=x.maxp*x.havep+y.maxp*y.havep;
            res.minp=x.minp*x.havep+y.minp*y.havep;
        }
        if(x.haven&&y.haven) {
            res.maxn=max(x.maxn,y.maxn);
            res.minn=min(x.minn,y.minn);
        }
        else if(x.haven||y.haven) {
            res.maxn=x.maxn*x.haven+y.maxn*y.haven;
            res.minn=x.minn*x.haven+y.minn*y.haven;
        }
        return res;
    }
    void build(int now,int l,int r,bool flag) {
        t[now].l=l,t[now].r=r;
        if(l==r) {
            if(a[flag][l]>=0) {
                t[now].havep=1;
                t[now].maxp=t[now].minp=a[flag][l];
            }
            else {
                t[now].haven=1;
                t[now].maxn=t[now].minn=a[flag][l];
            }
            return;
        }
        build(lson,l,mid,flag);
        build(rson,mid+1,r,flag);
        t[now]=merge(t[lson],t[rson]);
    }
    node query(int now,int l,int r) {
        if(l<=t[now].l&&r>=t[now].r) return t[now];
        node res;
        if(l<=mid) res=merge(res,query(lson,l,r));
        if(r>mid) res=merge(res,query(rson,l,r));
        return res;
    }
} T1,T2;
void chkmax(long long &x,long long y) {x=(x>y)?x:y;}
int main() {
    int n,m,q;
    scanf("%d%d%d",&n,&m,&q);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[0][i]);
    for(int i=1;i<=m;i++)
        scanf("%d",&a[1][i]);
    T1.build(1,1,n,0);
    T2.build(1,1,m,1);
    while(q--) {
        int l1,r1,l2,r2;
        scanf("%d%d%d%d",&l1,&r1,&l2,&r2);
        node A=T1.query(1,l1,r1);
        node B=T2.query(1,l2,r2);
        long long ans=-1e18;
        if(A.havep) {
            if(B.haven) chkmax(ans,1ll*A.minp*B.minn);
            else chkmax(ans,1ll*A.maxp*B.minp);
        }
        if(A.haven) {
            if(B.havep) chkmax(ans,1ll*A.maxn*B.maxp);
            else chkmax(ans,1ll*A.minn*B.maxn);
        }
        printf("%lld\n",ans);
    }
    return 0;
}

C. 星战

题意：有一张简单的有向图（不保证连通），每条边有可用和不可用两种状态，初始每条边都可用。定义一个图是合法的，当且仅当：

1. 从每个点开始都存在一个合适的移动方式使得能够无限移动下去。
2. 每个点有且仅有一条出边。

你需要进行 $q$ 次操作，每次如下：

1. 给出 $u,v$，将 $u\to v$ 变为不可用。保证此前处于可用状态。
2. 给出 $u$，将所有 $x\to u$ 全部变为不可用。
3. 给出 $u,v$，将 $u\to v$ 变为可用。保证此前处于不可用状态。
4. 给出 $u$，将所有 $x\to u$ 全部变为可用。

每次操作后回答这张图是否合法。$n,m,q\le 5\times 10^5$。

可以发现，合法的限制一是没有用的。因为如果满足了限制二，该有向图一定为一个基环内向树森林，于是每个节点必然可以通向一个环。可以通过反证法简单地证明：如果存在某个点不能无限移动下去，设它的终点为 $x$，根据限制二，$x$ 必然有出边，故不能成为终点，与假设矛盾。

于是问题转化为每次操作后判断是否每个点的出度均为 $1$。

我们考虑通过哈希来维护这一过程。我们给每个点赋一个随机权值，维护当前每条边起点的权值和 $nowsum$ 并预处理所有点的权值和 $all$。此时如果 $nowsum=all$ 等于每个点的权值和，我们就可以认为每个点恰有一个出边。

对于暴力连边和断边的操作，可以直接在 $nowsum$ 上加减。但是对于断点和恢复点的操作我们没法维护。所以考虑增加维护的状态。定义 $now_i$ 为当前可用的、以 $i$ 为终点的所有起点权值和；$sum_i$ 为所有（包括不可用）以 $i$ 为终点的起点权值和。于是，最终方案如下：

1. 暴力连断边：根据定义，$nowsum$ 增/减 $x$ 的权值，$now_y$ 同样增/减 $x$ 的权值。
2. 删点、恢复点：使用 $now_x$ 和 $sum_x$ 计算出 $nowsum$ 需要改变的值，更新即可。

可以感性理解成势能和动能的转化：$now_i$ 维护每个终点的势能（即其起点的权值和），势能越大，删掉该点时 $nowsum$ 就会减少更多。连边和断边相当于直接更改其终点的势能，而连点和断点相当于将其势能归零/回满。

#include<bits/stdc++.h>
using namespace std;
long long a[500010],sum[500010],now[500010];
signed main() {
    srand(time(0));
    int n,m,q;
    scanf("%d%d",&n,&m);
    long long nowsum=0,all=0;
    for(int i=1;i<=n;i++) a[i]=rand(),all+=a[i];
    for(int i=1;i<=m;i++) {
        int x,y;
        scanf("%d%d",&x,&y);
        sum[y]+=a[x],now[y]+=a[x],nowsum+=a[x];
    }
    scanf("%d",&q);
    while(q--) {
        int op,x,y;
        scanf("%d%d",&op,&x);
        if(op==1||op==3) scanf("%d",&y);
        if(op==1) now[y]-=a[x],nowsum-=a[x];
        else if(op==2) nowsum-=now[x],now[x]=0;
        else if(op==3) now[y]+=a[x],nowsum+=a[x];
        else nowsum+=sum[x]-now[x],now[x]=sum[x];
        if(nowsum==all) puts("YES");
        else puts("NO");
    }
    return 0;
}

D. 数据传输

题意：给你一个树，第 $i$ 个点有点权 $v_i(>0)$，定义一次跳跃是合法的，当且仅当跳跃的两个节点的距离不超过 $k$。每次询问给出两个节点 $s,t$，你需要考虑一个从 $s$ 走到 $t$ 的方案 $s\to c_1\to c_2\to\cdots\to t$ 使得每步跳跃都合法。输出经过的点的最小点权和（即 $\min\limits_c\{s+\sum c+t\}$）。$n,q\le 2\times 10^5,k\le 3$。

首先考虑最简单的 $k=1$ 的情况。此时每步跳跃只能沿着边走，所以答案即为路径上的点权和。可以使用 LCA 和树上差分计算。

对于 $k=2$，我们可以把路径拉出来，每次跳一步或跳两步，通过简单的 $O(n)$ DP 来计算答案（虽然复杂度不可行）。考虑这个做法的正确性：一定是在两点间路径上跳吗？答案是一定的。如果不在两点间路径上跳，情况一定如下图：

我们可以从 $2$ 跳到 $5$ 再跳到 $4$，但这样一定不如从 $2$ 直接跳到 $4$ 优。

对于 $k=3$，情况就变得麻烦多了。此时跳到路径外变得可行了，如下图：

此时如果点 $6$ 的权值比 $2,3,4$ 小，那么最优策略将是 $1\to 6\to 5$。这就导致了我们上一节的 DP 变得不可行。我们考虑加强上面的过程。这次不只是单独把这一条链拉出来，还要把这条链周围一格的点也拉出来一起考虑。容易证明，这条链周围两格的节点是没有考虑的意义的，证明与上面 $k=2$ 链外无意义类似。

然后我们考虑扩展 DP 状态：定义 $f[i][j\in\{0,1,2\}]$ 表示只考虑链上前 $i$ 个点及其周围一格的点，而当前跳到了一个距离 $i$ 为 $j$ 的点上的最小代价。接着考虑转移：

$f[i][0]$。此时就在第 $i$ 个节点本身。可以从第 $i-1$ 个节点本身转移而来，也可以从“与第 $i-1$ 个节点距离为 $1$ 的节点”转移而来（此时需要跳两格），也可以从“与第 $i-1$ 个节点距离为 $2$ 的节点”转移而来（此时需要跳三格）。故：$f[i][0]=\min(f[i-1][0]+v_i,f[i-1][1]+v_i,f[i-1][2]+v_i)$。

$f[i][1]$。此时我们在“与第 $i$ 个节点距离为 $1$ 的节点”上。这有哪些可能性呢？如下图：

此时当前所在的位置有 $i-1,a,b,i+1$ 四种可能性。对于在 $i-1$ 的情况，可以由 $f[i-1][0]$ 转移过来（即保持不动）；对于其他情况，我们只能从 $c$ 或 $i-2$（与 $i-1$ 距离为 $1$ 的点）转移，而不能从 $i-1$ 本身转移。这是因为，如果我们从 $i-1\to a$，下一步往上跳一格后往右至多跳两格，而此时可以直接从 $i-1$ 跳三格过去更优，所以不应从 $i-1\to a$。综上，$f[i][1]=\min(f[i-1][0],f[i-1][1]+mn_i)$，其中 $mn_i$ 为 $i$ 节点的邻居中最小的点权（都在 $i$ 周围的点没有本质区别，自然权值越小越好）。$mn$ 可以预处理出来。

$f[i][2]$。此时在 $c$ 或 $i-2$，距离 $i-1$ 为 $1$，所以直接由 $f[i-1][1]$ 转移而来。$f[i][2]=f[i-1][1]$。

结合以上分析，我们得到了如下的 DP 方程：

$$\begin{aligned} f[i][0]&=\min(f[i-1][0]+v_i,f[i-1][1]+v_i,f[i-1][2]+v_i)\\ f[i][1]&=\min(f[i-1][0],f[i-1][1]+mn_i)\\ f[i][2]&=\min(f[i-1][1]) \end{aligned}$$

（最后一个为了统一格式也用 $\min$）容易发现，$f[i]$ 的三个状态完全由 $f[i-1]$ 的三个状态以及其他仅与 $i$ 有关的贡献转移而来。我们可以想到使用矩阵来优化这一步骤。我们新定义一个矩阵乘法：$[A\cdot B]_{i,j}=\min\limits_k\{A_{i,k}+B_{k,j}\}$。此矩阵乘法同样具有结合律：

$$\begin{aligned} (A\cdot (B\cdot C))_{i,j}&=\min\limits_k\{A_{i,k}+(B\cdot C)_{k,j}\}\\ &=\min\limits_k\left\{A_{i,k}+\min\limits_p\{B_{k,p}+C_{p,j}\}\right\}\\ &=\min\limits_k\left\{\min\limits_p\{A_{i,k}+B_{k,p}+C_{p,j}\}\right\}\\ &=\min\limits_p\left\{\min\limits_k\{A_{i,k}+B_{k,p}+C_{p,j}\}\right\}\\ &=\min\limits_p\left\{\min\limits_k\{A_{i,k}+B_{k,p}\}+C_{p,j}\right\}\\ &=\min\limits_p\{(A\cdot B)_{i,p}+C_{p,j}\}\\ &=((A\cdot B)\cdot C)_{i,j} \end{aligned}$$

这是一个经典的矩阵乘法的定义：内层相加，外层极值。于是，我们可以把 DP 转移转化为下面的矩阵乘法：

$$\begin{bmatrix} f[i][0] & f[i][1] & f[i][2] \end{bmatrix} = \begin{bmatrix} f[i-1][0] & f[i-1][1] & f[i-1][2] \end{bmatrix} \cdot \begin{bmatrix} v_i & 0 & +\infty\\ v_i & mn_i & 0\\ v_i & +\infty & +\infty \end{bmatrix}$$

在 $k=2$ 时也类似，转移矩阵稍微改变一下即可。将 DP 变为矩阵的转化直接使得在每个点的转移变得独立，而与具体路径完全无关。

由于结合律，问题转化为求路径上每个节点的矩阵乘积。由于树上的路径可以分为向上的一段和向下的一段，我们考虑倍增求树上 ST 表。定义 $g[i][j]$ 为一个矩阵，表示从第 $i$ 个点开始，往上连续 $2^j$ 个点的矩阵乘积，可以在预处理 LCA 时顺便完成 $g$ 的预处理。同时，定义 $h[i][j]$ 与 $g[i][j]$ 类似，只不过保存的是从上往下乘的结果。最终答案即为向上的总转移矩阵乘向下的总转移矩阵，再乘 $s$ 时的初始状态，使用树上倍增即可。时间复杂度 $qn\log(n)\times k^3$。

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,q,k,v[200010];
struct matrix {
    int n,a[3][3];
    matrix operator*(matrix o) {
        matrix res;
        res.n=n;
        for(int i=0;i<n;i++)
            for(int j=0;j<n;j++) {
                res.a[i][j]=1e18;
                for(int k=0;k<n;k++)
                    res.a[i][j]=min(res.a[i][j],a[i][k]+o.a[k][j]);
            }
        return res;
    }
} f[200010][20],g[200010][20];
vector<int> e[200010];
int fa[200010][20],mn[200010],dep[200010];
void dfs(int now,int father,int depth) {
    fa[now][0]=father,dep[now]=depth;
    f[now][0].n=k;
    auto &t=f[now][0].a;
    for(int i=0;i<3;i++)
        t[i][0]=v[now];
    t[0][1]=t[1][2]=0;
    t[1][1]=mn[now];
    t[2][1]=t[0][2]=t[2][2]=1e18;
    if(k==2) t[1][1]=1e18;
    g[now][0]=f[now][0];
    for(int to:e[now])
        if(to!=father) dfs(to,now,depth+1);
}
int LCA(int x,int y) {
    if(dep[x]<dep[y]) swap(x,y);
    for(int i=19;i>=0;i--)
        if(dep[fa[x][i]]>=dep[y])
            x=fa[x][i];
    if(x==y) return x;
    for(int i=19;i>=0;i--)
        if(fa[x][i]!=fa[y][i])
            x=fa[x][i],y=fa[y][i];
    return fa[x][0];
}
signed main() {
    memset(mn,0x3f,sizeof(mn));
    scanf("%lld%lld%lld",&n,&q,&k);
    matrix init;
    init.n=k;
    for(int i=0;i<k;i++)
        for(int j=0;j<k;j++)
            init.a[i][j]=(i!=j)*1e18;
    for(int i=1;i<=n;i++)
        scanf("%lld",&v[i]);
    for(int i=1;i<n;i++) {
        int x,y;
        scanf("%lld%lld",&x,&y);
        e[x].push_back(y);
        e[y].push_back(x);
        mn[x]=min(mn[x],v[y]);
        mn[y]=min(mn[y],v[x]);
    }
    dfs(1,0,1);
    for(int x=0;x<=19;x++)
        f[0][x]=g[0][x]=init;
    for(int j=1;j<=19;j++)
        for(int i=1;i<=n;i++) {
            fa[i][j]=fa[fa[i][j-1]][j-1];
            f[i][j]=f[i][j-1]*f[fa[i][j-1]][j-1];
            g[i][j]=g[fa[i][j-1]][j-1]*g[i][j-1];
        }
    while(q--) {
        int s,t;
        scanf("%lld%lld",&s,&t);
        int lca=LCA(s,t),x=v[s];
        s=fa[s][0];
        matrix tmp1=init,tmp2=init;
        for(int i=19;i>=0&&s;i--)
            if(dep[fa[s][i]]+1>=dep[lca])
                tmp1=tmp1*f[s][i],s=fa[s][i];
        for(int i=19;i>=0&&t;i--)
            if(dep[fa[t][i]]>=dep[lca])
                tmp2=g[t][i]*tmp2,t=fa[t][i];
        matrix ans=tmp1*tmp2;
        printf("%lld\n",ans.a[0][0]+x);
    }
    return 0;
}