专栏文章

NOIP2025补题笔记

SStaque
算法·理论参与者 4已保存评论 3

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
3 条
当前快照
3 份
快照标识符
@mj8u50bp
此快照首次捕获于
2025/12/17 01:07
2 个月前
此快照最后确认于
2026/02/12 01:29
上周
查看原文
越菜越练。

A

一眼贪，注意到整组的买一定只买 x+yx+y 最小的那一组。
对于只买 xx 的，排序然后枚举前缀和即可。
AC CodeCPP
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N=100005;
int n;ll m,res;
ll a[N],b[N];
int main(){
  ios::sync_with_stdio(0);
  cin.tie(nullptr);
  cin>>n>>m;
  for(int i=1;i<=n;i++)cin>>a[i]>>b[i],b[i]+=a[i];
  sort(b+1,b+1+n),sort(a+1,a+1+n);
  for(int i=0;i<=n;i++){
    if(i)a[i]+=a[i-1];
    if(a[i]<=m)res=max(res,(m-a[i])/b[1]*2+i);
  }
  cout<<res;
  return 0;
}

B

启示

特殊性质 m=2m=2 启示了我们什么？
如果第一个是 wx=1w_x=1，后面被卡住的第一个 wy=2w_y=2，买的最后一个是 wz=1w_z=1，满足 az+ax<aya_z+a_x<a_y 则会爆炸。

正解

扩展到整体。
已经花了 m−1m-1，然后第一个被卡住的是 uu，最后买下的是 vv，则如果前面买的存在一个 xx，满足 wx=1w_x=1 且 av+ax<aua_v+a_x<a_u 则不优。
因此容斥算不合法方案。
枚举 uu，我们可以将其划分为三个部分。
  1. i>ui>u，什么时候都会在 uu 前考虑。
  2. i<ui<u 且 ai×2>aua_i\times 2>a_u，当 wi=1w_i=1 时会在前面考虑，wi=2w_i=2 反之。
  3. ai×2≤aua_i\times 2\le a_u，什么时候都在 uu 后考虑。
分别称为 AA，BB，CC。
可以证明 vv 一定在 CC 中。
在 CC 中枚举 vv。
此时可以确定可能会使策略爆炸的部分，满足 ai<au−ava_i<a_u-a_v，记为 DD。
如何使 AA 和 BB 中在前考虑的部分满足 ∑wi=m−1\sum w_i=m-1？
BB 只有 wi=1w_i=1 才会在前面产生 11 的花费；AA 一定在前面考虑，所以至少产生 11 的花费，减去这部分，需要的花费就是 m−1−∣A∣m-1-|A| 而这部分花费由 AA 中的 wi=2w_i=2 和 BB 中的 wi=1w_i=1 贡献。
num1=(∣A∣+∣B∣m−1−∣A∣)num1={{|A|+|B|}\choose{m-1-|A|}}
如何对爆炸的策略计数？
这是困难的，所以考虑在这里再容斥一次，求满足条件的数目。
当 ii 在 DD 中也在 AA 或 BB 中，那么其 wiw_i 必须为 22。
因此对原式做调整。
设 E=A∪BE=A\cup B。
num2=(∣A∣+∣B∣−∣D∩E∣m−1−∣A∣−∣D∩A∣)num2={{|A|+|B|-|D\cap E|}\choose{m-1-|A|-|D\cap A|}}
后面的 CC 中，i>vi>v 的 wi=2w_i=2 ，i<vi<v 随便玩了，设这个数为 ku,vk_{u,v}
所以答案就出来了。
ans=2n−∑u∑v2ku,v((∣A∣+∣B∣m−1−∣A∣)−(∣A∣+∣B∣−∣D∩E∣m−1−∣A∣−∣D∩A∣))ans=2^n-\sum_u \sum_v 2^{k_{u,v}}({{|A|+|B|}\choose{m-1-|A|}}-{{|A|+|B|-|D\cap E|}\choose{m-1-|A|-|D\cap A|}})
完结。
AC CodeCPP
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N=5005;
const int mod=998244353;
ll qpow(ll x,int y){
  ll res=1;
  while(y){
    if(y&1)res=res*x%mod;
    x=x*x%mod,y>>=1;
  }return res;
}
struct Set{int bg,ed,siz;}S[10];
int n,m,a[N],t[N];
ll fac[N],ifac[N];
inline ll C(int n,int m){
  if(m>n||n<0||m<0)return 0;
  return fac[n]*ifac[m]%mod*ifac[n-m]%mod;
}
inline int getJ(Set x,Set y){//取两集之交大小
  int l=max(x.bg,y.bg),r=min(x.ed,y.ed);
  return max(0,r-l+1);
}
void solve(){
  cin>>n>>m;ll res=0;
  for(int i=1;i<=n;i++)cin>>a[i];
  n++,a[n]=0;
  sort(a+1,a+1+n);
  for(int u=n;u>=2;u--){
    S[1]={u+1,n,n-u};
    int re=u-1,j=1;
    while(a[re]*2>a[u])re--;
    S[2]={re+1,u-1,(u-1)-(re+1)+1};
    S[3]={1,re,re};
    ll num1=C(S[1].siz+S[2].siz,m-S[1].siz-1);
    if(num1==0)continue;
    for(int v=S[3].ed;v>=1;v--){
      while(j<=n&&a[u]-a[v]>a[j])j++;
      S[5]={1,j-1,j-1};
      int sizE=getJ(S[5],S[1])+getJ(S[5],S[2]);
      ll num2=C(S[1].siz+S[2].siz-sizE,m-S[1].siz-1-getJ(S[1],S[5]));
      int sizF=max(v-2,0);
      ll num=(num1-num2+mod)%mod*t[sizF]%mod;
      res=(res+num)%mod;
    }
  }
  res=(t[n-1]+mod-res)%mod;
  cout<<res<<"\n";
}
int main(){
  ios::sync_with_stdio(0);
  cin.tie(nullptr);
  fac[0]=ifac[0]=t[0]=1;
  for(int i=1;i<N;i++)fac[i]=fac[i-1]*i%mod,t[i]=t[i-1]*2%mod;
  ifac[N-1]=qpow(fac[N-1],mod-2);
  for(int i=N-2;i>=1;i--)ifac[i]=ifac[i+1]*(i+1)%mod;
  int CC,TC;cin>>CC>>TC;
  while(TC--)solve();
  return 0;
}

C

解法1

首先有个暴力 dpdp。
设 fu,i,jf_{u,i,j} 为 uu 点及其子树 mex⁡=i\operatorname{mex}=i，由 jj 个点权 ≥i\ge i。
有树上背包做法，具体的，一维钦定最大值，一维背包转移，然后从后往前递推即可做到 O(n3)O(n^3)，有 4848 分
n3n^3 CodeCPP
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N=405;
const ll inf=1e15;
inline void gmax(ll &x,ll y){x=max(x,y);}
int n,m,fa[N],siz[N];
ll f[N][N][N],tmp[N],t[N][N];
vector<int> G[N];
void dfs(int u){
  f[u][0][1]=0,f[u][1][0]=0,siz[u]=1;
  for(auto v:G[u]){
    dfs(v);
    for(int i=0;i<=siz[u]+siz[v];i++)
      for(int j=0;j<=siz[u]+siz[v];j++)t[i][j]=-inf;
    for(int i=0;i<=siz[u];i++)tmp[i]=-inf;
    for(int vmx=0;vmx<=siz[v];vmx++){
      for(int i=0;i<=siz[u];i++)tmp[i]=max(tmp[i],f[u][vmx][i]);
      for(int i=0;i<=siz[u];i++)
        for(int j=0;j<=siz[v];j++)
          gmax(t[vmx][i+j],tmp[i]+f[v][vmx][j]);
    }
    for(int i=0;i<=siz[v];i++)tmp[i]=-inf;
    for(int umx=0;umx<=siz[u];umx++){
      for(int i=0;i<=siz[v];i++)tmp[i]=max(tmp[i],f[v][umx][i]);
      for(int i=0;i<=siz[u];i++)
        for(int j=0;j<=siz[v];j++)
          gmax(t[umx][i+j],f[u][umx][i]+tmp[j]);
    }
    siz[u]+=siz[v];
    for(int i=0;i<=siz[u];i++)
      for(int j=0;j<=siz[u];j++)f[u][i][j]=t[i][j];
  }
  for(int i=0;i<siz[u];i++)
    for(int j=siz[u];j>=1;j--)
      gmax(f[u][i+1][j-1],f[u][i][j]);
  for(int i=0;i<=siz[u];i++)
    for(int j=0;j<=siz[u];j++)
      f[u][i][j]+=i;
}
void solve(){
  cin>>n>>m;
  for(int i=1;i<=n;i++)
    for(int j=0;j<=n;j++)for(int k=0;k<=n;k++)
      f[i][j][k]=-inf;
  for(int i=2;i<=n;i++)
    cin>>fa[i],G[fa[i]].push_back(i);
  dfs(1);
  ll ans=0;
  for(int i=0;i<=n;i++)
    for(int j=0;j<=n;j++)
      gmax(ans,f[1][i][j]);
  cout<<ans<<"\n";
  for(int i=1;i<=n;i++)G[i].clear();
}
int main(){
  // freopen("x.in","r",stdin);
  // freopen("x.out","w",stdout);
  ios::sync_with_stdio(0);
  cin.tie(nullptr);
  int TC;cin>>TC;while(TC--)solve();
  return 0;
}

解法2

解法一启发我们想单个点的贡献。
如果以取到 max⁡\max 的点为儿子进行剖分，uu 的贡献就是 uu 到根的路径上最长的连续链。
则问题变成了对树的剖分形态进行 dpdp，有状态 fu,i,jf_{u,i,j} 表示 uu 点目前处在的链长 jj，历史最长链长为 ii 的子树贡献，转移显然，是 3d−0d3d-0d 的，可以做到 O(nm2)O(nm^2) 拿到 7676 分。
nm2nm^2 CodeCPP
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N=8005;
const int M=805;
const ll inf=1e13;
int n,m,fa[N],dep[N],siz[N];
ll s[N][M];
vector<ll> f[N][M];
vector<int> G[N];
void dfs(int u){
  dep[u]=dep[fa[u]]+1,siz[u]=1;
  for(auto v:G[u]){
    dfs(v);siz[u]+=siz[v];
    for(int i=1;i<=m;i++)s[u][i]+=f[v][i][1];
  }
  for(int i=1;i<=m;i++)
    for(int j=1;j<=m;j++)
      f[u][i][j]=i*siz[u];
  for(auto v:G[u]){
    for(int i=1;i<=m;i++)
      for(int j=1;j<=m;j++)
        if(j+1<=m)f[u][i][j]=max(f[u][i][j],i+s[u][i]-f[v][i][1]+f[v][max(i,j+1)][j+1]);
  }
}
void solve(){
  cin>>n>>m;m++;
  memset(s,0,sizeof s);
  for(int i=1;i<=n;i++)
    for(int j=1;j<=m;j++)f[i][j].resize(m+1);
  for(int i=2;i<=n;i++)
    cin>>fa[i],G[fa[i]].push_back(i);
  dfs(1);
  cout<<f[1][1][1]<<"\n";
  for(int i=1;i<=n;i++)G[i].clear();
}
int main(){
  // freopen("x.in","r",stdin);
  // freopen("x.out","w",stdout);
  ios::sync_with_stdio(0);
  cin.tie(nullptr);
  int TC;cin>>TC;while(TC--)solve();
  return 0;
}

解法3

这个 dp 的贡献分为两部分，一部分是当前链贡献，一个是历史链贡献，于是只需要分别维护这两个即可。
设 Fu,i=fu,1,iF_{u,i}=f_{u,1,i}，Gu,i=fu,i,iG_{u,i}=f_{u,i,i}。
GG 的转移显然， FF 的转移需要求一个毛毛虫状物，用 dfs 序和树状数组简单维护即可。
AC CodeCPP
#include<bits/stdc++.h>
using namespace std;
#define ll int
#define lowbit(x) ((x)&(-x))
const int N=8005;
const int M=805;
int n,m,tim,dfn[N],siz[N],fa[N],dep[N];
ll F[N][M],G[N][M],sum[M],d[M];
vector<int> to[N][M],rG[N];
struct BIT{
  ll T[N];
  inline void init(){memset(T,0,sizeof T);}
  inline void add(int x,ll y){for(int i=x+1;i<N;i+=lowbit(i))T[i]+=y;}
  inline ll sum(int x){int res=0;for(int i=x+1;i;i^=lowbit(i))res+=T[i];return res;}
  inline ll qry(int l,int r){return sum(r)-sum(l-1);}
}B[M],S[M];//B是原点权值，S是儿子权值
inline void upd(int p,int x,ll y){
  B[p].add(dfn[x],y),B[p].add(dfn[x]+siz[x],-y);
  S[p].add(dfn[fa[x]],y),S[p].add(dfn[fa[x]]+siz[fa[x]],-y);
}
void dfs1(int u){
  dfn[u]=++tim,siz[u]=1,dep[u]=dep[fa[u]]+1;
  to[u][0].push_back(u);
  for(auto v:rG[u]){
    dfs1(v);
    siz[u]+=siz[v];
    for(int i=0;i<m;i++)
      for(auto s:to[v][i])to[u][i+1].push_back(s);
  }
}
void dfs2(int u){
  for(int i=1;i<=m;i++)F[u][i]=G[u][i]=siz[u]*i;
  for(auto v:rG[u])dfs2(v);
  //G的转移
  for(auto v:rG[u])
    for(int i=1;i<=dep[u]+1;i++)upd(i,v,F[v][i]);
  for(int i=1;i<=dep[u];i++)sum[i]=0;
  for(auto k:rG[u]){
    int v=k;
    for(int i=1;i<=dep[u];i++)sum[i]+=F[v][i];
  }
  for(auto k:rG[u]){
    int v=k;
    for(int i=1;i<=dep[u];i++)G[u][i]=max(G[u][i],i+sum[i]-F[v][i]+G[v][i+1]);
  }
  //F的转移
  for(int i=1;i<=dep[u];i++)
    for(auto k:to[u][i]){
      int v=k;
      F[u][i]=max(F[u][i],i*i+G[v][i+1]+S[i].sum(dfn[fa[v]])-B[i].sum(dfn[v]));
    }
}
void solve(){
  cin>>n>>m;m++,tim=0;
  for(int i=1;i<=m;i++)B[i].init(),S[i].init();
  for(int i=2;i<=n;i++)
    cin>>fa[i],rG[fa[i]].push_back(i);
  dfs1(1);dfs2(1);
  cout<<F[1][1]<<"\n";
  for(int i=1;i<=n;i++)rG[i].clear();
  for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)to[i][j].clear();
}
int main(){
  // freopen("x.in","r",stdin);
  // freopen("x.out","w",stdout);
  ios::sync_with_stdio(0);
  cin.tie(nullptr);
  int TC;cin>>TC;while(TC--)solve();
  return 0;
}
updated on 12.12: 提供了一份不卡常且更短的实现。
AC CodeCPP
#include<bits/stdc++.h>
using namespace std;
const int N=8005;
const int M=805;
int F[N][M],G[N][M],tmp[M],n,m;
int fa[N],dep[N],dfn[N],siz[N],tim;
vector<int> rG[N],to[N];
inline void gmax(int &x,int y){x=max(x,y);}
struct BIT{
  int t[M][N];
  void init(){memset(t,0,sizeof t);}
  inline int lowbit(int x){return x&-x;}
  inline void add(int p,int x,int y){for(int i=x;i<N;i+=lowbit(i))t[p][i]+=y;}
  inline int sum(int p,int x){int res=0;for(int i=x;i;i^=lowbit(i))res+=t[p][i];return res;}
}F1,F2;
void dfs(int u){
  dep[u]=dep[fa[u]]+1,siz[u]=1;
  dfn[u]=++tim,to[u].push_back(u);
  for(auto v:rG[u]){
    dfs(v),siz[u]+=siz[v];
    for(auto s:to[v])to[u].push_back(s);
  }
  for(int i=1;i<=m;i++)F[u][i]=G[u][i]=siz[u]*i,tmp[i]=0;
  for(auto v:rG[u]){
    for(int i=1;i<=dep[u];i++){
      tmp[i]+=F[v][i];
      F1.add(i,dfn[v],F[v][i]),F1.add(i,dfn[v]+siz[v],-F[v][i]);
      F2.add(i,dfn[u],F[v][i]),F2.add(i,dfn[u]+siz[u],-F[v][i]);
    }
  }
  for(auto v:rG[u])
    for(int i=1;i<=dep[u];i++)gmax(G[u][i],i+tmp[i]-F[v][i]+G[v][i+1]);
  for(auto v:to[u]){
    int dis=dep[v]-dep[u];
    if(v==u||dis>dep[u])continue;
    gmax(F[u][dis],dis*dis+G[v][dis+1]+F2.sum(dis,dfn[fa[v]])-F1.sum(dis,dfn[v]));
  }
}
void solve(){
  cin>>n>>m,m++,tim=0;
  for(int i=2;i<=n;i++)
    cin>>fa[i],rG[fa[i]].push_back(i);
  dfs(1);
  cout<<F[1][1]<<"\n";
  memset(F,0,sizeof F),memset(G,0,sizeof G);
  F1.init(),F2.init();
  for(int i=1;i<=n;i++)rG[i].clear(),to[i].clear();
}
int main(){
  ios::sync_with_stdio(0);
  cin.tie(nullptr);
  int TC;cin>>TC;while(TC--)solve();
  return 0;
}

D

启发性解法

性质 DE 启发我们使用分治，使用 ST 表简单维护前缀最大最小，求以每个点开头或结尾且越过分界点的最大值，贡献就是一个前缀或后缀最大物。

正解

发现以 2p2^p 为分界长度的分割性质，2p+1≤len≤2p+12^p+1\le len\le 2^{p+1} 的区间，其会跨过 11 到 22 个分界线，最优化问题可以算重，所以直接预处理所有即可。
对于询问，整块预处理，散块以下界减 11 作为分割大小直接跑一遍就行了，时间复杂度 O(nlog⁡2n+qn)O(n\log^2n+qn)。
AC CodeCPP
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
const int N=50005;
const ll inf=1e13;
int n,q,lg[N];
ll s[N],mx[N][18],mi[N][18],tmp[N],B[18][N],PL[20],PR[20],res[18][18][N],ans[N];
inline ll qry1(int l,int r){
  if(l>r)return -inf;
  int k=lg[r-l+1];
  return max(mx[l][k],mx[r-(1<<k)+1][k]);
}
inline ll qry2(int l,int r){
  if(l>r)return inf;
  int k=lg[r-l+1];
  return min(mi[l][k],mi[r-(1<<k)+1][k]);
}
void solve(int id,int lc,int rc){
  int len=PL[id]-1;
  for(int xmid=len;xmid<n;xmid+=len){
    int l=max(xmid-(len<<1)+1,1),r=min(xmid+(len<<1),n);
    tmp[l-1]=-inf;
    for(int i=l;i<=xmid;i++){
      tmp[i]=max(tmp[i-1],qry1(max(xmid+1,i+lc-1),min(r,i+rc-1))-s[i-1]);
      ans[i]=max(ans[i],tmp[i]);
    }
    tmp[r+1]=-inf;
    for(int i=r;i>xmid;i--){
      tmp[i]=max(tmp[i+1],s[i]-qry2(max(i-rc,l-1),min(i-lc,xmid-1)));
      ans[i]=max(ans[i],tmp[i]);
    }
  }
}
int main(){
  // freopen("x.in","r",stdin);
  // freopen("x.out","w",stdout);
  for(int i=2;i<N;i++)lg[i]=lg[i>>1]+1;
  cin>>n;
  for(int i=1;i<=n;i++)
    cin>>s[i],s[i]+=s[i-1],mi[i][0]=mx[i][0]=s[i];
  for(int j=1;j<=17;j++)for(int i=0;i<=n-(1<<j)+1;i++)
    mx[i][j]=max(mx[i][j-1],mx[i+(1<<(j-1))][j-1]),
    mi[i][j]=min(mi[i][j-1],mi[i+(1<<(j-1))][j-1]);
  for(int i=1;i<=n;i++)for(int j=0;j<18;j++)B[j][i]=-inf;
  for(int i=1;i<=n;i++)B[0][i]=s[i]-s[i-1];
  PL[0]=PR[0]=1;
  int c=1;
  for(int len=1;len<n;len<<=1,c++){
    int L=len+1,R=min(len<<1,n);
    PL[c]=L,PR[c]=R;
    for(int xmid=len;xmid<n;xmid+=len){
      int l=max(xmid-(len<<1)+1,1),r=min(xmid+(len<<1),n);
      tmp[l-1]=-inf;
      for(int i=l;i<=xmid;i++){
        tmp[i]=max(tmp[i-1],qry1(max(xmid+1,i+L-1),min(r,i+R-1))-s[i-1]);
        B[c][i]=max(B[c][i],tmp[i]);
      }
      tmp[r+1]=-inf;
      for(int i=r;i>xmid;i--){
        tmp[i]=max(tmp[i+1],s[i]-qry2(max(i-R,l-1),min(i-L,xmid-1)));
        B[c][i]=max(B[c][i],tmp[i]);
      }
    }
  }c--;
  for(int i=0;i<=c;i++){
    for(int j=1;j<=n;j++)tmp[j]=-inf;
    for(int j=i;j<=c;j++)
      for(int k=1;k<=n;k++)tmp[k]=res[i][j][k]=max(tmp[k],B[j][k]);
  }
  int q;cin>>q;
  while(q--){
    ll l,r;
    cin>>l>>r;
    int LL=-1,RR=-1;
    for(int i=0;i<=c;i++){
      if(PL[i]>=l&&PR[i]<=r){
        if(LL==-1)LL=i;
        RR=i;
      }
    }
    if(~LL)for(int i=1;i<=n;i++)ans[i]=res[LL][RR][i];
    else for(int i=1;i<=n;i++)ans[i]=-inf;
    for(int i=0;i<=c;i++){
      int p=min(PR[i],r)-max(PL[i],l);
      if(p>=0&&p!=PR[i]-PL[i])
        solve(i,max(PL[i],l),min(PR[i],r));
    }
    ull num=0;
    for(int i=1;i<=n;i++)num^=(ull)ans[i]*i;
    cout<<num<<"\n";
  }
  return 0;
}

评论

共 3 条评论，欢迎与作者交流。

正在加载评论...