第十九届浙大宁波理工学院程序设计大赛题解

A

签到题，输出"Welcome to 19th NBT Programming Contest"即可

B

考虑$dpdp$预处理出$2\times 10^{5}2\backslash times\; 10^5$内的所有答案然后$O(1)O(1)$查询

设：

$f_{NBT}[i]f\_\{NBT\}[i]$表示长度为$ii$且含有子序列'NBT'的字符串个数

$f_{NB}[i]f\_\{NB\}[i]$表示长度为$ii$且含有子序列'NB'，但不含子序列'NBT'的字符串个数

$f_N[i]f\_\{N\}[i]$表示长度为$ii$且含有子序列'N'，但不含子序列'NB'的字符串个数

$f_0[i]f\_\{0\}[i]$表示长度为$ii$且不含子序列'N'的字符串个数

则有

$f_{NBT}[i]=f_{NBT}[i-1]\times 26+f_{NB}[i-1]\times 1f\_\{NBT\}[i]=f\_\{NBT\}[i-1]\backslash times\; 26+f\_\{NB\}[i-1]\backslash times\; 1$

$f_{NB}[i]=f_{NB}[i-1]\times 25+f_N[i-1]\times 1f\_\{NB\}[i]=f\_\{NB\}[i-1]\backslash times\; 25+f\_\{N\}[i-1]\backslash times\; 1$

$f_N[i]=f_N[i-1]\times 25+f_0[i-1]\times 1f\_\{N\}[i]=f\_\{N\}[i-1]\backslash times\; 25+f\_\{0\}[i-1]\backslash times\; 1$

$f_0[i]=f_0[i-1]\times 25f\_\{0\}[i]=f\_\{0\}[i-1]\backslash times\; 25$

以计算$f_{NB}[i]f\_\{NB\}[i]$为例，如果前$i-1i-1$位已经含有子序列'NB'了，由于不能含有子序列'NBT'，则第$ii$位只能选取除'T'以外的$2525$个字母；如果前$i-1i-1$位只含有子序列'N'，而不含有子序列'NB'，则第$ii$位只能是'B'

注意初始化然后递推即可

C

方法一：可以发现加法和乘法在这里的单调性是相同的，除法的单调性是相反的，乘法和除法的贡献大于加法。那么我们只需要让$ff$为最小值，$ee$为次小值，$cc$和$dd$为最大值和次大值，$aa$和$bb$为剩下的两个数即可。$O(1)O(1)$即可计算出答案

方法二：对六个数枚举全排列，对每种情况计算答案并取$\max \backslash max$即可

D

按从前往后、从后往前的顺序分别遍历$nn$道题，遇到hard的题或者用时超过五小时就结束

两种情况得到的结果取$\max \backslash max$即为答案

E

对于平均数，只需要维护当前所有数的和，除以当前的个数即是平均值

对于众数，只需要维护每个数当前出现的次数，如果当前输入的数的出现次数大于上一轮的众数，则更新众数，出现次数相同则取较大值作为众数。

对于方差，考虑其分子部分：

因此分别维护$a_{i}a\_i$的和，$a_i^{2}a\_i^2$的和，以及$a_{i}a\_i$的平均数即可

对于中位数，可以采用对顶堆，即一个大顶堆和小顶堆

让大顶堆只存放小于等于中位数的值，小顶堆只存放大于中位数的值，则大顶堆的$toptop$永远都是中位数的值

因此可知大顶堆的$sizesize$总是等于小顶堆的$sizesize$或比小顶堆的$sizesize$大$11$，对于输入进来的数判断放到哪个堆里即可

F

由于求本质不同的固定后缀的子串，容易想到后缀自动机，先用$ss$串构建自动机。对于一个节点，该节点所能表示的字符串的数量为$len[i]-len[link[i]]len[i]-len[link[i]]$，用输入串$tt$去匹配，如果串$tt$匹配失败，说明没有以$tt$结尾的子串，答案为$00$；假设匹配结束后$lastlast$停留在节点$ii$，那么以$ii$为根在后缀链接树上的子树之和减去节点$ii$所不能表示的子串数量即为答案。

G

记录当前时间为$tt$，对于要走的路口，$t\mathrm{\%}(r+g)t\backslash \%(r+g)$表示在一个红绿灯周期内所处的时刻

如果$t\mathrm{\%}(r+g)+l\le gt\backslash \%(r+g)+l\backslash leq\; g$则可以在绿灯结束前直接通过

否则必须等到下一次绿灯

H

当$(x_1,y_1)=(x_2,y_2)(x\_1,y\_1)=(x\_2,y\_2)$时，显然答案为$00$

当小汤圆和家的直线距离为整数时，只需要朝着家的方向跳一次就可以到家

当直线距离不是整数时，可以通过曼哈顿距离跳两次回家

I

设$f[i]f[i]$表示从当前有$ii$个灯泡亮起，到所有灯泡都亮起的期望次数，则有：

$\frac{i}{n}\backslash frac\{i\}\{n\}$表示熄灭一个灯泡的概率，$\frac{n-i}{n}\backslash frac\{n-i\}\{n\}$表示点亮一个灯泡的概率

将$f[n]=0f[n]=0$代入$f[n-1]f[n-1]$的转移方程中，得到$f[n-1]=\frac{n-1}{n}f[n-2]+1f[n-1]=\backslash frac\{n-1\}\{n\}f[n-2]+1$

再将$f[n-1]f[n-1]$代入$f[n-2]f[n-2]$的转移方程中，可以得到$f[n-2]f[n-2]$只关于$f[n-3]f[n-3]$的方程

所以对于$1\le i\le n-11\backslash leq\; i\backslash leq\; n-1$，都有$f[i]=k[i]f[i-1]+b[i]f[i]=k[i]\; f[i-1]+b[i]$，其中$k[i],b[i]k[i],b[i]$都是常数

因此可以从后往前维护$k[i],b[i]k[i],b[i]$，再把$f[1]=k[1]f[0]+b[1]f[1]=k[1]f[0]+b[1]$代入$f[0]=f[1]+1f[0]=f[1]+1$解出$f[0]f[0]$的值，最后从$f[0]f[0]$递推出$f[1]f[n-1]f[1]\backslash text\{~\}f[n-1]$的值即可

J

因为输入的数组是一个排列，所以一段区间的$\text{MEX}\backslash text\{MEX\}$等于此区间外数字的最小值

交换位置可以看成是单点修改两个位置上的值

用线段树维护区间和、区间最小值即可

注意特判区间大小为$nn$的情况