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\}

，于是分类讨论：

$\prod_{i=l}^r=1$ ，此时序列全 $1$ ， $\sum_{i=l}^r a_i=r-l+1=k+1$ ，特判即可。
$\prod_{i=l}^r=0$ ，此时 $\sum_{i=l}^r a_i=k$
- $k>r-l$ ，无解。
- $k=r-l$ ，仅存在 $1$ 个 $0$ 。
- $k<r-l$ ，存在 $k$ 个 $1$ 。
若子段里有 $x$ 个 $1$ ，目标为 $y$ 个，那么需修改 $|x-y|$ 次。

对于子段内

1

的数量，前缀和即可。

所有修改方法取

\min

即可。

仅给出核心代码：

CPP

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)

便是容易的。

给出核心代码：

CPP

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)

。

给出核心代码：

CPP

//计数排序
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$。 难度：中位蓝 #### 后两题做法过于抽象，想学习者找我问。

文章操作