dp practice day 7

三道大水题，选的太成功惹！
01背包+树形dp+combo

CF 687C
类似01背包的格式，给你一堆硬币，问你在能组成k的条件下还能组成一些其他什么别的数
类似01背包的转移
dp[i][j]表示在能够组成i的时候，能否组成j

$dp[i+a[k]][j]=d[i+a[k]][j+a[k]]=(dp[i][j]==1)$

void solve(){
  int n,k;
  cin>>n>>k;
  vector<int>a(n+1);
  for(int i=1;i<=n;++i)cin>>a[i];
  vector dp(k+1,vector<int>(k+1));
  dp[0][0]=1;
  for(int i=0;i<=n;++i){
    for(int v1=k;v1>=0;--v1){
        for(int v2=k;v2>=0;--v2){
            if(dp[v1][v2]&&v1+a[i]<=k){
                dp[v1+a[i]][v2]=dp[v1+a[i]][v2+a[i]]=1;
            }
        }
    }
  }
  vector<int>ans;
  for(int i=0;i<=k;++i){
    if(dp[k][i]){
        ans.push_back(i);
    }
  }
  cout<<ans.size()<<'\n';
  for(int i=0;i<ans.size();++i){
    cout<<ans[i]<<" \n"[i==ans.size()-1];
  }
  return;
}

CF 685B

树形dp，首先我们可以先把每棵树的重儿子求出来(dfs)
之后了解一个性质，一颗树的重心总在重儿子的重心和根的路径上
所以我们只需要从重儿子的重心开始向上爬，就能够找到重心惹

void solve(){
  int n,q;cin>>n>>q;
  vector<int>fa(n+1),ans(n+1),hson(n+1),siz(n+1);
  vector<vector<int>>E(n+1);
  for(int i=2;i<=n;++i){
    int x;cin>>x;
    E[x].push_back(i);
    fa[i]=x;
  }
  function<void(int)>dfs1=[&](int now){
    siz[now]=1;
    for(int v:E[now]){
        dfs1(v);
        siz[now]+=siz[v];
        if(siz[v]>siz[hson[now]]){
            hson[now]=v;
        }
    }
  };
  function<void(int)>dfs2=[&](int now){
    if(!hson[now]){
        ans[now]=now;
        return;
    }
    for(int v:E[now]){
        dfs2(v);
    }
    if(2*siz[hson[now]]<=siz[now]){
        ans[now]=now;
    }
    else{
        for(int v=ans[hson[now]];v!=now;v=fa[v]){
            if(max(siz[hson[v]],siz[now]-siz[v])*2<=siz[now]){
                ans[now]=v;
                break;
            }
        }
    }
  };
  dfs1(1);
  dfs2(1);
  while(q--){
    int v;cin>>v;
    cout<<ans[v]<<'\n';
  }
  return;
}

CF 689E
给你一堆区间，让你每次选k个，问能够每次选k个的区间和的和为多少

首先考虑对于一个元素来说，如果有cnt个区间选中了他，那么他的贡献为${C_{cnt}^k}$ 知道这个了之后，就类似滑动窗口每次去取就好了

ll quick_pow(ll x,ll exp,int p)
{
      ll ans=1;
      while(exp)
      {
        if(exp&1)ans=ans*x%p;
        exp>>=1;
        x=x*x%p;
      }
      return ans;
}
ll inv[MAXN],fac[MAXN];
void init(int n,int p)
{
  memset(inv,0,sizeof(inv));
  memset(fac,0,sizeof(fac));
  inv[0]=fac[0]=1;
  for(int i=1;i<=n;++i)
  {
    fac[i]=fac[i-1]*i%p;
  }
  inv[n]=quick_pow(fac[n],p-2,p)%p;
  for(int i=n;i>=1;--i)inv[i-1]=inv[i]*i%p;
}
ll C(ll n,ll m,ll p)
{
  if(m>n||m<0)return 0;
  return fac[n]*inv[n-m]%p*inv[m]%p;
}
void solve(){
  int n,k;cin>>n>>k;
  using pii=pair<int,int>;
  vector<pii>vec;
  for(int i=1;i<=n;++i){
    int l,r;
    cin>>l>>r;
    vec.push_back({l-1,1});
    vec.push_back({r,-1});
  }
  sort(vec.begin(),vec.end());
  ll cnt=0,ans=0,left=-1;
  for(auto pi:vec){
    ans=(ans+C(cnt,k,MOD)*(pi.first-left))%MOD;
    left=pi.first;
    cnt+=pi.second;
  }
  cout<<ans<<'\n';
  return;
}

OK,今天的水题完成惹，开始写OS的复习惹