【$T1$】金币

题目大意

国王给忠诚的$Saber$发工资，当连续的$n$天每天收到$n$枚金币时，$Saber$会在之后的$n+1$天每天收到$n+1$枚金币

询问在前$k$天一共怒领多少工资

数据范围

$1\leqslant k\leqslant 10000$

题解

考你会不会编程咯

【$T2$】扫雷游戏

题目大意

给出一个$n\times m$的矩阵，矩阵中每个地雷格位置已知，求每个非地雷格八个邻格上的地雷总数(左上左下右上右下正上正下正左正右)

数据范围

$1\leqslant n\leqslant 100,1\leqslant m\leqslant 100$

题解

考你会不会编程咯

【$T3$】求和

题目大意

给出$n$个格子，编号是$1~n$，每个格子染了一种颜色$Colour_i$，而且写了一个数字$Number_i$

若有两个不同的格子编号$x,z$满足奇偶性相同，且格子颜色相同，则这个二元组对答案的贡献是$(x+z)\times (Number_x+Number_z)$

求最终答案除以10007所得余数

数据范围

$1\leqslant n,m,Number_i\leqslant 100000,1\leqslant Colour_i\leqslant m$

题解

$(x+z)\times (Number_x+Number_z)=x\times Number_x+x\times Number_z+z\times Number_x+z\times Number_z$

则每个格子$x$在每个合法的二元组($x,z$)对答案的贡献是$x\times Number_x+x\times Number_z$，然而时间复杂度是$O(n^2)$，怎么办呢？

可以记录集合$S$，使得在集合$S$中的格子两两可以组成一个合法的二元组，然后用$size$表示集合$S$的格子个数，$sum$表示集合$S$中的$\sum Number_i$，则集合$S$中的格子$x$对答案的独立贡献就可以表示为$$x\times Number_x\times (size-1)+x\times (sum-Number_x)$$

最后$O(n)$扫过去就好啦

【$T4$】推销员

题目大意

给出一个有$n$个数字的数列，数字的编号是$1-n$

选取k个数，假设其中编号的最大值为$m$，那么得到一个叫做疲劳值的东西，等价于$2\times m+k$个数的总和

询问当$1\leqslant k\leqslant n$时的$n$个当前最大的疲劳值

数据范围

$n\leqslant 10^5$

题解

用线段树维护数列最值，每当$k$增加，就取区间最值就好啦