daily 2

CF 245H

给你q个query，求每个query中回文串的数量

容斥+预处理

${dp[i][j]=dp[i+1][j]+dp[i][j-1]-dp[i+1][j-1]+s[i..j] is a pad}$

void solve(){
  string s;
  cin>>s;
  int n=s.size();
  s='*'+s+'*'+'#';
  vector dp(n+2,vector<int>(n+2));
  vector pad(n+2,vector<int>(n+2,-1));
  function<int(int,int)>dfs=[&](int l,int r){
      if(pad[l][r]!=-1)return pad[l][r];
      if(s[l]!=s[r])return 0;
      pad[l+1][r-1]=dfs(l+1,r-1);
      return pad[l+1][r-1];
  };
  for(int i=1;i<=n;++i){
    dp[i][i+1]=(s[i]==s[i+1])+2;
    dp[i][i]=1;
    pad[i][i]=dp[i][i];
    pad[i][i+1]=(dp[i][i+1]==3);
  }
  //dp[i][j]=dp[i+1][j]+dp[i][j-1]-dp[i+1][j-1]+s[i..j]==pad
  for(int len=3;len<=n;++len){
    for(int l=1;l+len-1<=n;++l){
      int r=l+len-1;
      pad[l][r]=dfs(l,r);
      dp[l][r]=dp[l+1][r]+dp[l][r-1]-dp[l+1][r-1]+pad[l][r];
    }
  }
  int q;
  cin>>q;
  while(q--){
    int l,r;
    cin>>l>>r;
    cout<<dp[l][r]<<'\n';
  }
  return;
}

CF 509C

智力题（我的智力很低）一道

我们实现一个find方法，用于获得把当前的dif给最小化到0的时候，对应的digit数组

由于我们需要升序的a数组，首先我们看${b[i]-b[i-1]}$，如果这个值>0那么，那么我们直接调用find方法去找到对应的digits

如果这个值<0,那我们首先从个位开始累加，然后把后面适当的位置+1，再调用find即可

void solve(){
  int n;cin>>n;
  vector<int>b(n+1);
  for(int i=1;i<=n;++i)cin>>b[i];
  vector<int>digit(N);
  int len=1;
  function<void(int)>find=[&](int dif){
    for(int i=1;dif;++i){
      if(i>len){
        len=i;
      }
      while(dif&&digit[i]<9){
        --dif;
        ++digit[i];
      }
    }
  };
  for(int i=1;i<=n;++i){
    int dif=b[i]-b[i-1];
    if(dif>0){
      find(dif);
    }else{
      for(int j=1;;++j){
        if(j>len)len=j;
        if(dif>0&&digit[j]<9){
          dif--;
          digit[j]++;
          find(dif);
          break;
        }
        dif+=digit[j];
        digit[j]=0;
      }
    }
    for(int j=len;j>=1;--j){
      cout<<digit[j];
    }
    cout<<'\n';
  }
  return;
}