官方题解 | 挑战赛20
本次题目的总体难度如下,各位选手可以借此评估一下自身的技术水平
题目编号 题目标题 难度 T1 小午的222 入门 T2 午枫的01树中心 普及- T3 午枫爱搬家2 普及- T4 午枫的又一个01串 普及/提高- T5 午枫的彩排 普及/提高- T6 午枫的字符串修改 普及/提高-
T1 小午的222
题目大意
有一个形如 x00...0x00...0x00...0 的数字,求这个数字可以分解出多少个 222 。
解题思路
本题输入的数字非常大,无法用 int 或 long long 存储,可以用 string 存储。
形如 x00…0x00\dots0x00…0 (x∈[1,9])(x\in[1,9])(x∈[1,9]) 的数字,可以看成 x×10×10×⋯×10x\times 10\times10\times \dots\times10x×10×10×⋯×10 ,而 10=2×510=2\times510=2×5 ,所以每个 101010 可以分解出一个 222 。那么这串数字有多少个 000 就能分解出多少个 222 ,剩下 xxx 单独分解一下,即可得到答案。
参考代码
T2 午枫的01树中心
题目大意
有一棵 010101 树,求有多少个节点与其周围所有节点的权值都不同。
解题思路
我们只需要在建好图后,对每一个点进行判断是否是中心节点。
判断每一个节点时,只需要遍历其周围所有距离为 111 的节点是否与他的权值不相同即可。
参考代码
T3 午枫爱搬家2
题目大意
有 nnn 件物品,每件物品有体积和价值两种属性,有一辆容量为 mmm 的卡车,求搬运的物品在没超过卡车容量的前提下最大能存放的价值。
解题思路
本题考虑用 010101 背包求解。
设 dpjdp_{j}dpj 表示消耗 jjj 的容积时,能得到的最大价值。
那么状态转移为 dpj=max(dpj,dpj−wi+vi)dp_{j}=max(dp_{j},dp_{j-w_i}+v_i)dpj =max(dpj ,dpj−wi +vi ) 。
参考代码
T4 午枫的又一个01串
题目大意
给定一个 010101 串,这个串的度为相邻两位元素不相同的个数,可以进行指定操作最多 mmm 次,求出最小度是多少。
解题思路
对于一个 010101 串,如果我们进行的操作区间不在开头也不在结尾,即 [l,r][l,r][l,r] 满足 1<l<r<n1<l<r<n1<l<r<n ,不难 sls_lsl 和 sl−1s_{l-1}sl−1 从不同变为相同,srs_rsr 和 sr***_{r****r+1 从不同变为相同。所以当我们对中间部分操作一次,度就会减 222 。
考虑完中间部分操作的影响,接下来考虑开头和结尾操作会有什么影响:
如果开头 s1=1s_1=1s1 =1 ,则无法操作,同理,如果结尾 sn=0s_n=0sn =0 也无法操作。
如果开头 s1=0s_1=0s1 =0 ,我们对区间 [1,r][1,r][1,r] (1<r<n)(1<r<n)(1<r<n) 做一次操作后,由于 s1s_1s1 前面没有数字了,原本就没有度,所以左端点的改变不会的度产生影响,srs_rsr 和 sr***_{r****r+1 从不同变为相同,因此此次操作会让度减少 111 。同理,对结尾 sn=1s_n=1sn =1 ,做一次操作也会让度减少 111 。
因此,先求出原串的度,优先对串的中间部分进行操作,在判断开头结尾的情况做出相应操作,计算度的减少量即可。
参考代码
T5 午枫的彩排
题目大意
有 nnn 名演员,每位演员有特定的入场时间和退场时间,还有自身的能力值。入场时会帮助所有还在场且能力值小于等于他的演员,他会获得 wi−minww_i-minwwi −minw 的评分。求所有演员的评分。
解题思路
由于演员的入场顺序和入场时间有关,我们可以将所有演员按照入场顺序从小到大排序。
按照能力值为第一关键字,退场时间为第二关键字放到优先队列中,按照从小到大的顺序排序,这样当我们遍历到某一位演员 xxx 时,优先队列中第一个退场时间大于 sxs_xsx 的演员的能力值既是当前场上能力值最小的一位演员。
时间复杂度 O(nlogn)O(nlogn)O(nlogn)
参考代码
T6 午枫的字符串修改
题目大意
给定一个初始串,有 qqq 次操作,求操作完之后的字符串。
解题思路
本题一共有两个操作,这里记第一种操作为 MMM ,第二种操作为 CCC 。
我们可以先考虑如果只有第一种操作 MMM 的话,我们可以用差分的思想完成对所有字符循环右移的移动量的记录。定义差分数组 ddd ,假设对区间 [l,r][l,r][l,r] 做一次 M(ti,x)M(t_i,x)M(ti ,x) 后,差分数组将进行以下变化:
d[l]=d[l]+xd[r+1]=d[r+1]−xd[l]=d[l]+x\\ d[r+1]=d[r+1]-x d[l]=d[l]+xd[r+1]=d[r+1]−x
最后用前缀和求出每一位的移动量即可得到最终的答案。
第一种操作我们用差分实现了,那么如果加上第二种操作,其实可以在第一种操作的基础上,记录整个字符串循环右移的偏移量 disdisdis 。假设做一次 C(s,x)C(s,x)C(s,x) 后,偏移量 dis=dis+xdis=dis+xdis=dis+x 。
此时如果再对区间 [l.r][l.r][l.r] 做一次 M(ti,x)M(t_i,x)M(ti ,x) 的话,由于进行的是循环右移的操作,那么我们实际的区间需要对区间左右端点减去偏移量 disdisdis ,此时就会出现越界的情况,我们需要对越界的情况进行额外的处理:
* 如果没有越界,差分数组 ddd 会进行以下变化:
d[l−dis]=d[l−dis]+xd[r−dis+1]=d[r−dis+1]−xd[l-dis]=d[l-dis]+x\\ d[r-dis+1]=d[r-dis+1]-x d[l−dis]=d[l−dis]+xd[r−dis+1]=d[r−dis+1]−x
* 如果左边界越界,有边界没越界,差分数组 ddd 会进行以下变化:
d[l−dis+n]=d[l−dis+n]+xd[n+1]=d[n+1]−xd[1]=d[1]+xd[r−dis+1]=d[r−dis+1]−xd[l-dis+n]=d[l-dis+n]+x\\ d[n+1]=d[n+1]-x\\ d[1]=d[1]+x\\ d[r-dis+1]=d[r-dis+1]-x d[l−dis+n]=d[l−dis+n]+xd[n+1]=d[n+1]−xd[1]=d[1]+xd[r−dis+1]=d[r−dis+1]−x
* 如果两个边界都越界了,差分数组 ddd 会进行以下变化:
d[l−dis+n]=d[l−dis+n]+xd[r−dis+n]=d[r−dis+1]−xd[l-dis+n]=d[l-dis+n]+x\\ d[r-dis+n]=d[r-dis+1]-x d[l−dis+n]=d[l−dis+n]+xd[r−dis+n]=d[r−dis+1]−x
在这个过程中,差分数组 ddd 记录的移动量可以保证在 262626 以内,因为 262626 为一个循环,所以在记录的过程中移动量可以直接对 262626 取模。同理,字符串整体的偏移量 disdisdis 可以保证在 nnn 以内。
最后对差分数组 ddd 做一次前缀和就能得到原串每个位置的移动量,对每个位置加上这个移动量即可得到每一位变化后的字母。最后输出的时候还要注意把偏移量 disdisdis 的影响考虑进去。
时间复杂度 O(q+n)O(q+n)O(q+n)
参考代码