2025.08.23打卡Day282

健康

• 10 点半睡，7 点起床。
• 100 仰卧起坐 + 100 俯卧撑，没做深蹲和跑步是因为膝盖有点不舒服，休息一下。

娱乐

• 做发型。
• 看海龟汤。

算法

Codeforces：

• https://codeforces.com/contest/538/problem/C ，1600 分，只需要枚举每两个之间最多能到多少即可。

AtCoder：

• https://atcoder.jp/contests/abc403/tasks/abc403_f ，洛谷评普及+/提高，经典表达式题目。对于一个数 n，可以考虑其两种构造方式：直接拆分成两个数的乘积，即 n = i * j，然后递归解决 i 和 j 的问题；或者拆分成 n = i + j，然后递归解决 i 和 j 的问题。递归边界是 1...1 的情况。注意细节，如果是 i * j 的情况，那么对于 i 和 j 来说，假如他们是通过加法得到的最短表达式，则应该加上括号才能正确相乘。这样做的复杂度正确，是因为可以粗略的估计出这个范围内每个数的最短字符串的长度肯定不会超过 200，所以完全存的下，拼接复杂度也可以接受。
• https://atcoder.jp/contests/abc402/tasks/abc402_f ，洛谷评普及+/提高，看到数据范围基本就知道是双向分别搜索了，也算是一种折半搜索。先从 (1, 1) 开始走，走恰好 n - 1 步，把这些值存到对应的位置上，这个至多有 2^20 个数要存，可以承受。然后再从 (n, n) 开始走，走到中间那些位置上时，事实上最大值只需要看两个数，一个是加起来让自己恰好 < m 的那个数，一个是最大的数。
• https://atcoder.jp/contests/abc389/tasks/abc389_e ，洛谷评提高+/省选-，首先可以考虑拿 k 个和拿 k + 1 个，代价差多少，发现是 (2 * k + 1) * p，所以可以按照这个去贪心，每多拿一个，就把下一个的代价放到堆里。但是这样朴素的做会 TLE，因为总钱数很多。考虑加速，使用二分，去看少于某个代价的物品能否都被拿，求出这个最大的代价，然后对于剩下的来说，每种物品至多只能再买一个，所以复杂度就有了保证。