2024.9.29 题目

题解：2024.9.29 模拟赛

光

二分

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

爬

位运算 树

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

字符串

贪心

有 $n$ 个字母 $\text{A}$，$m$ 个实力 $\text{B}$，可以将其组成长度为 $n+m$ 的字符串，你需要让组成的字符串权值尽量大，权值计算规则如下：

1. 每连续 $a$ 个 $\text{A}$，若下一个字母也为 $\text{A}$，则权值 $+1$，即 $\alpha$ 个连续的 $\text{a}$ 提供 $\lfloor \frac{\alpha -1}{a}\rfloor$；
2. 每连续 $b$ 个 $\text{B}$，若下一个字母也为 $\text{B}$，则权值 $+1$，即 $\beta$ 个连续的 $\text{B}$ 提供 $\lfloor \frac{\beta -1}{b}\rfloor$；
3. 若相邻两字符不相同，则权值 $+1$。

另外，只有在有连续 $c$ 个字母 $\text{B}$ 的情况下才能切换至 $\text{A}$，但是 $\text{A}$ 可以随时切换至 $\text{B}$。

奇怪的函数

线段树 函数

有一函数 $f(x)$，函数有 $n$ 个步骤，每个步骤为一下三种形式之一：

1. $x\leftarrow x+a_i$
2. $x\leftarrow \min (x,a_i)$
3. $x\leftarrow \max (x,a_i)$

执行完 $n$ 个步骤之后，则返回更改后的 $x$。现你已经知道了每个步骤的类型以及每个步骤的数 $a_i$，有 $q$ 次询问，每一次询问可能会更改第 $i$ 个步骤的类型与权值，也有可能给出 $x$，在前面修改的基础上输出 $f(x)$ 的值。