【题解】牛客小白月赛3

T1 音标

考虑模拟。

每次读取一行字符串,从头到尾枚举,判断这个字母应该变为哪一个字母,然后直接替换并输出即可。

这样,我们就可以通过这道题目。

T2 躲藏

设原字符串数组为ss,模数20001204200101222000120420010122ModMod,将字符串中所有的大写字母预先变为小写 字母。

考虑动态规划。

f[i][j],(j=1,2,3,4)f[i][j],(j=1,2,3,4)表示前ii个字符中,匹配了字符串"ewbe"的前多少位,那么有转移方程:

f[i][1]=(f[i1][1]+(s[i]==c))%Modf[i][1]=\left(f[i-1][1]+\left(s[i]==^{\prime} c^{\prime}\right)\right) \% \operatorname{Mod}

f[i][2]=(f[i1][2]+(s[i]==w)f[i1][1])%Modf[i][2]=\left(f[i-1][2]+\left(s[i]==^{\prime} w^{\prime}\right) * f[i-1][1]\right) \% \operatorname{Mod}

f[i][3]=(f[i1][3]+(s[i]==b)f[i1][2])%Modf[i][3]=\left(f[i-1][3]+\left(s[i]==^{\prime} b^{\prime}\right) * f[i-1][2]\right) \% \operatorname{Mod}

f[i][4]=(f[i1][4]+(s[i]==c)f[i1][3])%Modf[i][4]=\left(f[i-1][4]+\left(s[i]==^{\prime} c^{\prime}\right) * f[i-1][3]\right) \% \operatorname{Mod}

理论上这样还是不能通过本题,因为数组的开小大概需要35MB左右,超过内存限制。我们来考虑优化这个状态设计。

容易发现,每一个字符的状态都只从它前一个字符的状态转移过来,显然我们可以考虑使用滚动数组来优化空间开销,这样就可以通过本题。

我们考虑去掉第一维的状态, 只保留第二维的状态。那么转移方程就变为:

f[1]=(f[1]+(s[i]==c))%Modf[1]=\left(f[1]+\left(s[i]==^{\prime} c^{\prime}\right)\right) \% \mathrm{Mod}

f[2]=(f[2]+(s[i]==w)f[1])%Modf[2]=\left(f[2]+\left(s[i]==^{\prime} w^{\prime}\right) * f[1]\right) \% \operatorname{Mod}

f[3]=(f[3]+(s[i]===b)f[2])%Modf[3]=\left(f[3]+\left(s[i]===^{\prime} b^{\prime}\right) * f[2]\right) \% \operatorname{Mod}

同一个位置有且仅有一个字符,不难发现转移方程间是不会相互影响的。因此,省去第一维的状态是正确的。

这样,我们就可以通过这道题目。

T3 博弈

数据组数较多,我们优先考虑预处理数组,然后直接回答询问。 考虑贪心。

k=1k=1时,游戏会一直继续下去,谁也无法取胜,故平局。

2k2≤k的每一个kk,枚举每一个数字,考虑它需要做几次操作,才能将这个数字变成全部为零的数字。

可以看出,最后的答案只与总操作数的奇偶性有关,而数字的总操作数是一定的,故这是一个假的博弈论。

对操作数求一个前缀和,判断其奇偶性,即可。

这样,我们就可以通过这道题目。

T4 妹纸

比较容易可以看出,假设我们要计算kk取模后的值,我们只需要看kk modmod (r1)(r- 1)是否在区间[l,r)[l,r)中,如果在,那么结果为0,否则结果为kk modmod (r1)(r- 1)

这样,整个序列就会变成:

1,2,,l1,0,0,,0,1,2,1,2, \ldots \ldots, l-1,0,0, \ldots \ldots, 0,1,2, \ldots \ldots

其中,l1l-1到下一个11之间共有rl+1r-l+100

聪明的读者可以看出,询问区间必定是由最多三个等差数列求和而得。

不妨称1,2...,l11,2...,l-1为一个连续段

我们可以将区间(a,b](a,b]分成三个部分,第一段为开始部分到第一个连续段结束(如果开始位置不在连续段内,则第一段记做00),第三段为最后一个连续段开始到结束部分(如果结束位置不在连续段内,则第三段记做00),中间段即为多个连续段的和。

显然,这三段都可以使用一些等差数列求和的公式来计算,细节较多,可以参考样例代码。

这样,我们就可以通过这道题目。

T5 幻方

考察选手空间力和想象力。

由于是从内部观察激光发射器的位置,比较难以想象。

我们假设从外部观察。设正面、左面与顶面的交的方块为参考点,记做(1,1,1)(1,1,1),沿着正面的项边为xx轴,项面的左侧边为yy轴,正面的左侧边为zz轴。

这样,从内部看这六个面,分别是:

●正面: xx轴从大到小,zz轴从小到大。

●背面: xx轴从小到大,zz轴从小到大。

●左侧面: yy轴从小到大,zz轴从小到大。

右侧面: yy轴从大到小,zz轴从小到大。

●项面: xx轴从小到大,yy轴从小到大。

●底面: xx轴从小到大,yy轴从大到小。

对于每个面的激光发射器,将一个二维坐标标记,然后枚举空间中每一个坐标, 判断是否三组坐标都被标记(即(x,y)(x,y)(x,z)(x,z)(y,z)(y,z)), 如果都被标记,那么答案加11

这样,我们就可以通过这道题目。

T6 异或与T7重复

考虑动态规划。

f[i][0/1]f[i][0/1]表示第ii个点不选择(0)(0) 或选择(1)(1)时的最大独立集的大小是多少。 那么我们可以设计出转移方程:

f[i][0]=max(f[son[i]][0],f[son[i]][1])f[i][0]=\sum \max (f[\operatorname{son}[i]][0], f[\operatorname{son}[i]][1])

f[i][1]=f[son][0]f[i][1]=\sum f[\operatorname{son}][0]

其中,son[i]son[i] 表示ii的子节点。

先来考虑第二个式子。如果当前节点被选择了,那么它的所有子节点都不能被选择,这个比较容易理解。

再考虑第一个式子。如果当前节点没有被选择,那么它的所有子节点可以被选择,也可以不被选择。

读者可能会有一个疑问:为什么当前节点没有被选择,它的子节点不被选择时,最大独立集的大小反而会增大呢?

我们不妨考虑一条长度为偶数的链,如图所示。

alt

我们可以选择0240、2、4三个点,也可以选择0250、2、5三个点。倘若节点44后跟了许多节点,显然我们应该放弃节点44的贡献,而将44的所有子节点贡献计算到答案中。

对树做完树形DP之后,那么答案即为f[s][1]f[s][1]

这样,我们就可以通过这道题目。

T7 旅游

考虑动态规划。

f[i][0/1]f[i][0/1]表示第ii个点不选择(0)(0) 或选择(1)(1)时的最大独立集的大小是多少。 那么我们可以设计出转移方程:

f[i][0]=max(f[son[i]][0],f[son[i]][1])f[i][0]=\sum \max (f[\operatorname{son}[i]][0], f[\operatorname{son}[i]][1])

f[i][1]=f[son][0]f[i][1]=\sum f[\operatorname{son}][0]

其中,son[i]son[i] 表示ii的子节点。

先来考虑第二个式子。如果当前节点被选择了,那么它的所有子节点都不能被选择,这个比较容易理解。

再考虑第一个式子。如果当前节点没有被选择,那么它的所有子节点可以被选择,也可以不被选择。

读者可能会有一个疑问:为什么当前节点没有被选择,它的子节点不被选择时,最大独立集的大小反而会增大呢?

我们不妨考虑一条长度为偶数的链,如图所示。

alt

我们可以选择0240、2、4三个点,也可以选择0250、2、5三个点。倘若节点44后跟了许多节点,显然我们应该放弃节点44的贡献,而将44的所有子节点贡献计算到答案中。

对树做完树形DP之后,那么答案即为f[s][1]f[s][1]

这样,我们就可以通过这道题目。

T8 纪年

不难发现,天干与地支的组合每60年为一个循环,我们可以直接将两个年份之间的差对60取模后,模拟即可。

亦可寻找年份与天干地支的关系,通过找规律寻找到答案。

这样,我们就可以通过这道题目。

T9 排名

通过公式,对每个人计算得分,然后排序即可。

可能需要注意排序时的常数问题。

这样,我们就可以通过这道题目。

T10 零点

对开头和结尾单独处理它们可能的整数零点,然后对每一"段函数计算零点是否为整数。

我们有斜率计算公式k=y2y1x2x1k=\frac{y_{2}-y_{1}}{x_{2}-x_{1}},那么就有y1=y2y1x2x1x1+by_{1}=\frac{y_{2}-y_{1}}{x_{2}-x_{1}} x_{1}+b,所以可以得到b=y1y2y1x2x1x1b=y_{1}-\frac{y_{2}-y_{1}}{x_{2}-x_{1}} x_{1}。所以即有方程:

y=(y2y1x2x1)x+(y1y2y1x2x1x1)y=\left(\frac{y_{2}-y_{1}}{x_{2}-x_{1}}\right) x+\left(y_{1}-\frac{y_{2}-y_{1}}{x_{2}-x_{1}} x_{1}\right)

y=0y=0, 则 x=x1y1x2x1y2y1x=x_{1}-y_{1} \frac{x_{2}-x_{1}}{y_{2}-y_{1}}

类似的,可以推出左右两条射线的方程,这里留给读者独立思考。

注意,可能有精度问题,可能会爆int,可能会有无数个整数零点的情况,需要选手多加判断。

这样,我们就可以通过这道题目。

全部评论

相关推荐

评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务