49周作业
2025.12.7-2025.12.13
A. Painting With Two Colors
B. Alice and Bob
C. Maximum Sum
D. Matching Numbers
E. Add, Divide and Floor
F. Did We Get Everything Covered?
$ Solution: $
贪心。
可以发现整个子序列越靠后，接不上的可能越大。
所以子序列的每一个字母一定是位置越靠后越好。
子序列第一个字母一定是前 $ k $ 个字母中第一个出现的位置最靠后的那个字母....依次类推。
实现上可以用 $ f_{i,j} $ 表示$ i \(以后第\) j $个字母出现的最早位置。
每次选取\(f_{i,j}\)最大的$ j $，然后令 $ i=f_{i,j} $。
G. Alice's Adventures in Cutting Cake
\(Solution:\)
贪心。
可以发现，答案一定是一个连续区间。
所以就是要在满足$ m $合法后，剩余的一段和最大。
而总数\(m\)不变，可以枚举在答案左边的区间数\(k\),则右边的区间数为\(m-k\)。
对于这两段前缀和后缀，必定要使其长度和最小，使得答案区间长度最大。
可以贪心地维护一个指针前后扫一遍求出当有\(i\)段合法区间的最小左端点和最大右端点。
最后枚举左右区间数，取答案的最大值即可。
浙公网安备 33010602011771号