2024.9.25 模拟赛

题目：2024.9.25 题目

变幻

对于数组 $a$，若有点 $i$ $(1<i<n)$ 满足 $a_{i-1}>a_i$ 且 $a_i<a_{i+1}$，称点 $i$ 为山谷。至多可以修改 $k$ 次数组，使指定位置上的数变得比原来小。求最大山谷点之和。

---

首先，我们发现两个山谷不可能挨在一起，因此两个手动创建的山谷必须要隔至少一座山。由于 $1\le k\le n\le 2000$，不难想到 dp。首先选择了前多少个需要保留，已经修改了多少次也需要保留，但是跟之前修改的方案没有太大关系，只需要记录最后一个是否紧挨着就行，因此可以设计出状态 $d{p}_{i,j,0/1}$ 表示为已经选择了前 $i$ 座山，修改了 $j$ 次，最后一座山是否在 $i$ 那里。

接下来考虑状态的转移。若第 $i$ 座山已经形成了山谷，我们就可以直接使用，因此 $d{p}_{i,j,1}=d{p}_{i-1,j,0}+a_i$；如果第 $i$ 座山没有形成山谷，我们就可以手动创建一个山谷，高度为 $\min (a_{i-1},a_{i+1})-1$，也就是 $d{p}_{i,j,1}=d{p}_{i-1,j-1,0}+\min (a_{i-1},a_{i+1})-1$。同时，$i$ 也可以不要山谷，即 $d{p}_{i,j,0}=\max (d{p}_{i-1,j,0},d{p}_{i-1,j,1})$。

最后 $dp$ 数组的所有值当中的最大值就是答案了。

交替

有一长度为 $n$ 的数组 $a$，会变换 $n-1$ 次，每一次变换逻辑如下：

• 若 $n$ 为偶数，则 $a_i=a_i+a_{i+1}$ $(1\le i<n)$，数组长度 $-1$；
• 若 $n$ 为奇数，则 $a_i=a_i-a_{i+1}$ $(1\le i<n)$，数组长度 $-1$。

最后 $a$ 只剩一个数字，输出该数字对 $10^9+7$ 取模的结果。

---

首先，我们来找一下 $n=1\sim 7$ 的规律。不难发现，当 $n$ 为奇数的时候，偶数位置上面的系数为 $0$，奇数位置上面的系数一正一负；但是 $n$ 为偶数似乎没有什么规律。不过我们可以在 $n$ 为偶数的时候让 $a_i\leftarrow a_i+a_{i+1}$，将其转化为奇数。

接下来我们考虑一下奇数位置上的系数究竟有什么规律。通过专门的打表代码，我们可以发现奇数位置上的数的系数于杨辉三角非常相像，也就是组合数。具体为：第 $j$ 个奇数对应杨辉三角某一行的第 $j$ 个数。通过整理，不难发现若数组长度为 $n$，第 $i$ 个位置系数（无符号）为 $C_{(n-1)/2}^{(i+1)/2-1}$。

本体当中要求对答案取模，但是组合数需要进行除法。因此我们可以使用快速幂法求逆元计算组合数，本题也就顺应解决了。

打拳

你参加擂台赛，包括你有 $2^n$ 个选手参加，所有选手的实力为 $1\sim 2^n$ 中不重复的数，你的实力为 $1$。比赛规则的相邻两个人比赛，实力强的胜，胜者晋级下一轮，直到只剩一名冠军。你可以规定初始的排列顺序，并买通了 $m$ 名选手，这 $m$ 名选手会在比赛时输给你。你必须满足自己战胜的选手的实力的最长上升子序列的长度不小于 $k$。请问有多少种初始排列可以让你在满足条件的情况下获得冠军？

---

暴力思路：暴力搜出所有的 $(2^n)!$ 种排列，然后对于每一种排列都进行模拟，判断是否能获得冠军，并使用 dp 求出最长上升子序列，判断是否大于等于 $k$，最后统计答案即可。时间复杂度 $\mathcal{O}((2^n)!\times n\times 2^n)$，成功获得 $20$ 分。

扑克

大模拟，不会写；不可以，总司令。$0$ 分。

总结

• 排名：$2$；
• 比赛分数：$220/400$；`
• 情况：相比与 2024.9.24 模拟赛，一般；
• 问题：模拟能力较差。