dp practice day 8

CF 837B

简单dp，记录一下[1..i]区间内的0和1的数量关系，然后用map记录dp值，存在相同的dp值的话就可以获得一个答案

void solve(){
  int n;cin>>n;
  string s;cin>>s;
  vector<int>dp(n+1,0);
  for(int i=1;i<=n;++i){
    if(s[i-1]=='1'){
        dp[i]=dp[i-1]+1;
    }else{
        dp[i]=dp[i-1]-1;
    }
  }
  map<int,int>mp;
  mp[0]=0;
  int ans=0;
  for(int i=1;i<=n;++i){
    if(mp.count(dp[i])){
        ans=max(ans,i-mp[dp[i]]);
    }else{
        mp[dp[i]]=i;
    }
  }
  cout<<ans<<'\n';
  return;
}

CF 869C

不会做，看的题解，首先同色的肯定不能连边，其次两个相同颜色的点不能和同一个点相连，所以就只能两两相连，两两计算后把答案想乘即可

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(){
  ll a,b,c;cin>>a>>b>>c;
  ll ans=1;
  auto calc=[&](ll x,ll y){
    ll minx=min(x,y);
    ll res=0;
    for(int i=0;i<=minx;++i){
        res=(res+C(x,i,MOD)*C(y,i,MOD)%MOD*fac[i]%MOD)%MOD;
    }
    return res;
  };
  ans=(ans*calc(a,b))%MOD;
  ans=(ans*calc(b,c))%MOD;
  ans=(ans*calc(a,c))%MOD;
  cout<<ans<<'\n';
  return;
}

CF 864E

带有时间的01背包，我们可以先按照销毁时间进行排序，然后按照01背包的去做，注意最后获得解集的时候需要从0-2000进行遍历，这是因为时间改变了我们的背包大小

struct node{
    int t,d,v,id;
};
void solve(){
  int n;cin>>n;
  vector<node>a(n+1);
  for(int i=1;i<=n;++i){
    cin>>a[i].t>>a[i].d>>a[i].v;
    a[i].id=i;
  }
  sort(a.begin()+1,a.end(),[&](node a,node b){
    return a.d<b.d;
  });
  vector<vector<int>>st(2001);
  vector<int>dp(2001);
  for(int i=1;i<=n;++i){
    int d=a[i].d,v=a[i].v,id=a[i].id,t=a[i].t;
    for(int j=d-1;j>=t;--j){
        if(dp[j]<dp[j-t]+v){
            dp[j]=dp[j-t]+v;
            st[j]=st[j-t];
            st[j].push_back(id);
        }
    }
  }
  int ans=0;
  for(int i=0;i<=2000;++i){
    if(dp[i]>dp[ans]){
        ans=i;
    }
  }
  cout<<dp[ans]<<'\n';
  cout<<st[ans].size()<<'\n';
  for(int i=0;i<st[ans].size();++i){
    cout<<st[ans][i]<<' ';
  }
  cout<<'\n';
  return;
}

明天要考试了，最近投了很多份国内建立，希望能够有好结果