ooliver

NOIP 真题汇编 做题笔记

ooliver

题单

天天爱打卡

好像在以前的题单里但是没做

考虑 DP，设 fi 表示截止到第 i 天并且第 i 天打卡的最大能量值，dpi 表示截止到第 i 天的最大能量值；枚举打卡区间，可以列出转移方程：

fi=maxi-1j=i-k{dpj-(i-j)d+∑[lk,rk]∈[j+1,i]vk}

这里数据结构优化一下就是 O(nlogn) 的复杂度。

会发现实际上有用的 j 的取值肯定是给的区间的左右端点，所以我们只记录端点，离散化一下即可。

代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define lc p<<1
#define rc p<<1|1

const int N=2e5+5,inf=1e9;
int c,T;
int n,m,k,d;
int a[N],l[N],r[N],v[N];
vector<pair<int,int>> p[N];

struct SEG{
    int t[N<<2],mx[N<<2],lazy[N<<2];
    void pushup(int p){
        mx[p]=max(mx[lc],mx[rc]);
    }
    void pushdown(int p){
        if(lazy[p]){
            mx[lc]+=lazy[p],lazy[lc]+=lazy[p];
            mx[rc]+=lazy[p],lazy[rc]+=lazy[p];
            lazy[p]=0;
        }
    }
    void build(int p,int l,int r){
        t[p]=lazy[p]=mx[p]=0;
        if(l==r) return;
        int mid=(l+r)>>1;
        build(lc,l,mid);
        build(rc,mid+1,r);
        pushup(p);
    }
    void modify(int p,int l,int r,int x,int y,int k){
        if(l>=x&&r<=y){
            mx[p]+=k,lazy[p]+=k;
            return;
        }
        pushdown(p);
        int mid=(l+r)>>1;
        if(x<=mid) modify(lc,l,mid,x,y,k);
        if(y>mid) modify(rc,mid+1,r,x,y,k);
        pushup(p);
    }
    int query(int p,int l,int r,int x,int y){
        if(l>=x&&r<=y) return mx[p];
        pushdown(p);
        int mid=(l+r)>>1,res=0;
        if(x<=mid) res=max(res,query(lc,l,mid,x,y));
        if(y>mid) res=max(res,query(rc,mid+1,r,x,y));
        return res;
    }
}seg;

void solve(){
    cin>>n>>m>>k>>d;
    for(int i=1;i<=m;i++){
        cin>>r[i]>>l[i]>>v[i];
        l[i]=r[i]-l[i];
        a[i*2-1]=l[i],a[i*2]=r[i];
    }
    sort(a+1,a+1+(m<<1));
    n=unique(a+1,a+1+(m<<1))-a-1;
    
    for(int i=1;i<=m;i++){
        l[i]=lower_bound(a+1,a+1+n,l[i])-a;
        r[i]=lower_bound(a+1,a+1+n,r[i])-a;
        p[r[i]].push_back({l[i],i});
    }
    int ans=0;
    seg.build(1,0,n);
    for(int i=1;i<=n;i++){
        seg.modify(1,0,n,0,i-1,-d*(a[i]-a[i-1]));
        for(auto[l,id]:p[i]) seg.modify(1,0,n,0,l,v[id]);
        int id=lower_bound(a+1,a+1+n,a[i]-k)-a;
        if(id<=i-1) ans=max(ans,seg.query(1,0,n,id,i-1));
        seg.modify(1,0,n,i+1,i+1,ans);
    }
    cout<<ans<<"\n";
    for(int i=1;i<=m;i++) p[r[i]].clear();
}

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>c>>T;
    while(T--){
        solve();
    }
    return 0;
}

建造军营

因为只会断掉一条边，所以边双里两个点肯定是不会受影响的，所以我们找到边双后把图缩成树。

然后来做树形 DP，设两个状态分别表示只有当前点子树中有关键点且 LCA 为当前这个点，以及当前点子树内没有关键点的方案数，转移方程还是比较好像，就是讨论子节点到当前节点这个边到底是不是必选的。

代码：

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

const int N=1e6+5;
const int mod=1e9+7;
int n,m,idx,cnt,ans;
int u[N],v[N],p2[N];
int low[N],dfn[N],in[N],num[N];
int dp[N][2],siz[N];
vector<int> g[N],t[N];
stack<int> st;

void tj(int u,int f){
    st.push(u);
    dfn[u]=low[u]=++idx;
    for(int v:g[u]){
        if(v==f) continue;
        if(!dfn[v]){
            tj(v,u);
            low[u]=min(low[u],low[v]);
        }
        else low[u]=min(low[u],dfn[v]);
    }
    if(low[u]==dfn[u]){
        cnt++;
        while(1){
            int x=st.top();
            st.pop();
            in[x]=cnt,num[cnt]++;
            if(x==u) break;
        }
    }
}

void dfs(int u,int f){
    dp[u][0]=1,dp[u][1]=p2[num[u]]-1,siz[u]=1;
    for(int v:t[u]){
        if(v==f) continue;
        dfs(v,u);
        siz[u]+=siz[v];
        int f0=0,f1=0;
        f0=(dp[u][0]*dp[v][0]%mod*2ll)%mod;
        f1=(dp[u][1]*dp[v][0]%mod*2)%mod;
        (f1+=dp[u][1]*dp[v][1])%=mod;
        (f1+=dp[u][0]*dp[v][1])%=mod;
        dp[u][0]=f0,dp[u][1]=f1;
    }
    if(u==1) (ans+=(dp[u][1]*p2[m-siz[u]+1]))%=mod;
    else (ans+=(dp[u][1]*p2[m-siz[u]]))%=mod;
}

signed main(){
    cin>>n>>m;
    p2[0]=1;
    for(int i=1;i<=max(m,n);i++) p2[i]=(p2[i-1]*2)%mod;
    for(int i=1;i<=m;i++){
        cin>>u[i]>>v[i];
        g[u[i]].push_back(v[i]);
        g[v[i]].push_back(u[i]);
    }
    for(int i=1;i<=n;i++) if(!dfn[i]) tj(i,0);
    for(int i=1;i<=m;i++){
        if(in[u[i]]==in[v[i]]) continue;
        t[in[u[i]]].push_back(in[v[i]]);
        t[in[v[i]]].push_back(in[u[i]]);
    }
    dfs(1,0);
    cout<<ans;
    return 0;
}