因为篇幅较长，因此题解分为两个帖子发放。
突然发现上面三片其实也没那么长(bushi
题解正文
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
T1 雪块高度
解题思路
一共有999999999个数字，从低到高分别为1,(1+2),(1+2+3),(1+2+3+4),...,(1+2+3...+999)1,(1+2),(1+2+3),(1+2+3+4),...,(1+2+3...+999)1,(1+2),(1+2+3),(1+2+3+4),...,(1+2+3...+999)。给定两个数字aaa和bbb，为相邻两个数减去xxx后的结果，求解xxx。
由于给出的是相邻两个数，较小的数字xxx为(1+2+3+...+n−1)(1 + 2 + 3 +... + n-1)(1+2+3+...+n−1),较大的数字yyy为(1+2+3+...+n−1+n)(1 + 2 + 3 +... + n-1 + n)(1+2+3+...+n−1+n)，他们的差值为nnn。
我们可以得出，未被覆盖的部分的高度为1+2+3+...+n−answer1+2+3+...+n-answer1+2+3+...+n−answer，故答案为(y−x)×(y−x+1)/2−y(y - x) \times (y - x + 1) / 2 - y(y−x)×(y−x+1)/2−y。
参考代码
T2 采矿场
解题思路
经过观察，可以发现NNN的取值为10510^5105，同时666与999的幂次结果会在某个阶段重合，因此我们可以先行枚举666幂次的最大值，然后枚举999幂次的最大值，剩余部分用1补足。
因为最后的答案一定为6x6^x6x + 9y9 ^ y9y + z×1z \times 1z×1，因此枚举其组合方式是可行的。
参考代码
T3 正除数
解题思路
一个整数xxx可以通过质因数分解得到x=p1a1p2a2⋯pkakx=p_1^{a_1}p_2^{a_2}\cdots p_k^{a_k}x=p1a1 p2a2 ⋯pkak ，其中pip_ipi 是质数，aia_iai 是pip_ipi 在xxx中出现的次数。对于所有的质因数pip_ipi ，求解N!N!N!对于所有的质因数能够整除的次数即可。
参考代码
T4 YUILICE的偶数回文串
题解思路
对于60%60\%60%的数据，可以设立f[i]f[i]f[i]表示为了使得区间[1,n][1,n][1,n]是一个美丽字符串所需最小花费。f[i]f[i]f[i]可以由前面的f[j]f[j]f[j]转移而来：f[i]=min(f[j−1]+ask(j,i))f[i]=min(f[j-1]+ask(j,i))f[i]=min(f[j−1]+ask(j,i))，其中jjj是最后一个偶回文串的左端点，ask(j,i)ask(j,i)ask(j,i)是为了使得区间[j,i][j,i][j,i]变成偶回文串所需最小花费。
对于100%100\%100%的数据，可以在60%60\%60%数据的基础上将ask(j,i)ask(j,i)ask(j,i)用动态规划预处理一下。设g[i][j]g[i][j]g[i][j]是ask(i,j)ask(i,j)ask(i,j)，则g[i][i+1]g[i][i+1]g[i][i+1]可以直接判断t[i]t[i]t[i]和t[i+1]t[i+1]t[i+1]得到，其他g[i][j]g[i][j]g[i][j]需要判断t[i]t[i]t[i]和t[j]t[j]t[j]得到。
参考代码
T5 先到为敬
解题思路
对于5%5\%5%的数据，此时从i走到j所需花费为∣xi−xj∣=∣yi−yj∣|x_i-x_j|=|y_i-y_j|∣xi −xj ∣=∣yi −yj ∣，走额外的点不会使得答案更小，因此输出∣xn−x1∣|x_n-x_1|∣xn −x1 ∣即可。复杂度O(n)O(n)O(n)
对于30%30\%30%的数据，可以暴力连边跑最短路。复杂度O(n2)O(n^2)O(n2)。
对于另外35%35\%35%的数据，此时从1到2到3到4...到n是最优秀的，循环一遍计算花费即可。
对于100%100\%100%的数据，考虑优化建图方式。
对于三个点 i,j,ki, j, ki,j,k, 若 xi<xj<xkx_{i}<x_{j}<x_{k}xi <xj <xk ,
则 i→k=xk−xi=(xk−xj)+(xj−xi)=i→j→ki \rightarrow k=x_{k}-x_{i}=\left(x_{k}-x_{j}\right)+\left(x_{j}-x_{i}\right)=i \rightarrow j \rightarrow ki→k=xk −xi =(xk −xj )+(xj −xi )=i→j→k, 边 i→ki \rightarrow ki→k 是根本不用连的。
所以将所有点的 xxx 坐标排序, 然后从小到大连边即可。
对于 yyy 坐标同理。
然后对于限制条件 min∣ax−bx∣,∣ay−by∣\min \left|a_{x}-b_{x}\right|,\left|a_{y}-b_{y}\right|min∣ax −bx ∣,∣ay −by ∣, 只需要跑最短路即可, 因为最短路不可能把你导向一条长的路径。
T6 又是字符串
题解思路
枚举所有的新串，然后计算原有的串变成新串所需的最小移动次数即可。如果最小移动次数≤k\leq k≤k时，ansansans累加即可。
串sss移动成为串ttt所需最小花费，我们可以找出ttt串中第xxx次出现的字符c1c1c1与其在sss中第xxx次出现的相同的字符c1c1c1的位置，计入aaa数组，答案即为aaa数组的逆序对数量。可以通过50%的数据
注意到一个性质：当k>=n∗(n−1)2k>={n*(n-1)\over 2}k>=2n∗(n−1) 时，可以从原串更改为任意新串，所以kkk太大没有什么用。
为了通过100%100\%100%的数据，可以考虑动态规划。
我们f[i][j][k][t]f[i][j][k][t]f[i][j][k][t] 表示当前新串已经使用了 i+j+ki+j+ki+j+k 个位置，使用了 iii 个 K，jK ， jK，j 个 EEE ， kkk 个 YYY ，且一共换了 ttt 次，的方案数。枚举下一个字符是什么，所需花费可以O(1)O(1)O(1)计算，因此转移的复杂度也为O(1)O(1)O(1)。
