题解：CF2110F Faculty

· · 题解

不失一般性的，我们设 x \le y。

从最简单的情况考虑，当 x = y 时，f(x,y) = 0 + 0 = 0。以下均为 x < y 的情况，推推式子可知：

f(x,y) = x \bmod y + y \bmod x= x + y - \lfloor\frac{x}{y}\rfloor y - \lfloor\frac{y}{x}\rfloor x

由于 x < y，式子可以进一步化简：

f(x,y) = x + y - \lfloor\frac{y}{x}\rfloor x

由 x < y 可知 \lfloor\frac{y}{x}\rfloor \ge 1，于是可以得到以下观察：

x \le x + y \bmod x = f(x,y) = y - (\lfloor\frac{y}{x}\rfloor - 1)x \le y

分析可知，当 x \mid y 时不等式左侧取等；当 x < y < 2x 时不等式右侧取等。

接下来考虑对于任意前缀长度为 k 的答案是怎么取到的。当 n = 1 时答案显然为 0，n = 2 时为 a_1 \bmod a_2 + a_2 \bmod a_1。对于 n \ge 3 的情况，考虑 f(x,y) 与 f(y,z) 满足 x \le y \le z，由不等式可知 x \le f(x,y) \le y \le f(y,z) \le z，因此可以证明前缀长度为 k 的最大值里一定有一个数取到 \max \limits_{i = 1}^k\{a_i\}。

再由不等式可知存在 y \ge 2x 的情况时才会使得答案变得不确定，而这种情况最多只会有 \log 次，因此直接暴力更新即可，总时间复杂度 O(n \log n)。

代码如下：

void solve ()
{
    int n = read ();
    vector <int> a (n + 1),ans (n + 1,0);
    for (int i = 1;i <= n;++i) a[i] = read ();
    int mx = a[1];
    for (int i = 2;i <= n;++i)
    {
        if (a[i] > mx)
        {
            if (a[i] >= mx * 2) {for (int j = 1;j < i;++j) ans[i] = max (ans[i],a[i] % a[j] + a[j] % a[i]);}
            else ans[i] = a[i];
            mx = a[i];
        }
        else ans[i] = max (ans[i - 1],mx % a[i] + a[i] % mx);
    }
    for (int i = 1;i <= n;++i) printf ("%d ",ans[i]);
    puts ("");
}