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