daily 3

今天阿里下书面offer了，全心等鹅中

做了3道背包，明天复习一下背包和状压

CF 837D

给你一堆数，求乘积中0的数量最多的数，set的大小为k

几个数相乘之后的数的0的个数取决于2和5的因数的数量
先处理出来，然后
$dp[i][j][k]$表示前i个数中选择了j个数，且5的数量为k,2的数量为dp[i][j][k],转移就很清楚了

void solve(){
  int n,k;
  cin>>n>>k;
  vector<ll>num(n+1),fac5(n+1),fac2(n+1);
  for(int i=1;i<=n;++i){
    cin>>num[i];
    ll& x=num[i];
    while(x%5==0){
        fac5[i]++;
        x/=5;
    }
    while(x%2==0){
        fac2[i]++;
        x/=2;
    }
  }
  vector dp(n+1,vector<ll>(N,-INF));
  dp[0][0]=0;
  for(int i=1;i<=n;++i){
    for(int j=k;j>=1;--j){
        for(int l=N-1;l>=fac5[i];--l){
            if(num[i]){
                dp[j][l]=max(dp[j-1][l-fac5[i]]+fac2[i],dp[j][l]);
            }
        }
    }
  }
  ll ans=0;
  for(ll i=0;i<N;++i){
    ans=max(ans,min(i,dp[k][i]));
  }
  cout<<ans<<'\n';
  return;
}

CF 755F

首先我们可以发现（指看了题解发现）原关系可以形成很多不同大小的环，那么对于奇数长度的环，我们可以减少${(len/2)+1}$个元素来让之中每个人都没法获得礼物，对于偶数长度的环,这个值则是${len/2}$,那么，我们可以直接01背包开始选喽，但是这样会超时，正确的做法是把每个长度相同的环做成状态压缩之后再选即可

void solve(){
  int n,k;
  cin>>n>>k;
  vector<int>vis(n+1),a(vis),num(vis),lens(vis),v(vis);//num: number of rings that has length i,lens: length of i ring
  int cnt=0;//count of total rings;(distinct size)
  for(int i=1;i<=n;++i)cin>>a[i];
  for(int i=1;i<=n;++i){
    int now=i,len=0;
    while(!vis[now]){
        vis[now]=1;
        ++len;
        now=a[now];
    }
    if(num[len])num[len]++;
    else num[len]=1,lens[++cnt]=len;
  }
  ll ans=0;
  for(int i=1;i<=cnt;++i){
    ans+=lens[i]/2*num[lens[i]];
  }
  if(ans>=k){
    ans=k*2;
  }else{
    ans+=k;
  }
  ans=min(ans,(ll)n);
  int tot=0;
  for(int i=1;i<=cnt;++i){
    for(int j=1;j<=num[lens[i]];j<<=1){
        v[++tot]=j*lens[i];
        num[lens[i]]-=j;
    }
    if(num[lens[i]]){
        v[++tot]=num[lens[i]]*lens[i];
    }
  }
  bitset<N>dp;
  dp.set(0);
  for(int i=1;i<=tot;++i){
    dp|=(dp<<v[i]);
  }
  if(dp.test(k)){
    cout<<k<<' '<<ans<<'\n';
  }else{
    cout<<k+1<<' '<<ans<<'\n';
  }
  return;
}

CF 510D

一开始也没想出来，看题解了之后发现只要选择的数gcd=1就可以了。。。感觉自己好傻逼，那么用map优化一下空间复杂度就好了

int gcd(int a,int b){return b?gcd(b,a%b):a;}
void solve(){
  int n;cin>>n;
  vector<int>l(n),c(n);
  for(int i=0;i<n;++i)cin>>l[i];
  for(int i=0;i<n;++i)cin>>c[i];
  map<int,int>dp;
  dp[0]=0;
  for(int i=0;i<n;++i){
    for(auto& k:dp){
        int tmp=gcd(l[i],k.first);
        if(dp[tmp]!=0){
            dp[tmp]=min(dp[tmp],k.second+c[i]);
        }else{
            dp[tmp]=k.second+c[i];
        }
    }
  }
  cout<<(dp.count(1)?dp[1]:-1)<<'\n';
  return;
}