专栏文章

题解：CF2110F Faculty

llw393
CF2110F题解参与者 4已保存评论 3

文章操作

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

当前评论
3 条
当前快照
1 份
快照标识符
@mip7h0t3
此快照首次捕获于
2025/12/03 07:24
3 个月前
此快照最后确认于
2025/12/03 07:24
3 个月前
查看原文
这道题算是本场除 AB 外，代码最为简单的了，但是思维难度大。
我们先证明命题 11：f(x,y)≤max⁡(x,y)f(x,y) \le \max(x,y)
证明：
若 x=yx = y 则 f(x,y)=0f(x,y) = 0。
否则设 x≤yx \le y。
此时 x mod y=x,y mod x=y−⌊yx⌋xx \bmod y = x, y \bmod x = y -\lfloor\frac yx\rfloor x。
f(x,y)=x+y−⌊yx⌋xf(x,y) = x + y - \lfloor\frac yx\rfloor x。
由于 ⌊yx⌋≥1\lfloor\frac yx\rfloor \ge 1，命题得证。
再证明命题 22：长度为 kk 的前缀中最大的 f(ai,aj)f(a_i,a_j)，ai≥aja_i \ge a_j，在 ai=max⁡j=1kaja_i = \max_{j=1}^k a_j 中取得。
证明：
设 aia_i 为长度为 kk 的前缀中的最大元素，f(ax,ay)f(a_x, a_y) 大于找到的值，ax≤xya_x \le x_y，由前命题，得 f(ax,ay)≤ayf(a_x, a_y)\le a_y。
我们再考虑 f(ai,ay)f(a_i, a_y)，由于 ay≤aia_y \le a_i，得 f(ax,ay)≤ay≤f(ai,ay)f(a_x,a_y)\le a_y \le f(a_i,a_y)。
最后证明命题三：若 x<y<2xx < y < 2x，则 f(x,y)=yf(x,y) = y
证明：
f(x,y)=f(x,y)=x+y−⌊yx⌋xf(x,y) = f(x,y) = x + y - \lfloor\frac yx\rfloor x，由 x<y<2xx < y < 2x，知 ⌊yx⌋=1\lfloor\frac yx\rfloor = 1，从而 f(x,y)=yf(x,y) = y。
借助上述三个命题得正确性，我们可以枚举了。设在长度为 kk 的前缀中，最大值为 xx，最大的 f(x,y)f(x,y) 为 ansans。
我们用以下步骤更新 ansans：
  1. 若 ak+1<xa_{k+1} <x，利用命题 22，更新 ansans；
  2. 若 x<ak+1<2xx < a_{k+1} < 2x，利用命题 33，更新 ansans；
  3. 若 ak+1≥2xa_{k+1} \ge 2x，直接暴力遍历数组。
由于每次在前缀最大值达到前一个最大值的两倍才会枚举数组内的所有元素，所以时间复杂度可以证明是 O(nlog⁡A)O(n\log A)，其中 A=max⁡i=1naiA = \max_{i=1}^n a_i。
代码：
CPP
#include<bits/stdc++.h>
using namespace std;

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

void solve(){
  int n; cin >> n;
  vector<int>a(n + 1);
  for(int i = 1; i <= n; i++) cin >> a[i];
  int ans = 0, maxn = a[1];
  for(int i = 1; i <= n; i++){
    ans = max(ans, f(maxn, a[i]));
    if(a[i] > maxn){
      if(a[i] >= maxn * 2){
        maxn = a[i];
        for(int j = 1; j <= i; j++) ans = max(ans, f(a[i], a[j]));
      } else { maxn = a[i]; ans = maxn; }
    }
    cout << ans << ' ';
  }
  cout << '\n';
}

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

评论

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

正在加载评论...