T1 蜡烛

分析

这道题目要求我们在数轴上选择K个蜡烛点燃，使得从原点出发，移动并点燃这些蜡烛所需的总时间最短。蜡烛的位置已经按升序排列。

思路

1. 关键观察：最优解一定是选择连续的K个蜡烛。因为如果选择不连续的蜡烛，中间跳过某些蜡烛会导致路径更长。
2. 计算时间：对于每个连续的K个蜡烛区间[x_i, x_j]，计算从原点出发的最短路径：

（1）可能路径1：先到最左边的蜡烛x_i，再到最右边的x_j

（2）可能路径2：先到最右边的蜡烛x_j，再到最左边的x_i

（3）取这两种路径中的较小值

时间复杂度

O(N)，因为我们只需要遍历蜡烛数组一次，对每个窗口进行常数时间的计算。

T2 白日梦

思路1：将读入的字符串翻转，dream、dreamer、erase、eraser变成maerd、remaerd、esare、resare，贪心得进行线性扫描即可。

思路2：利用字符串末尾字符erase函数O(1)时间复杂度的性质，从末尾进行判定删除：

T3 重复重复重复重复

思路

1. 理解重复数：所有数字相同的数称为重复数，如111、2222等。对于数字$d(1-9)$，长度为k的重复数可以表示为$d×(10^k-1)/9$。

2. 枚举数字和长度：

- 我们需要枚举所有可能的数字d（1-9）和长度k（1到N）    - 对于每个d和k，检查$d×(10^k-1)/9$是否能被M整除    - 记录满足条件的最大数

3. 优化计算：    - 预处理$10^k mod 9 M$的值，避免重复计算    - 对于每个k，计算$10^k mod 9M$    - 检查是否存在d使得$d×(10^k-1) ≡ 0 mod 9M$

4. 寻找最大解：    - 从最大长度N开始向下检查    - 对于每个长度k，检查是否存在合适的d    - 一旦找到满足条件的k和d，即可构造最大解

T4

题意

在一个H行W列的网格中，有些格子是障碍物（'#'表示），其他是空地（'.'表示）。我们需要找到一个空地点放置灯，使得灯能照亮最多的格子。灯可以照亮同一行和同一列的所有格子，直到遇到障碍物为止。

思路

这道题的关键是预处理每个格子能向四个方向（上、下、左、右）延伸的最大长度。具体来说：

1. 对于每个格子(i,j)，计算它左边连续的空地数量（包括自己）left[i][j]
2. 计算它右边连续的空地数量（包括自己）right[i][j]
3. 计算它上边连续的空地数量（包括自己）up[i][j]
4. 计算它下边连续的空地数量（包括自己）down[i][j]

然后对于每个空地格子(i,j)，它能照亮的格子数量就是 left[i][j] + right[i][j] + up[i][j] + down[i][j] - 3（因为自己会被四个方向各算一次，需要减去重复的3次）。