YBOI-3题解

· · 题解

J3-T1

设 4x+k=n 且 k< 4，那么填 k 个 5，剩下填 4 时是 5 最少的方案，此后可以 4 个一组的增加 5 的数量，来替换掉 5 个 4。

可以增加的次数为 \frac{x-k}{5}，答案在其基础上 +1 即可。

注意若 x<k 则 4 的数量不足以换足够的 5，此时答案为 0。

难度：中位橙

J3-T2

注意到 a_i\in\{0,1\}，那么 \prod a_i\in\{0,1\}，于是分类讨论：

对于子段内 1 的数量，前缀和即可。

所有修改方法取 \min 即可。

仅给出核心代码：

for(int i=1;i<=n;i++)
    cin>>a[i],s[i]=s[i-1]+a[i];
while(q--){
    cin>>l>>r>>k;
    if(s[r]-s[l-1]==r-l+1&&r-l+1==k+1)
        cout<<abs(k+1-(s[r]-s[l-1]))<<'\n';
    else if(r-l+1<=k)
        cout<<-1<<'\n';
    else
        cout<<abs(k-(s[r]-s[l-1]))<<'\n';
}

难度：高位橙

J3-T3

其实无向无环联通图就是树，题目背景里有提及推广做法，发现与中位数所求相似，于是推广做法至本题。

具体来说，问题转化为求令所有子树大小最大值最小的点。

不妨设 f_u 为以 u 为根时的最大子树，设 sz_u 为以 u 为根的子树的大小。

先钦定 1 为根。

记 v 为 u 的儿子，显然有转移：

f_u=\max_{v} sz_v sz_u=\sum_v sz_v

考虑父亲节点的贡献：

f_u=\max(f_u,n-sz_u)

此时取到最小的 f_u 的 u 就是所求的 i，有了 i 之后计算 S(u) 便是容易的。

给出核心代码：

void dfs(int u,int fa){
    sz[u]=1;
    for(int v:g[u]){
        if(v==fa) continue;
        dfs(v,u);
        f[u]=max(f[u],sz[v]);
        sz[u]+=sz[v];
    }
    f[u]=max(f[u],n-sz[u]);
}

难度：中位黄

S3-T1

记 V=2\times 10^6。

不妨设 f_i 为考虑到位置 i 的最大长度和。

考虑讲 (x,y) 按 x 排序，若相同则按 y 排序。

设目前考虑到了 (x_i,y_i)，则有：

f_{y_i}=\max_{j=0}^{x_i-1} f_j+y_i-x_i+1

此时是 O(nV) 的。

考虑使用树状数组维护 f_j 的前缀最大值，答案为 \max_{i=1}^V f_i。

这就是出题人的 O(n\log V) 做法。

其实注意到转移式中的 f_j 是静态的，直接线性求前缀最大值即可，可以做到 O(n\log n+V)，瓶颈在于排序。

进一步的思考，值域不大，考虑按 x 计数排序，再对相同的 x 按 y 排序，在随机数据下近似 O(n+V)。

给出核心代码：

//计数排序
for(int i=1;i<=n;i++) g[a[i].x].push_back(a[i].y);
for(int i=0;i<M;i++) sort(g[i].begin(),g[i].end());
for(int i=0;i<M;i++)
    for(int j:g[i])
        a[++p].x=i,a[p].y=j;
//dp
for(int i=1;i<=n;i++){
    while(now<a[i].x) maxn=max(maxn,f[now++]);
    int res=maxn+a[i].y-a[i].x+1;
    f[a[i].y]=max(res,f[a[i].y]);
    ans=max(ans,res);
}

难度：中位绿

S3-T2

设 f_{i,j} 为 i 单位时间后在 j 路口的方案数，有转移：

f_{i,j}=f_{i-1,j-1}+f_{i-1,j+1}

特别的，f_{i,5}=0。

注意到转移式可以转为矩阵形式：

0&1&0&0&0&0&0&1\\ 1&0&1&0&0&0&0&0\\ 0&1&0&1&0&0&0&0\\ 0&0&1&0&1&0&0&0\\ 0&0&0&0&0&0&0&0\\ 0&0&0&0&1&0&1&0\\ 0&0&0&0&0&1&0&1\\ 1&0&0&0&0&0&1&0\\ \end{matrix}\right]

然后矩阵乘法即可，时间复杂度为 O(w^3\log n)，w=8。

从另一个角度思考，设 f_i 为第 i 秒到第 5 路口的方案数。

显然走偶数单位时间才能到达，由上面的转移式可以推出（中间可以自己推，懒得写了）：

f_i=4f_{i-2}-2f_{i-4}

按此构造矩阵，则 w=2。

难度：中位蓝

后两题做法过于抽象，想学习者找我问。