daily 2

CF 758D

简单的DP策略，就是最后一位用多少+一个溢出判断 ${log(dp[i-k][j-1])+log(n)-log(INF-cur_val)<=EPS}$

void solve(){
  ll n;
  cin>>n;
  string s;
  cin>>s;
  int m=s.size();
  vector dp(m+1,vector<ll>(m+1));
  for(int i=1;i<=m;++i){
    for(int j=1;j<=i;++j){
      dp[i][j]=INF;
    }
  }
  s='0'+s;
  for(ll i=1;i<=m;++i){
    for(ll j=1;j<=i;++j){
      ll cur_val=0,base=1;
      for(ll k=1;i-k>=j-1;++k){
        cur_val+=((ll)(s[i-k+1]-'0'))*base;
        if(cur_val>=n||base>=n){
          break;
        }
        base*=10;
        if(j==1&&k!=i){
          continue;
        }
        if(!(s[i-k+1]-'0'==0&&k!=1)){
          if(log(dp[i-k][j-1])+log(n)-log(INF-cur_val)<=EPS){
            dp[i][j]=min(dp[i][j],dp[i-k][j-1]*n+cur_val);
          }
        }
      }
    }
  }
  cout<<*min_element(dp[m].begin()+1,dp[m].begin()+m+1)<<'\n';
  return;
}

CF 822D

nlogn卡过～～～～

void solve(){
  ll t,l,r;
  cin>>t>>l>>r;
  vector dp(MAXM,INF);
  dp[1]=0;
  for(int i=1;i<=r;++i){
    for(int j=2;j*i<=r;++j){
        dp[i*j]=min(dp[i*j],dp[i]+1ll*j*i*(j-1)/2);
    }
  }
  ll ans=0;
  ll base=1;
  for(int i=l;i<=r;++i){
    ans=(ans+base*(dp[i]%MOD))%MOD;
    base=base*t%MOD;
  }
  cout<<ans<<'\n';
  return;
}