NOIP2025补题笔记

Staque · 2025-12-07 10:26:44 · 算法·理论

越菜越练。

A

一眼贪，注意到整组的买一定只买 x+y 最小的那一组。

对于只买 x 的，排序然后枚举前缀和即可。

::::success[AC Code]

#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=2 启示了我们什么？

如果第一个是 w_x=1，后面被卡住的第一个 w_y=2，买的最后一个是 w_z=1，满足 a_z+a_x<a_y 则会爆炸。

正解

扩展到整体。

已经花了 m-1，然后第一个被卡住的是 u，最后买下的是 v，则如果前面买的存在一个 x，满足 w_x=1 且 a_v+a_x<a_u 则不优。

因此容斥算不合法方案。

枚举 u，我们可以将其划分为三个部分。

分别称为 A，B，C。

可以证明 v 一定在 C 中。

在 C 中枚举 v。

此时可以确定可能会使策略爆炸的部分，满足 a_i<a_u-a_v，记为 D。

如何使 A 和 B 中在前考虑的部分满足 \sum w_i=m-1？

所以答案就出来了。

完结。

::::success[AC Code]

#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

首先有个暴力 dp。

设 f_{u,i,j} 为 u 点及其子树 \operatorname{mex}=i，由 j 个点权 \ge i。

有树上背包做法，具体的，一维钦定最大值，一维背包转移，然后从后往前递推即可做到 O(n^3)，有 48 分

::::success[n^3 Code]

#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 的点为儿子进行剖分，u 的贡献就是 u 到根的路径上最长的连续链。

则问题变成了对树的剖分形态进行 dp，有状态 f_{u,i,j} 表示 u 点目前处在的链长 j，历史最长链长为 i 的子树贡献，转移显然，是 3d-0d 的，可以做到 O(nm^2) 拿到 76 分。

::::success[nm^2 Code]

#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 的贡献分为两部分，一部分是当前链贡献，一个是历史链贡献，于是只需要分别维护这两个即可。

设 F_{u,i}=f_{u,1,i}，G_{u,i}=f_{u,i,i}。