2021牛客OI赛前集训营-提高组题解（第三场）

T1 变换

易知，连续变换两个位置是不明智的选择。所以我们可以设计 dp[i][j][0/1] 的状态，其中第三维表示上一个位置是否被改变过，i 表示当前位置，j 表示之前已经变换过 j 次（要保证 j 时刻小于等于 k）。如果当前位置的 a[i] 已经是山谷点，则无需变换，否则可以考虑变换的转移方程，在 dp 过程中一直记录最大值即可。

https://ac.nowcoder.com/acm/contest/view-submission?submissionId=48938305

T2 交替

打表找规律题。易知最终的答案是由原来的数组乘以每一位对应的系数求和得到的，所以我们打表找规律，来看看每一位的系数到底是多少。打一个 10 行左右的表，就可以发现系数与杨辉三角有关，再进行细节的维护即可算出（具体规律见 std）

https://ac.nowcoder.com/acm/contest/view-submission?submissionId=48938291

T3 打拳

https://ac.nowcoder.com/acm/contest/view-submission?submissionId=48938271

20pts

暴力枚举所有情况即可。

50pts

对于所有 k=1 的情况，考虑本质上这个过程就是问你有多少种不同的二叉树，并且对于 1 号节点到根的路径，每个点都是子树内的最大值，且这个值得是被收买的人之一。

那么 dp[i∈[0,m]][j∈[0,2^n-1]] 表示已经考虑过前 i 小的被收买的人，当前 j 这个状态中是 1 的位置已经被某个收买的人占有的方案数。

那么直接枚举这个人是否占了某个位置，然后用组合数转移即可（具体可看 std）。

注意到最后还得给答案乘上 2^n，因为这 n 个子树之间的顺序并没有确定。

100pts

考虑到还得在这个过程中维护 LIS，那么首先考虑 LIS 的一种维护方法：

我们可以从小到大依次来算每个数字的 LIS，这个数字的 LIS，等于在他位置之前所有数字 LIS 的最大值 +1。

例如 4 个数字 {3 1 2 4}

我们用如下顺序算出 LIS：

{0 1 0 0}

{0 1 2 0}

{1 1 2 0}

{1 1 2 3}

那么我们可以暴力出所有 LIS 过程中可能的序列，发现这个数量其实并不太大，当 n=9 的时候也才不到 120000，那么就用这个当之前那个状压的状态，去跑 dp 即可。

时间复杂度 n\times 120000log_2120000 \times n。

实际上有一个更强的结论，当 k 比较接近 n 的时候，有用状态特别少，那么实际上可以在搜索的时候只保留那些可能让 LIS 大于等于 k 的状态，于是可以把 n 和 k 出的很接近，然后放大 n。

T4 扑克

需要暴力出所有的五元组，然后把这些五元组排序，以及存一下每个三元组，可能构成哪些rank的五元组。

写完以后对于每组询问，就直接在对应的三元组里面二分就好了。

https://ac.nowcoder.com/acm/contest/view-submission?submissionId=48938279