daily 2

今天水了两题，明天终于要变正常了

CF 349B

构造题

我们先把最大的位数给整出来，然后如果每次遍历剩下的位，如果能够达到对应的位数并且有多余的颜料那么接涂这个色

void solve(){
  int v;cin>>v;
  vector<int>a(10);
  int minx=1e9;
  for(int i=0;i<9;++i){
    cin>>a[i];
    minx=min(a[i],minx);
  }
  int cnt=v/minx;
  if(!cnt){
    cout<<-1<<'\n';
    return;
  }
  while(cnt--){
    int pick=-1;
    for(int i=8;i>=0;--i){
        if((v-a[i])/minx==cnt&&v>=a[i]){
            cout<<(i+1);
            pick=i;
            break;
        }
    }
    v-=a[pick];
  }
  return;
}

CF 351B

概率dp

${dp[i]}$表示消除i对逆序对所需的操作数

${dp[i]=dp[i-2]0.5+2+dp[i]0.5}$

void solve(){
  int n;
  cin>>n;
  vector<int>a(n);
  for(int i=0;i<n;++i)cin>>a[i];
  int cnt=0;
  for(int i=1;i<n;++i){
    for(int j=0;j<i;++j){
        if(a[j]>a[i]){
            ++cnt;
        }
    }
  }
  double ans=0;
  if(cnt&1){
    ans=2*cnt-1;
  }else{
    ans=2*cnt;
  }
  //dp[i]=0.5dp[i-2]+0.5*dp[i]+2;
  printf("%.6f",ans);
  return;
}