DiandianSPA @ 2024-09-24 19:42:41

by yzm0325 @ 2024-10-02 14:24:24

@DiandianSPA 二叉堆

by yzm0325 @ 2024-10-02 14:28:09

或者可持久化非确定状态AC自动机分块维护线段平衡仙人掌优化最小费用最大流预处理混合图上莫比乌斯反演莫队带花和=NPY舞蹈链并查集树状数组套主席树预处理动态DP分治FFT求多项式逆元对数函数的指数函数用可持久化并查集合并最小费用循环流上插头DP

by Rieman_sum @ 2024-10-03 08:57:45

这题不是spfa模板题吗

by _shining @ 2024-10-12 16:32:41

二分即可。

by Lucashuang @ 2024-11-03 13:17:13

二分+队列+递归即可

#include<bits/stdc++.h>
using namespace std;
int m , n , a[200001] , l1 , s , r1 , maxx = 0 , ans;
priority_queue<int> que;
int fen(int l , int r){
    if(l == r) return a[l];
    m = (l + r) / 2;
    s = a[m] , l1 = a[m] , r1 = a[m + 1];
    for(int i = m - 1; i >= l; i--){
        s += a[i];
        l1 = max(l1 , s);
    }
    int s1 = a[m + 1];
    for(int i = m + 2; i <= r; i++){
        s1 += a[i];
        r1 = max(r1 , s1);
    }
    return max(max(fen(l , m) , fen(m + 1 , r)) , l1 + r1);
}
bool check(int k){
    for(int i = 1; i <= n; i++){
        que.push(a[i]);
    }
    while(!que.empty()){
        k -= que.top();
        que.pop();
    }
    if(k){
        return true;
    } else {
        return false;
    }
}
int f(int n){
    if(n == 1) return a[1];
    return a[n] + f(n - 1);
}
int main(){
    int n = 2 , ans;
    for(int i = 1; i <= n; i++){
        cin >> a[i];
    }
    ans = fen(1 , n);
    if(check(ans)){
        if(f(n) == ans){
            cout << ans;
        } else {
            cout << "Wrong!";
        }
    } else {
        cout << "Wrong!";
    }
    return 0;
}