分析

首先对于每个敌人单独预处理时间线（即在什么时候可以杀死这个敌人，什么时候杀不死了），然后通过一个总时间线去更新答案。

code

#include
    
     using namespace std;const int N = 1e5 + 10;map
     
       add, erase;set
      
        timeline;vector
       
        
          > V[N];int max_health[N], regen[N];int main() {    int n, m, bounty, increase, damage;    cin >> n >> m >> bounty >> increase >> damage;    for (int i = 0; i < n; i++) {        int h;        scanf("%d%d%d", &max_health[i], &h, &regen[i]);        V[i].push_back(make_pair(0, h));    }    for (int i = 0; i < m; i++) {        int t, id, h;        scanf("%d%d%d", &t, &id, &h);        V[id - 1].push_back(make_pair(t, h));    }    for (int i = 0; i < n; i++) {        auto& v = V[i];        sort(v.begin(), v.end());        if(increase > 0) {            if(damage >= max_health[i] || (!regen[i] && v.back().second <= damage)) {                return puts("-1") * 0;            }        }        for (int j = 0; j < v.size(); j++) {            if(v[j].second > damage) continue;            add[v[j].first]++;            long long interval = 2e9;            if(j != v.size() - 1) interval = min(interval, v[j + 1].first - v[j].first - 1);            if(regen[i]) interval = min(interval, 1LL * (damage - v[j].second) / regen[i]);            erase[v[j].first + interval]++;            timeline.insert(v[j].first);            timeline.insert(v[j].first + interval);        }    }    long long ans = 0, cnt = 0;    for (long long x : timeline) {        cnt += add[x];        ans = max(ans, cnt * (bounty + x * increase));        cnt -= erase[x];    }    cout << ans << endl;    return 0;}
        
       
      
     
    

分析

虽然 \(n\) 和 \(m\) 的数据都很大（ \(n*m\)的矩阵），但是 \(k\) 很小，那我们就应该考虑是否可能要枚举 \(k\) 了。

求期望分为求分子和分母。分母是所有的撒网方案数，分母无法改变，我们要求分子尽可能大。

分子实际上是要求在某种鱼的布局情况下，所有可能的撒网方案下，鱼出现的次数之和最大。那么可以考虑一条鱼在不同位置对答案的贡献最大是多少，也就是说有几种方案的网可以罩住这条鱼所在的位置，这里要对行列都预处理下，再用优先队列维护下答案，因为 \(n\) 和 \(m\) 都很大我们无法全部枚举出来，最后取最大的 \(k\) 个即可。

code

#include
    
     using namespace std;const int N = 1e5 + 10;int a[N], b[N];struct P {    long long x;    int i;    P() {}    P(long long x, int i): x(x), i(i) {}    friend bool operator <(P a, P b)  {        return a.x < b.x;    }};priority_queue
     
 q;int main() {    int n, m, r, k;    cin >> n >> m >> r >> k;    for (int i = 1; i <= n; i++) {        a[i] = min(n - r + 1, i) - max(i - r + 1, 1) + 1;    }    for (int i = 1; i <= m; i++) {        b[i] = min(m - r + 1, i) - max(i - r + 1, 1) + 1;    }    sort(a + 1, a + n + 1);    sort(b + 1, b + m + 1);    for (int i = 1; i <= n; i++) {        q.push(P(a[i] * b[m], m));    }    long long z = 1LL * (n - r + 1) * (m - r + 1);    long long s = 0;    while(k--) {        P p = q.top(); q.pop();        s += p.x;        if(p.i > 1) {            p.x /= b[p.i];            p.i--;            p.x *= b[p.i];            q.push(p);        }    }    printf("%.10f\n", 1.0 * s / z);    return 0;}
    

分析

二分答案 \(ans\)，问题转化成小于等于 \(ans\) 的有多少个数。

dfs 暴力枚举素因子构造数，当然不能直接枚举所有素因子，考虑分成两组（按下标奇偶交替分组），使得后面构造出的两组数数量尽可能相等。假设数量最多为 \(n\)，那么将两组排序后，\(O(n)\) 的复杂度就可以回答转化后的问题，当然排序会有 \(O(nlogn)\) 的复杂度。

由这道题可见 CF 的速度还是很快的，本地跑 3 秒，CF 1.3 秒。

code

#include
    
     using namespace std;int n;long long k;vector
     
       v1, v2;vector
      
        res1, res2;void dfs(int i, long long x, long long r, vector
       
         v, vector
        
         & res) {    res.push_back(x);    for(int j = i; j < v.size(); j++) {        if(v[j] <= r / x) dfs(j, x * v[j], r, v, res);        else break;    }}long long judge(long long r) {    int s = res2.size() - 1;    long long ans = 0;    for (int i = 0; i < res1.size(); i++) {        while(s >= 0 && res2[s] > r / res1[i]) s--;        ans += s + 1;    }    return ans;}int main() {    cin >> n;    for (int i = 0; i < n; i++) {        int p;        cin >> p;        !(i & 1) ? v1.push_back(p) : v2.push_back(p);    }    cin >> k;    res1.clear();    res2.clear();    dfs(0, 1, 1e18, v1, res1);    dfs(0, 1, 1e18, v2, res2);    sort(res1.begin(), res1.end());    sort(res2.begin(), res2.end());    long long l = 1, r = 1e18;    while(l < r) {        long long mid = l + r >> 1;        if(judge(mid) < k) l = mid + 1;        else r = mid;    }    cout << l << endl;    return 0;}