题解：[[2024.9.29 模拟赛]] ## 光 #二分 在 $2\times 2$ 的网格内有 $4$ 盏灯，每盏灯可以选择不同的耗电量，耗电量为非负整数。若一盏灯的耗电量为 $x$，则对自己格子提供 $x$ 的亮度，对相邻格子提供 $\left\lfloor\cfrac{x}{2}\right\rfloor$ 的亮度，对对角格子提供 $\left\lfloor\cfrac{x}{4}\right\rfloor$ 的亮度。现告诉你每个格子需要达到的最小亮度，求每一盏灯的耗电量的和的最小值。 ## 爬 #位运算 #树 有 $n$ 点的树，每个根结点为 $1$，每个结点都有一只蚂蚁，第 $i$ 个结点的蚂蚁的权值为 $a_i$。对于每一只蚂蚁，它可以向父结点爬或留在原地，但只能选择一次。如果所有蚂蚁选择完毕后，有结点有多只蚂蚁，那么产生这些蚂蚁权值的异或和。问所有方案的快乐值之和。 ## 字符串 #贪心 有 $n$ 个字母 $\texttt{A}$，$m$ 个实力 $\texttt{B}$，可以将其组成长度为 $n+m$ 的字符串，你需要让组成的字符串权值尽量大，权值计算规则如下： 1. 每连续 $a$ 个 $\texttt{A}$，若下一个字母也为 $\texttt{A}$，则权值 $+1$，即 $\alpha$ 个连续的 $\texttt{a}$ 提供 $\left\lfloor\cfrac{\alpha-1}{a}\right\rfloor$； 2. 每连续 $b$ 个 ${} \texttt{B} {}$，若下一个字母也为 $\texttt{B}$，则权值 $+1$，即 $\beta$ 个连续的 $\texttt{B}$ 提供 $\left\lfloor\cfrac{\beta-1}{b}\right\rfloor$； 3. 若相邻两字符不相同，则权值 $+1$。 另外，只有在有连续 $c$ 个字母 $\texttt{B}$ 的情况下才能切换至 $\texttt{A}$，但是 $\texttt{A}$ 可以随时切换至 $\texttt{B}$。 ## 奇怪的函数 #线段树 #函数 有一函数 $f(x)$，函数有 $n$ 个步骤，每个步骤为一下三种形式之一： 1. $x\gets x+a_i$ 2. $x\gets\min(x,a_i)$ 3. $x\gets\max(x,a_i)$ 执行完 $n$ 个步骤之后，则返回更改后的 $x$。现你已经知道了每个步骤的类型以及每个步骤的数 $a_i$，有 $q$ 次询问，每一次询问可能会更改第 $i$ 个步骤的类型与权值，也有可能给出 $x$，在前面修改的基础上输出 $f(x)$ 的值。