水水水水水水水水水水（指文章）

比赛历程：

9:20 分写完了ABD，发现 D 大样例锅了就自闭了。

然后过一会猜了 C 的结论，之后就一直对拍。。D挂了好几次。还是代码能力不行

A

直接模拟。

#include <bits/stdc++.h>

#define fi first
#define se second
#define db double
#define U unsigned
#define P std::pair<int,int>
#define LL long long
#define pb push_back
#define MP std::make_pair
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define FOR(i,a,b) for(int i = a;i <= b;++i)
#define ROF(i,a,b) for(int i = a;i >= b;--i)
#define DEBUG(x) std::cerr << #x << '=' << x << std::endl

const int MAXN = 5e5 + 5;

struct Node{
    LL x,y;
    Node(LL x=0,LL y=0) : x(x),y(y) {}
    Node operator * (const LL &n) const {
        return Node(x*n,y*n);
    }
    Node operator + (const Node &t) const {
        return Node(x+t.x,y+t.y);
    }
}d[4];
// U R D L

int main(){
    d[0] = Node(0,1);d[1] = Node(1,0);d[2] = Node(0,-1);d[3] = Node(-1,0);
    int n,T;scanf("%d%d",&n,&T);
    Node D(0,0);int now = 0;
    FOR(i,1,n){
        LL x;scanf("%lld",&x);
        D = D+(d[now]*x);(now += x) %= 4;
    }
    d[0] = Node(D.x,D.y);
    FOR(i,1,3) d[i].x = d[i-1].y,d[i].y = -d[i-1].x;
    Node ans(0,0);int nnow = 0;
    FOR(i,1,T){
        ans = ans+d[nnow];
        (nnow += now) %= 4;
    }
    if(ans.x < 0) ans.x = -ans.x;
    if(ans.y < 0) ans.y = -ans.y;
    printf("%lld\n",ans.x+ans.y);
    return 0;
}

B

枚举一下最大的坐标是啥，用大根堆维护选了哪些点，每次弹堆顶弹到满足 $<m$ 的限制为止。

#include <bits/stdc++.h>

#define fi first
#define se second
#define db double
#define U unsigned
#define P std::pair<LL,LL>
#define LL long long
#define pb push_back
#define MP std::make_pair
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define FOR(i,a,b) for(int i = a;i <= b;++i)
#define ROF(i,a,b) for(int i = a;i >= b;--i)
#define DEBUG(x) std::cerr << #x << '=' << x << std::endl
#define int LL
const int MAXN = 1e5 + 5;
LL n,m;
P a[MAXN];
LL sm = 0;
std::multiset<LL> S;

signed main(){
    scanf("%lld%lld",&n,&m);
    FOR(i,1,n) scanf("%lld%lld",&a[i].fi,&a[i].se);
    std::sort(a+1,a+n+1);
    int ans = 0;
    FOR(i,1,n){
        S.insert(a[i].se);sm += a[i].se;
        int lim = m-a[i].fi;
        if(lim < 0) break;
        while(sm > lim){
            sm -= *S.rbegin();
            S.erase((--S.end()));
        }
        ans = std::max(ans,(int)S.size());
    }
    printf("%lld\n",ans);
    return 0;
}

C

手玩后发现规律：选了 $S$ 内的点，能都被选到的充要条件是 $\sum_{v \in S} L_v \leq n$。

然后就是个背包了。

#include <bits/stdc++.h>

#define fi first
#define se second
#define db double
#define U unsigned
#define P std::pair<int,int>
#define LL long long
#define pb push_back
#define MP std::make_pair
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define FOR(i,a,b) for(int i = a;i <= b;++i)
#define ROF(i,a,b) for(int i = a;i >= b;--i)
#define DEBUG(x) std::cerr << #x << '=' << x << std::endl

const int MAXN = 1000+5;
int n,L[MAXN],D[MAXN];
LL f[MAXN];

int main(){
    scanf("%d",&n);
    FOR(i,1,n) scanf("%d",L+i);FOR(i,1,n) scanf("%d",D+i);
    CLR(f,-0x3f);f[0] = 0;
    FOR(i,1,n){
        ROF(j,n,L[i]){
            f[j] = std::max(f[j],f[j-L[i]]+D[i]);
        }
    }
    LL ans = 0;
    FOR(i,0,n) ans = std::max(ans,f[i]);
    printf("%lld\n",ans);
    return 0;
}

D

对于每个位置 $i$ 开两个 set 分别维护前 $i$ 大和剩下的数，再开两个全局 set 维护前 $n$ 大和剩下的数。

每次修改的时候相当于往全局 set 里插入/删除一些点，直接做就行了。要开 multiset，注意边界情况的处理即可。

#include <bits/stdc++.h>

#define fi first
#define se second
#define db double
#define U unsigned
#define P std::pair<int,int>
#define LL long long
#define pb push_back
#define MP std::make_pair
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define FOR(i,a,b) for(int i = a;i <= b;++i)
#define ROF(i,a,b) for(int i = a;i >= b;--i)
#define DEBUG(x) std::cerr << #x << '=' << x << std::endl

const int MAXN = 3e5 + 5;
std::multiset<int> S1[MAXN],S2[MAXN];// 1=big
std::multiset<int> big,small;
int n,m;LL sm;
char str[MAXN];

inline void add(int x){
    if(big.size() < n){
        big.insert(x);
        sm += x;
    }
    else{
        int t = *big.begin();
        if(x > t){
            sm -= t;
            small.insert(t);
            big.erase(big.begin());
            sm += x;
            big.insert(x);
        }
        else{
            small.insert(x);
        }
    }
}

inline void del(int x){
    if(big.find(x) != big.end()){
        sm -= x;
        big.erase(big.find(x));
        if(!small.empty()){
            int b = *small.rbegin();
            small.erase((--small.end()));
            big.insert(b);
            sm += b;
        }
    }
    else{
        auto p = big.find(x);
        if(p != big.end()){
            sm -= x;
            big.erase(p);
            sm += *small.rbegin();
            big.insert(*small.rbegin());
            small.erase((--small.end()));
        }
        else{
            small.erase(small.find(x));
        }
    }
}

int main(){
    scanf("%d%d",&n,&m);
    FOR(i,1,m){
        scanf("%s",str);int t,x;scanf("%d%d",&t,&x);
        if(str[0] == 'B'){
            if(S1[t].size() < t){
                S1[t].insert(x);
                add(x);
            }
            else{
                int b = *S1[t].begin();
                if(x > b){
                    del(b);
                    S2[t].insert(b);
                    S1[t].erase(S1[t].begin());
                    add(x);
                    S1[t].insert(x);
                }
                else{
                    S2[t].insert(x);
                }
            }
        }
        else{
            if(S1[t].find(x) != S1[t].end()){
                S1[t].erase(S1[t].find(x));
                del(x);
                if(!S2[t].empty()){
                    int b = *S2[t].rbegin();
                    S2[t].erase((--S2[t].end()));
                    S1[t].insert(b);
                    add(b);
                }
            }
            else{
                auto p = S1[t].find(t);
                if(p != S1[t].end()){
                    S1[t].erase(p);
                    del(x);
                    add(*S2[t].rbegin());
                    S1[t].insert(*S2[t].rbegin());
                    S2[t].erase((--S2[t].end()));
                }
                else{
                    S2[t].erase(S2[t].find(x));
                }
            }
        }
        printf("%lld\n",sm);
    }
    return 0;
}