0919练习赛

· · 个人记录

两道思维题都很妙好评

circle

感觉我说不清楚。。。直接粘题解算了

感觉这个上面那个证明和下面的转换成LIS都好绝

code

color

显然唯一可行的方法是最左最右边两列都放x种颜色，设左边的颜色集合是S，右边的颜色集合是T，那么中间的m-2列乱放S∩T的颜色。必须满足|S|=|T|。

先考虑左右两边。每一边都要恰放|S|种颜色，显然这个不能直接组合数，但理性分析可以斯特林数。不过考试的时候想了一个dp：设f[i]表示在一个长度为n的序列中i种颜色都要放的方案数。n是定值，题目给的。那么可以转移：f_i=i^n-\sum_{1<=j<i}{(^i_j)f_j}

然后dp后就可以写答案了。枚举S与T的交集大小为a，并集大小为b，考虑到|S|=|T|。

Ans=\sum_{a,b,a<b,(b-a)mod 2==0}(^k_b)(^b_a)(^{b-a}_{(b-a)/2})(f_{a+(b-a)/2})^2a^{n(m-2)}

code

simulate

膜拜题解：

首先不要对轮去考虑，不要将问题变得有阶段性而变得不好做，题目的本意就是不断选择一个元素，将其减 2 并将两旁的元素加 1 ，使得操作之后所有的元素都非负，直到不能继续操作为止。那么可以看出，操作本质上是没有先后顺序的，我们就可以按照从 1 到 n 的顺序去操作。 考虑我们已经操作到第 i 个位置， 1 到 i − 1 都已经变成了 0 或 1 ，但第 i 个位置上的数可能很大。考虑用一个栈去维护 0 的位置，然后仅仅考虑栈顶元素到 i 的这么一段，假设它是长成这样的一个东西： 0 1 1 1 1 1 4 x ，当前的 a[i] 是 4 ，假设 a[i + 1] 是x 。考虑我们对 a[i] 进行操作： 0 1 1 1 1 1 4 x → 0 1 1 1 1 2 2 x+1 → 0 1 1 1 2 0 3 x+1 → 0 1 1 2 0 1 3 x+1 → · · · → 1 0 1 1 1 1 3 x+1 。也就是说，我们操作一次会把 a[i] 减 1 ，同时会把 a[i + 1] 加 1 ，以及会把离 i 最近的一个 0 向后移动一位。然后如果当 0 移动到 i − 1 时，下一步就会把 a[i] 减 2 ，把 a[i + 1] 加 1 ，然后把栈顶的 0 删掉。然后直接模拟这个过程就好了。时间复杂度 O(n) 。

就是所有操作顺序无影响比较难想，后面的要简单一些。其实我现在还不知道为什么操作顺序无影响

模拟那个过程，不要一个一个来。不要当前-1，stack[top]+1,应当一次多走几步，不然时间复杂度是错的。

code