[语言月赛 202401] 区间函数最大值 题解

· · 题解

Source & Knowledge

2024 年 1 月语言月赛,由洛谷网校入门计划/基础计划提供。

题目大意

给定 A, B, C, D, E, F, G, P, X_1, X_2, Y_1, Y_2,求当 X _ 1 \leq x \leq X _ 2Y _ 1 \leq y \leq Y _ 2x, y 均为整数时 f(x, y) = (A x ^ 3 + B y ^ 3 + C x ^ 2 y + Dxy ^ 2 + Exy + Fx + Gy) \bmod P 的最大值。

题目分析

本题考察对二重循环结构的运用。

注意到 x, y 都是整数且 X _ 1 \leq x\leq X _ 2Y _ 1 \leq y \leq Y _ 2,因此使用一个二重循环枚举所有的 x, y 即可。核心代码如下:

for (int x = x1; x <= x2; ++x) {
    for (int y = y1; y <= y2; ++y) {
        // 计算函数值        
    }
}

其中查找函数最大值使用擂台法,即,初始时使用一个变量 c(本题 c 可初始化为 0),此后不断让 c 与新计算的函数值比较并取最大值即可。

int c = 0;

// 在循环内
long long fxy = ....
if (fxy > c) c = fxy;

最后需要注意,x, y 最大值为 10 ^ 3A \sim G 最大值为 10 ^ 9,因此 A x ^ 3 等的最大值可以达到 10 ^ {12},超过 int 类型所能容纳的范围。因此可能需要使用 long long 来做函数的计算,以避免溢出的情况。

视频讲解