How to AK zhqwq-CSPS模拟赛

· · 个人记录

题外话

总结成绩：寄了。

T1-sbt

直接按照题意模拟，通过观察可以发现，向左走，变小，向右走，变大。
其实就是一个 BST。

T2-gift

实际不需要知道每个颜色出现多少次，只需要知道有多少个元素出现奇数次，有多少个出现偶数次。
设 f_{i,j} 为前 i 个有 j 个颜色出现奇数次的方案数。
转移的时候，想一下下一个颜色是什么。如果下一个颜色在这 j 个现在出现奇数次的颜色里面出现过，那么下一个状态出现奇数次的颜色数相较于现在减一。 否则下一个出现奇数次的颜色书相较于现在加一。

转移：f[i+1][j-1]+=f[i][j]*j，f[i+1][j+1]+=f[i][j]*(m-j)

代码在写。