E

考虑背包中一个物体进入dp过程即可 删去同理

#include <bits/stdc++.h>
using namespace std;
const int mod = 998244353;
#define int long long

signed main(){
    ios::sync_with_stdio(false);cin.tie(nullptr);
    int n,k;cin>>n>>k;
    vector<int>dp(k+1);
    dp[0]=1;
    for(int i=1;i<=n;i++){
        char c;cin>>c;
        int x;cin>>x;
        if(c=='-') for(int j=x;j<=k;j++)(dp[j]-=dp[j-x])%=mod;
        else for(int j=k;j>=x;j--)(dp[j]+=dp[j-x])%=mod;
        cout<<(dp[k]+mod)%mod<<'\n';
    }
    return 0;
}

F

二分答案 check x 轴枚举 y 轴直接维护出前缀 后缀 min max y坐标即可

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
#define all(x) (x).begin(),(x).end()
#define INF 0x3f3f3f3f3f3f3f3f
#define PII pair<int,int>

signed main(){
    ios::sync_with_stdio(false);cin.tie(nullptr);
    int n;cin>>n;
    vector<PII>v;
    vector<int>a,pre_mn(n,INF),pre_mx(n,-INF),suf_mn(n,INF),suf_mx(n,-INF);
    for(int i=1;i<=n;i++){
        int x,y;cin>>x>>y;
        v.push_back({x,y});
        a.push_back(x);
    }
    sort(all(v));
    sort(all(a));
    for(int i=0;i<n;i++){
        if(i)pre_mn[i]=min(pre_mn[i],pre_mn[i-1]);
        if(i)pre_mx[i]=max(pre_mx[i],pre_mx[i-1]);
        pre_mn[i]=min(pre_mn[i],v[i].second);
        pre_mx[i]=max(pre_mx[i],v[i].second);
    }
    for(int i=n-1;i>=0;i--){
        if(i!=n-1)suf_mn[i]=min(suf_mn[i],suf_mn[i+1]);
        if(i!=n-1)suf_mx[i]=max(suf_mx[i],suf_mx[i+1]);
        suf_mn[i]=min(suf_mn[i],v[i].second);
        suf_mx[i]=max(suf_mx[i],v[i].second);
    }
    int l=0,r=1e9;
    while(l<r){
        int mid=l+r+1>>1;
        int x=mid,flag=0;
        for(int i=0;i<n;i++){
            int R=a[i]+x;
            int it=lower_bound(all(a),R)-a.begin();
            if(it==n)continue;
            if(pre_mx[i]-suf_mn[it]>=x||suf_mx[it]-pre_mn[i]>=x){
                flag=1;
                break;
            }
        }
        if(flag)l=mid;
        else r=mid-1;
    }
    cout<<l<<endl;
    return 0;
}

G

我们发现等差数列 公差恒为x

这样我们在输入的时候就可以-下标*x

就是来找一个数 让他们都相等 而不是等差数列就好求多了

然后发现具有单调性

二分是肯定的 check mid长度类是否有一个数让他们路径和<=k

这个数我们必然是选中位数的路径 肯定是最短的 然后就是权值线段树二分找中位数 以及 维护一些val cnt的计算路径和了

时间复杂度O（n2logn）足以通过本题

例外： 我们可以发现 他二分过程可以双指针来替代 时间复杂度可以降为O（nlogn） 如果不会写线段树二分 那我们可以用一些偷鸡小技巧求中位数比如pbds

#include <bits/stdc++.h>
using namespace std;
const int N = 2e5+10;
#define int long long
#define PII pair<int,int>
struct node{
    int l,r,v,cnt;
}tr[N<<2];
int n,m,a[N],mpp[N];
void pushup(int i) {
    auto &u = tr[i], &l = tr[i << 1], &r = tr[i << 1 | 1];
    u.v = l.v + r.v;
    u.cnt = l.cnt + r.cnt;
}
void build(int i,int l,int r) {
    tr[i].l = l, tr[i].r = r, tr[i].cnt = 0, tr[i].v = 0;
    if (l == r) {
        return;
    }
    int mid = l + r >> 1;
    build(i << 1, l, mid);
    build(i << 1 | 1, mid + 1, r);
}
void modify(int i,int x,int k,int k2) {
    if (tr[i].l >= x && tr[i].r <= x) {
        auto &u = tr[i];
        u.v += k;
        u.cnt += k2;
        return;
    }
    if (tr[i].l > x || tr[i].r < x)return;
    if (tr[i << 1].r >= x)modify(i << 1, x, k, k2);
    if (tr[i << 1 | 1].l <= x)modify(i << 1 | 1, x, k, k2);
    pushup(i);
}
int query(int i,int f) {
    if (tr[i].l == tr[i].r) {
        return tr[i].l;
    }
    if (tr[i << 1].cnt >= f)return query(i << 1, f);
    else return query(i << 1 | 1, f - tr[i << 1].cnt);
}
PII query(int i,int l,int r) {
    PII res = {0, 0};
    if (tr[i].l >= l && tr[i].r <= r) {
        auto &u = tr[i];
        return {u.v, u.cnt};
    }
    if (tr[i].l > r || tr[i].r < l)return res;
    if (tr[i << 1].r >= l) {
        PII now = query(i << 1, l, r);
        res.first += now.first;
        res.second += now.second;
    }
    if (tr[i << 1 | 1].l <= r) {
        PII now = query(i << 1 | 1, l, r);
        res.first += now.first;
        res.second += now.second;
    }
    return res;
}
void solve() {
    cin >> n >> m;
    map<int, int> mp;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        a[i] -= i;
        mp[a[i]]++;
    }
    int idx = 0;
    for (auto[pos, w]: mp) {
        ++idx;
        mp[pos] = idx;
        mpp[idx] = pos;
    }
    int ans = 1;
    build(1, 1, n);
    for (int i = 1, j = i; i <= n && j <= n; i++) {
        while (j <= n) {
            modify(1, mp[a[j]], a[j], 1);
            int mid = j - i + 1;
            int z = mpp[query(1, (mid + 1) / 2)];
            auto[lv, lcnt]=query(1, 1, mp[z]);
            auto[rv, rcnt]=query(1, mp[z] + 1, idx);
            if (lcnt * z - lv + rv - rcnt * z <= m) {
                ans = max(ans, mid);
                j++;
            } else {
                modify(1, mp[a[i]], -a[i], -1);
                modify(1, mp[a[j]], -a[j], -1);
                break;
            }
        }
    }
    cout << ans << '\n';
}
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;cin >> t;
    while (t--) {
        solve();
    }
}