A

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

B

考虑dpdp预处理出2×1052\times 10^5内的所有答案然后O(1)O(1)查询

设：

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

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

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

f0[i]f_{0}[i]表示长度为ii且不含子序列'N'的字符串个数

则有

fNBT[i]=fNBT[i−1]×26+fNB[i−1]×1f_{NBT}[i]=f_{NBT}[i-1]\times 26+f_{NB}[i-1]\times 1

fNB[i]=fNB[i−1]×25+fN[i−1]×1f_{NB}[i]=f_{NB}[i-1]\times 25+f_{N}[i-1]\times 1

fN[i]=fN[i−1]×25+f0[i−1]×1f_{N}[i]=f_{N}[i-1]\times 25+f_{0}[i-1]\times 1

f0[i]=f0[i−1]×25f_{0}[i]=f_{0}[i-1]\times 25

以计算fNB[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⁡\max即可

D

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

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

E

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

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

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

∑i=1n(ai−aˉ)2=∑i=1n(ai2−2aiaˉ+aˉ2)=∑i=1nai2−2aˉ∑i=1nai+∑i=1naˉ2=∑i=1nai2−2aˉ∑i=1nai+naˉ2 \begin{array}{lcl} \sum\limits_{i=1}^{n}(a_i-\bar{a})^2 \\ =\sum\limits_{i=1}^{n}(a_i^2-2a_i\bar{a}+\bar{a}^2) \\ =\sum\limits_{i=1}^{n}a_i^2-2\bar{a}\sum\limits_{i=1}^{n}a_i + \sum\limits_{i=1}^{n}\bar{a}^2 \\ =\sum\limits_{i=1}^{n}a_i^2-2\bar{a}\sum\limits_{i=1}^{n}a_i + n\bar{a}^2 \end{array}

因此分别维护aia_i的和，ai2a_i^2的和，以及aia_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%(r+g)t\%(r+g)表示在一个红绿灯周期内所处的时刻

如果t%(r+g)+l≤gt\%(r+g)+l\leq g则可以在绿灯结束前直接通过

否则必须等到下一次绿灯

H

当(x1,y1)=(x2,y2)(x_1,y_1)=(x_2,y_2)时，显然答案为00

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

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

I

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

f[i]={0,i=ninf[i−1]+n−inf[i+1]+1,1≤i≤n−1f[1]+1,i=0 f[i]= \left\{ \begin{array}{lcl} 0 &,& i=n\\ \frac{i}{n}f[i-1]+\frac{n-i}{n}f[i+1]+1 &,& 1\leq i\leq n-1\\ f[1]+1 &,& i=0 \end{array} \right.

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

将f[n]=0f[n]=0代入f[n−1]f[n-1]的转移方程中，得到f[n−1]=n−1nf[n−2]+1f[n-1]=\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≤i≤n−11\leq i\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]\text{~}f[n-1]的值即可

J

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

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

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

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