【比赛记录】CFR957（Div.3）

KSCD_ · 2024-07-12 10:59:33 · 个人记录

记录

A-E 切了，F 想了一会困了就睡了，没做出。

题解

A. Only Pluses

枚举所有加的情况直接算即可，或者有数学结论，但我没想。

B. Angry Monk

由于最后要合到同一段，那么在最终合并之前只能剩最多一段非 1 的，显然要剩下最大的那段。总代价为所有其他段的 2a_i-1 之和。

C. Gorilla and Permutation

要最大化 f 同时最小化 g，显然要把不小于 k 的放在最前面，不大于 m 的放在最后面。另外为了让大数在 f 里多贡献，在 g 里少贡献，前面要递减放，后面要递增放，中间无所谓。

D. Test of Love

DP，设 f_i 表示到达 i 所需的最少游泳格数，如果第 i 格是地面，更新 f_j=\min(f_j,f_i),f_j\le i+m。如果是水，更新 f_{i+1}=\min(f_{i+1},f_i+1)，最后判断 f_{n+1} 是否不超过 k 即可。

E. Novice's Mistake

设 n 的长度为 l，考虑枚举最后保留的位数 i，可以算出保留部分的数字大小 k。那么有以下式子：

• na-b=k
• la-b=i

解得 a=\frac{k-i}{n-l}，求出 b，判断 a,b 是否合法即可。

当且仅当 n=1 时 n-l=0，会 RE，特判出来有 9999 种 b=a+1 的方案即可。

F. Valuable Cards

考虑贪心，也就是从左到右依次分出极长合法子段。先预处理出 x 的所有因数 dx_i，用 unordered_map 维护已经能构成的因数集合，每到 a_j 就枚举所有因数 k\in dx，看是否能新构成这个因数，也就是 a_j\mid k 且 \frac {k}{a_j} 出现过，直到 x 能构成就把 j 分到下一段即可。