题解：CF2110F Faculty

qqqaaazzz_qwq · 2025-05-26 12:32:24 · 题解

比赛结束前 8 分钟会了，3 分钟写完代码，结束前 5 分钟过了（

先来挖掘一下这个 f(x,y) 的性质。（假设 x > y）。

• (x \bmod y) + (y \bmod x) = (x \bmod y) + y \geq y
• (x \bmod y) + (y \bmod x) \leq x-y+y \leq x

总结：y \leq f(x,y) \leq x。

设前缀最大值为 x，前缀严格次大值为 y，若不存在严格次大值，则前缀所有元素都相同，结论自然成立（答案为 0）。则我们可以证明答案 \geq y，因为 f(x,y)\geq y。如果我们不选 x，则结果必定 \leq y，是不优的。所以前缀最大值必定被选上（关键结论）。

然后这道题就基本做完了，下面是代码：

#include <bits/stdc++.h>
#define FAST ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
using namespace std;
int a[1000010];
int n;

int f(int x,int y){
    return x%y+y%x;
}

void solve(){
    cin >> n;
    for (int i=1;i<=n;i++) cin >> a[i];
    int mx = 0,ans = 0;
    for (int i=1;i<=n;i++){
        if(a[i]>=mx*2){
            mx = a[i];//暴力更新，做多发生 log V 次
            ans = 0;
            for (int j=1;j<=i;j++) ans = max(ans,f(a[i],a[j]));
        }
        else if(a[i]>mx){
            ans = a[i];//f(a[i],mx) = mx + a[i] - mx
            mx = a[i];
        }
        else ans = max(ans,f(a[i],mx));
        cout << ans << " ";
    }
    cout << "\n";
}

signed main()
{
    int t;
    cin >> t;
    while(t--) solve();
    return 0;
}