1. 如下代码

#include <bits/stdc++.h>
#define rep(i,l,r) for(int i=l;i<=r;++i)

using namespace std;

const int N=2e5+23;
const int SN=8e5+24;

int n;
int d[SN],tag[SN];

inline int read()
{
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9')
    {
        if(ch=='-')
            f=-1;
        ch=getchar();
    }
    while(ch>='0' && ch<='9')
        x=x*10+ch-'0',ch=getchar();
    return x*f;
}

inline void write(int x) {
    if(x<0){
        putchar('-');
        x=-x;
    }
    if(x>9) 
        write(x/10);
    putchar(x%10+'0');
}

void push_down(int s,int t,int p)
{
    int lc=2*p,rc=2*p+1;
    int mid=s+(t-s)/2;
    d[lc]=tag[p]*(mid-s+1);
    d[rc]=tag[p]*(t-mid);
    tag[lc]=tag[p];
    tag[rc]=tag[p];
    tag[p]=0;
}

void update(int l,int r,int v,int s,int t,int p)
{
    int lc=2*p,rc=2*p+1;
    if(l<=s&&r>=t)
    {
        d[p]=(t-s+1)*v;
        tag[p]=v;
        return;
    }
    if(tag[p]&&s!=t)
        push_down(s,t,p);
    int mid=s+(t-s)/2;
    if(l<=mid)
        update(l,r,v,s,mid,lc);
    if(r>mid)
        update(l,r,v,mid+1,t,rc);
    d[p]=d[lc]+d[rc];
}

// int query(int l,int r,int s,int t,int p)
// {
//     int lc=2*p,rc=2*p+1;
//     if(l<=s&&r>=t)
//         return d[p];
//     if(tag[p])
//         push_down(s,t,p);
//     int mid=s+(t-s)/2;
//     int ans=0;
//     if(l<=mid)
//         ans+=query(l,r,s,mid,lc);
//     if(r>mid)
//         ans+=query(l,r,mid+1,t,rc);
//     return ans;
// }

signed main()
{
    int t=read();
    while(t--){
        memset(d,0,sizeof(d));
        memset(tag,0,sizeof(tag));
        int n=read(),m=read();
        int full=-1;
        rep(i,1,m){
            int opt=read(),x=read();
            if(opt==1)
                update(x,x,1,1,n,1);
            if(opt==2)
            {
                if(x!=1) update(1,x-1,1,1,n,1);
                if(x!=n) update(x+1,n,1,1,n,1);
            }
            if(d[1]==n&&full==-1){
                full=i;
                for(i++;i<=m;++i)
                    int t1=read(),t2=read();
                break;
            }
        }
        write(full);
        putchar('\n');
    }
}

怎么卡常才能通过 P9343.

2. 一下代码

#include <bits/stdc++.h>
#define rep(i,l,r) for(int i=l;i<=r;++i)

using namespace std;

int n;
int s[424],f[424];
int dp[403][1002];

int dfs(int d,int zs,int qs){
    int& ans=dp[d][zs+qs];
    // if(ans!=0x3f3f3f) return ans;
    if(d==n+1){
        if(zs<0||qs<0) return 0;
        return zs+qs;
    }
    int ans0,ans1;
    ans0=dfs(d+1,zs,qs);
    ans1=dfs(d+1,zs+s[d],qs+f[d]);
    ans=max(ans1,ans0);
    return ans;
}

int main()
{
    memset(dp,0x3f3f3f,sizeof(dp));
    ios::sync_with_stdio(false);
    cin>>n;
    rep(i,1,n)
        cin>>s[i]>>f[i];
    cout<<dfs(1,0,0);
}

如何剪枝才能通过 P2340