题目：[[2024.9.29 题目]] ## 光 在 $2\times 2$ 的网格内有 $4$ 盏灯，每盏灯可以选择不同的耗电量，耗电量为非负整数。若一盏灯的耗电量为 $x$，则对自己格子提供 $x$ 的亮度，对相邻格子提供 $\left\lfloor\cfrac{x}{2}\right\rfloor$ 的亮度，对对角格子提供 $\left\lfloor\cfrac{x}{4}\right\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\limits_{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})$ 的深度优先搜索暴力搜出所有的 $\texttt{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 模拟赛]] 较好； - **问题**：数学推导能力不行，不会贪心。