题解：AT_abc469_e [ABC469E] Pro Exam Eligibility

_zyx2012 · 2026-08-07 09:55:52 · 题解

怎么题解区清一色二分啊，来补一发不二分的做法。

首先，给你一个区间 [l,r]，使用前缀和即可求出它的得分。

然后注意到最大区间 [l,r] 一定满足 S_l=S_r=1。

然后你注意到如果两个区间 [l_1,r] 的得分大于 [l_2,r]，那 [l_1,r+1] 的得分也大于 [l_2,r]。

然后你就会发现它的决策是有单调性的，每次在右侧插入一个新数，然后更新一下答案就可以了。

复杂度 \mathcal{O}(n)，做完了。

代码：

#include <bits/stdc++.h>
using namespace std;

using i64 = long long;
using u64 = unsigned long long;
using u32 = unsigned;

using i128 = __int128;
using u128 = unsigned __int128;

mt19937_64 mrand((u64)random_device{}() << 32 ^ random_device{}() ^
    chrono::high_resolution_clock::now().time_since_epoch().count());
template<class T = i64,class T2>T rnd(T l,T2 r){
return uniform_int_distribution<T>(l,r)(mrand);}

int main (){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);

    int n,k;
    cin >> n >> k;

    string s;
    cin >> s;

    s = ' ' + s;
    deque<int> q;
    double ans = 0;
    vector<int> cnt(n + 1);

    for (int i = 1;i <= n;i++) cnt[i] = cnt[i - 1] + (s[i] == 'o');

    auto calc = [&](int l,int r){
        return (cnt[r] - cnt[l - 1]) / (r - l + 1.);
    };

    for (int i = 1;i <= n;i++) if (s[i] == 'o'&&(q.empty()||q.back() != i - 1)) q.push_back(i);

    for (int i = 1,prv = 1;i <= n;i++) if (s[i] == 'o'&&cnt[i] >= k){
        for (;!q.empty()&&cnt[i] - cnt[q[0] - 1] >= k;q.pop_front())
            if (calc(q[0],i) > calc(prv,i)) prv = q[0];
        ans = max(ans,calc(prv,i));
    }

    cout << fixed << setprecision(10) << ans << '\n';
}