【题解】牛客小白月赛3

T1 音标

考虑模拟。

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

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

T2 躲藏

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

考虑动态规划。

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

$f[i][1]=(f[i-1][1]+(s[i]={=}^{\mathrm{\prime }}{c}^{\mathrm{\prime }}))\mathrm{\%}\mathrm{Mod}f[i][1]=\backslash left(f[i-1][1]+\backslash left(s[i]==^\{\backslash prime\}\; c^\{\backslash prime\}\backslash right)\backslash right)\; \backslash \%\; \backslash operatorname\{Mod\}$

$f[i][2]=(f[i-1][2]+(s[i]={=}^{\mathrm{\prime }}{w}^{\mathrm{\prime }})\ast f[i-1][1])\mathrm{\%}\mathrm{Mod}f[i][2]=\backslash left(f[i-1][2]+\backslash left(s[i]==^\{\backslash prime\}\; w^\{\backslash prime\}\backslash right)\; *\; f[i-1][1]\backslash right)\; \backslash \%\; \backslash operatorname\{Mod\}$

$f[i][3]=(f[i-1][3]+(s[i]={=}^{\mathrm{\prime }}{b}^{\mathrm{\prime }})\ast f[i-1][2])\mathrm{\%}\mathrm{Mod}f[i][3]=\backslash left(f[i-1][3]+\backslash left(s[i]==^\{\backslash prime\}\; b^\{\backslash prime\}\backslash right)\; *\; f[i-1][2]\backslash right)\; \backslash \%\; \backslash operatorname\{Mod\}$

$f[i][4]=(f[i-1][4]+(s[i]={=}^{\mathrm{\prime }}{c}^{\mathrm{\prime }})\ast f[i-1][3])\mathrm{\%}\mathrm{Mod}f[i][4]=\backslash left(f[i-1][4]+\backslash left(s[i]==^\{\backslash prime\}\; c^\{\backslash prime\}\backslash right)\; *\; f[i-1][3]\backslash right)\; \backslash \%\; \backslash operatorname\{Mod\}$

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

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

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

$f[1]=(f[1]+(s[i]={=}^{\mathrm{\prime }}{c}^{\mathrm{\prime }}))\mathrm{\%}\mathrm{M}\mathrm{o}\mathrm{d}f[1]=\backslash left(f[1]+\backslash left(s[i]==^\{\backslash prime\}\; c^\{\backslash prime\}\backslash right)\backslash right)\; \backslash \%\; \backslash mathrm\{Mod\}$

$f[2]=(f[2]+(s[i]={=}^{\mathrm{\prime }}{w}^{\mathrm{\prime }})\ast f[1])\mathrm{\%}\mathrm{Mod}f[2]=\backslash left(f[2]+\backslash left(s[i]==^\{\backslash prime\}\; w^\{\backslash prime\}\backslash right)\; *\; f[1]\backslash right)\; \backslash \%\; \backslash operatorname\{Mod\}$

$f[3]=(f[3]+(s[i]=={=}^{\mathrm{\prime }}{b}^{\mathrm{\prime }})\ast f[2])\mathrm{\%}\mathrm{Mod}f[3]=\backslash left(f[3]+\backslash left(s[i]===^\{\backslash prime\}\; b^\{\backslash prime\}\backslash right)\; *\; f[2]\backslash right)\; \backslash \%\; \backslash operatorname\{Mod\}$

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

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

T3 博弈

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

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

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

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

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

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

T4 妹纸

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

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

$1,2,\dots \dots ,l-1,0,0,\dots \dots ,0,1,2,\dots \dots 1,2,\; \backslash ldots\; \backslash ldots,\; l-1,0,0,\; \backslash ldots\; \backslash ldots,\; 0,1,2,\; \backslash ldots\; \backslash ldots$

其中，$l-1l-1$到下一个$11$之间共有$r-l+1r-l+1$个$00$。

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

不妨称$1,\mathrm{2...},l-11,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\mathrm{/}1]f[i][0/1]$表示第$ii$个点不选择$(0)(0)$ 或选择$(1)(1)$时的最大独立集的大小是多少。 那么我们可以设计出转移方程:

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

$f[i][1]=\sum f[\mathrm{son}][0]f[i][1]=\backslash sum\; f[\backslash operatorname\{son\}][0]$

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

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

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

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

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

我们可以选择$0\mathrm{、}2\mathrm{、}40、2、4$三个点，也可以选择$0\mathrm{、}2\mathrm{、}50、2、5$三个点。倘若节点$44$后跟了许多节点，显然我们应该放弃节点$44$的贡献，而将$44$的所有子节点贡献计算到答案中。

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

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

T7 旅游

考虑动态规划。

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

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

$f[i][1]=\sum f[\mathrm{son}][0]f[i][1]=\backslash sum\; f[\backslash operatorname\{son\}][0]$

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

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

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

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

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

我们可以选择$0\mathrm{、}2\mathrm{、}40、2、4$三个点，也可以选择$0\mathrm{、}2\mathrm{、}50、2、5$三个点。倘若节点$44$后跟了许多节点，显然我们应该放弃节点$44$的贡献，而将$44$的所有子节点贡献计算到答案中。

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

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

T8 纪年

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

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

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

T9 排名

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

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

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

T10 零点

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

我们有斜率计算公式$k=\frac{y_2-y_1}{x_2-x_1}k=\backslash frac\{y\_\{2\}-y\_\{1\}\}\{x\_\{2\}-x\_\{1\}\}$，那么就有$y_1=\frac{y_2-y_1}{x_2-x_1}{x}_1+by\_\{1\}=\backslash frac\{y\_\{2\}-y\_\{1\}\}\{x\_\{2\}-x\_\{1\}\}\; x\_\{1\}+b$，所以可以得到$b=y_1-\frac{y_2-y_1}{x_2-x_1}{x}_{1}b=y\_\{1\}-\backslash frac\{y\_\{2\}-y\_\{1\}\}\{x\_\{2\}-x\_\{1\}\}\; x\_\{1\}$。所以即有方程：

$y=\left(\frac{y_2-y_1}{x_2-x_1}\right)x+(y_1-\frac{y_2-y_1}{x_2-x_1}{x}_1)y=\backslash left(\backslash frac\{y\_\{2\}-y\_\{1\}\}\{x\_\{2\}-x\_\{1\}\}\backslash right)\; x+\backslash left(y\_\{1\}-\backslash frac\{y\_\{2\}-y\_\{1\}\}\{x\_\{2\}-x\_\{1\}\}\; x\_\{1\}\backslash right)$

令 $y=0y=0$, 则 $x=x_1-y_1\frac{x_2-x_1}{y_2-y_1}x=x\_\{1\}-y\_\{1\}\; \backslash frac\{x\_\{2\}-x\_\{1\}\}\{y\_\{2\}-y\_\{1\}\}$ 。

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

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

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