20231018NOIP训练赛
时间安排
7:50-8:10 写T1
9:10-10:30写T2
10:30-11:50写T4
总结
没看T3去做了T4，考完试发现T3比T4更可做。
题解
T1
贪心题，排序之后贪心即可
T2
对a做前缀和，把题目的式子化成
\[\sum_{l=1}^{n} \sum_{r=l}^n \sum_{i=l}^{r} b[i]*(sum[r]-sum[l]) \]对于每一个系数的即为
\[f_i=sum[i-1]*(n-i+1)+(sum[n]-sum[i])*(i) \]然后对f做前缀和，询问时加上系数乘k
T3
把期望转化为平均数
\[\dfrac{\sum_{i=1}^{m} \sum_{j=1}^{m} d(i,j) \times (m-1)!}{m!} \]\[=\dfrac{\sum_{i=1}^{m} \sum_{j=1}^{m} d(i,j)}{m} \]于是问题转化为求出\(\sum_{i=1}^{m} \sum_{j=i+1}^{m} d(i,j)\)，可以对于每一个边计算其贡献
T4
考虑根号分治
当x小于sqrt(n)时，设\(isum_{i,j}\)表示表示模i时余数小于等于j时修改的前缀和
当x大于sqrt(n)时，先把原序列分成sqrt(n)个块，然后对序列进行差分，然后用树状数组进行维护
标签：10,20231018NOIP,sum,T3,sqrt,训练赛,T4 From： https://www.cnblogs.com/RYANGSJ/p/17775581.html