7059 分配

思路分析

男生每人分 x 个，女生每人分 y 个。

要求：

• 每个学生至少 1 个，至多 100000 个；
• 男生之间分到的糖果数相同，女生之间分到的糖果数相同；
• 如果男生和女生都存在，则必须 x > y；
• 剩下糖果尽量少，也就是分出去的糖果尽量多。

分类讨论：

1. 只有男生：让男生每人尽量多分，但不能超过 100000；
2. 只有女生：同理；
3. 男女都有：枚举女生每人分到的数量 y，范围最多只有 1~100000，再计算男生最多能分多少 x。

如果不存在合法方案，输出 -1。

C++代码

4509 [CSP-J 2023T2] 公路

思路分析

油箱无限大，所以如果之前遇到过更便宜的油站，就应该尽量用之前更便宜的价格买油。

从左到右走：

• minPrice 记录到当前为止遇到过的最低油价；
• left 表示当前车里剩下的油还能跑多少公里；
• 如果剩余里程不够走下一段，就按当前最低油价买油；
• 因为只能买整数升，所以需要向上取整。

买 need 公里的油量：

liters = (need + d - 1) / d

C++代码

4859 二维前缀和模板

思路分析

二维前缀和 s[i][j] 表示从 (1,1) 到 (i,j) 这个矩形内所有元素之和。

计算公式：

s[i][j] = s[i-1][j] + s[i][j-1] - s[i-1][j-1] + a[i][j]

查询子矩阵 (x1,y1) 到 (x2,y2) 的和：

s[x2][y2] - s[x1-1][y2] - s[x2][y1-1] + s[x1-1][y1-1]

因为矩阵大小最大 1000 x 1000，询问最多 200000，直接每次枚举子矩阵会超时，必须用二维前缀和做到每次 O(1) 查询。

C++代码

7378 [AHOI2018初中组] 分组

思路分析

每组必须由连续的实力值组成，并且同一组内不能出现重复值。目标是让最小组的人数尽量大。

先排序。按实力值从小到大处理，每个实力值可能出现多次。

贪心原则：

• 如果当前实力值能接在上一实力值结尾的小组后面，就优先接到长度最短的小组后面；
• 因为短的小组最危险，优先延长短组，才能让最终最小组尽量大；
• 如果当前数量比上一批正在延续的小组更多，多出来的只能新开组；
• 如果当前数量更少，没被延续的小组就在上一实力值结束。

用两个数组保存“以上一个值结尾的小组长度”和“以当前值结尾的小组长度”。这些长度始终按从小到大排列。

C++代码

6381 严格的Aki

思路分析

要求最短区间 [l,r]，使区间内包含 1~m 这 m 种不同数字。

使用双指针维护窗口：

• cnt[x] 表示当前窗口里数字 x 出现了几次；
• kind 表示当前窗口已经包含多少种不同数字；
• 右指针不断扩展窗口；
• 当 kind == m 时，说明当前窗口合法，就尝试移动左指针缩短窗口；
• 每次合法时更新最短答案，如果长度相同，因为左指针是从小到大移动的，先遇到的左端点更小。

C++代码