专栏文章

题解：CF2110F Faculty

SSUNCHAOYI废物生成器
CF2110F题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@min03fkk
此快照首次捕获于
2025/12/01 18:22
3 个月前
此快照最后确认于
2025/12/01 18:22
3 个月前
查看原文
不失一般性的，我们设 x≤yx \le y。
从最简单的情况考虑，当 x=yx = y 时，f(x,y)=0+0=0f(x,y) = 0 + 0 = 0。以下均为 x<yx < y 的情况，推推式子可知：
f(x,y)=x mod y+y mod x=x+y−⌊xy⌋y−⌊yx⌋xf(x,y) = x \bmod y + y \bmod x= x + y - \lfloor\frac{x}{y}\rfloor y - \lfloor\frac{y}{x}\rfloor x
由于 x<yx < y，式子可以进一步化简：
f(x,y)=x+y−⌊yx⌋xf(x,y) = x + y - \lfloor\frac{y}{x}\rfloor x
由 x<yx < y 可知 ⌊yx⌋≥1\lfloor\frac{y}{x}\rfloor \ge 1，于是可以得到以下观察：
x≤x+y mod x=f(x,y)=y−(⌊yx⌋−1)x≤yx \le x + y \bmod x = f(x,y) = y - (\lfloor\frac{y}{x}\rfloor - 1)x \le y
分析可知，当 x∣yx \mid y 时不等式左侧取等；当 x<y<2xx < y < 2x 时不等式右侧取等。
接下来考虑对于任意前缀长度为 kk 的答案是怎么取到的。当 n=1n = 1 时答案显然为 00，n=2n = 2 时为 a1 mod a2+a2 mod a1a_1 \bmod a_2 + a_2 \bmod a_1。对于 n≥3n \ge 3 的情况，考虑 f(x,y)f(x,y) 与 f(y,z)f(y,z) 满足 x≤y≤zx \le y \le z，由不等式可知 x≤f(x,y)≤y≤f(y,z)≤zx \le f(x,y) \le y \le f(y,z) \le z，因此可以证明前缀长度为 kk 的最大值里一定有一个数取到 max⁡i=1k{ai}\max \limits_{i = 1}^k\{a_i\}。
再由不等式可知存在 y≥2xy \ge 2x 的情况时才会使得答案变得不确定，而这种情况最多只会有 log⁡\log 次，因此直接暴力更新即可，总时间复杂度 O(nlog⁡n)O(n \log n)。
代码如下：
CPP
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 ("");
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...