daily 2

一道dp一道智力题

CF 404D

void solve(){
  string s;
  cin>>s;
  int n=s.size();
  s=')'+s;
  vector dp(n+1,vector<int>(5));//0:itself is a minner, 1:only left has a minner 2:only right has a minner 3:left and right both have miners 4:non of them has a miner
  dp[0][4]=dp[0][2]=1;
  bool able=false;
  for(int i=1;i<=n;++i){
    able=s[i]=='?';
    if(able||s[i]=='*'){
        dp[i][0]=(dp[i][0]+dp[i-1][0])%MOD;
        dp[i][0]=(dp[i][0]+dp[i-1][2])%MOD;
        dp[i][0]=(dp[i][0]+dp[i-1][3])%MOD;
    }
    if(able||s[i]=='0'){
        dp[i][4]=(dp[i][4]+dp[i-1][1])%MOD;
        dp[i][4]=(dp[i][4]+dp[i-1][4])%MOD;
    }
    if(able||s[i]=='1'){
        dp[i][1]=(dp[i][1]+dp[i-1][0])%MOD;
        dp[i][2]=(dp[i][2]+dp[i-1][4])%MOD;
        dp[i][2]=(dp[i][2]+dp[i-1][1])%MOD;
    }
    if(able||s[i]=='2'){
        dp[i][3]=(dp[i][3]+dp[i-1][0])%MOD;
    }
  }
  ll ans=0;
  able=s[n]=='?';
  if(able||s[n]=='*')ans=(ans+dp[n][0])%MOD;
  if(able||s[n]=='0')ans=(ans+dp[n][4])%MOD;
  if(able||s[n]=='1')ans=(ans+dp[n][1])%MOD;
  cout<<ans<<'\n';
  return;
}

CF 351A

void solve(){
  int n;
  cin>>n;
  double sum=0;
  int cnt=0;
  vector<double>a(2*n+1);
  for(int i=1;i<=2*n;++i){
    cin>>a[i];
    sum+=a[i]-floor(a[i]);
    if(a[i]-floor(a[i])<eps){
        ++cnt;
    }
  }
  double ans=6e10;
  for(int i=n;i>=n-cnt;--i){
    ans=min(ans,fabs(i-sum));
  }
  cout << setiosflags(ios::fixed) << setprecision(3) << ans << endl;
  return;
}