2024.9.29 模拟赛

题目：2024.9.29 题目

光

在 $2\times 2$ 的网格内有 $4$ 盏灯，每盏灯可以选择不同的耗电量，耗电量为非负整数。若一盏灯的耗电量为 $x$，则对自己格子提供 $x$ 的亮度，对相邻格子提供 $\lfloor \frac{x}{2}\rfloor$ 的亮度，对对角格子提供 $\lfloor \frac{x}{4}\rfloor$ 的亮度。现告诉你每个格子需要达到的最小亮度，求每一盏灯的耗电量的和的最小值。

---

首先，我们可以很快猜出：任意灯的耗电量都不大于对应位置需要的亮度，因为高于需要的亮度就没意义了。因此我们可以很快地写出 $\mathcal{O}(n^4)$ 无脑暴力，即枚举每一盏灯的耗电量并判断是否满足条件。

接下来考虑优化。不难发现，在枚举完前三个灯泡之后，第四个灯泡一定是耗电量越小越好，但是只有达到一定耗电量才能满足条件，因此可以使用二分求出第四个灯泡的最小耗电量将其优化至 $\mathcal{O}(n^3{\log }_{2}n)$。

经过短暂思考后发现，枚举完三个灯泡的耗电量之后，最后一个灯泡的最小耗电量是可以计算出来的，因为耗电量与给任意格子提供的亮度成正比，所以可以将其优化至 $\mathcal{O}(n^3)$。成功获得 $70$ 分。

爬

有 $n$ 点的树，每个根结点为 $1$，每个结点都有一只蚂蚁，第 $i$ 个结点的蚂蚁的权值为 $a_i$。对于每一只蚂蚁，它可以向父结点爬或留在原地，但只能选择一次。如果所有蚂蚁选择完毕后，有结点有多只蚂蚁，那么产生这些蚂蚁权值的异或和。问所有方案的快乐值之和。

---

由于本题计算答案的方式为异或和，因此考虑对权值进行二进制拆分。对于结点 $x$，$x$ 的所有儿子 $y$ 都可能会移动到 $x$。令 $s$ 为 $x$ 自己加上儿子的数量，则 $2^{s-1}$ 为儿子上移的组合数，$2^{n-s}$ 为其它结点上移的组合数。令 $a_i$ 表示为 $x$ 与它的儿子第 $i$ 位不为 $1$ 的数量，那么对于二进制第 $i$ 位，有 $2^i$ 种组合，答案需要加上 $\sum _{i=0}^{\lceil {\log }_{2}10^9\rceil }{2}^i\times 2^{s-1}\times 2^{n-s}$，其中 $\lceil {\log }_{2}10^9\rceil$ 大概是 $30$。

然后只有一只蚂蚁在结点上的情况，并加上对根结点的恶心特判，即可 AC。时间复杂度为 $\mathcal{O}(n)$，在递归函数里面开局部数组爆栈了，得 $90$ 分。

字符串

通过 $\mathcal{O}(2^{n+m})$ 的深度优先搜索暴力搜出所有的 $\text{A,B}$ 序列，然后现判断一下是否满足 $c$ 的限制，再计算出最终的权值，取最大值即可。时间复杂度为 $\mathcal{O}(2^{n+m}(n+m))$，原应获得 $20$ 分，写挂了得 $10$ 分。

奇怪的函数

通过两个数组存储函数的第 $i$ 步骤的信息，然后使用 $\mathcal{O}(1)$ 的更改与 $\mathcal{O}(n)$ 的调用时间复杂度写出暴力，总时间复杂度 $\mathcal{O}(nq)$，运气好得到 $70$ 分。

总结

• 排名：$1$；
• 比赛分数：$240/400$；
• 情况：相比与 2024.9.26 模拟赛 较好；
• 问题：数学推导能力不行，不会贪心。