daily 3

2023/3/26 daily Codeforces dp

今天腾讯笔试做的有点差，还好不影响，刚刚做完题了去健个身然后背八股了

CF 254 C

思维题

首先我们可以统计出每个字符在s和t中分别出现了多少次，然后我们遍历s，每次找到对应cnt1[x]>cnt2[x]的位置，因为这个位置肯定需要变化，然后我们遍历26个字母，这里有一个技巧，如果你正好可以发现现在就可以替换的(j<x且cnt1[j]<cnt2[j])那么肯定要直接修改，但是如果你对应的cnt2[x]的位置=0，这表示在t中不需要当前元素，那么也要修改。其余的情况表明t中需要x这个元素，那么我们就之后再改

void solve(){
  string s,t;
  cin>>s>>t;
  //we need to find those places that cnt1[s[i]]>cnt2[s[i]],then transform them
  vector<int>cnt1(26),cnt2(26);
  for(int i=0;i<s.size();++i){
    cnt1[s[i]-'A']++;
    cnt2[t[i]-'A']++;
  }
  int ans=0;
  for(int i=0;i<s.size();++i){
    int x=s[i]-'A';
    if(cnt1[x]>cnt2[x]){
      for(int j=0;j<26;++j){
        if(cnt1[j]<cnt2[j]){
          if(j<x||!cnt2[x]){
            cnt2[j]--;
            s[i]=j+'A';
            ++ans;
          }else{
            cnt2[x]--;
          }
          break;
        }
      }
      cnt1[x]--;//subtract it in s
    }
  }
  cout<<ans<<'\n'<<s<<'\n';
  return;
}

CF 9D

思维+dp

另使用i个节点且树的高度小于j的答案数为dp[i][j]

那么转移方程很好写

dp[i][j]+=dp[left][j-1]*dp[i-left-1][j-1];
分别枚举i,left,j就好了

void solve(){
  int n,h;
  cin>>n>>h;
  vector dp(n+1,vector<ll>(n+1));//dp[i][j] means using i nodes and the depth is less than j
  for(int height=1;height<=n;++height){
    dp[0][height-1]=1;
    for(int total_nodes=1;total_nodes<=n;++total_nodes){
        for(int left=0;left<total_nodes;++left){//number of left nodes
            dp[total_nodes][height]+=dp[left][height-1]*dp[total_nodes-left-1][height-1];
        }
    }
  }
  cout<<dp[n][n]-dp[n][h-1]<<'\n';
  return;
}

CF 1117D

首先可以容易写出转移方程

dp[i]=dp[i-1]+dp[i-m]

然后用矩阵快速幂优化就好啦

ll n,m;
struct Mat{
    ll mat[110][110];
    Mat(){};
    Mat operator*(Mat const &b)const
    {
        Mat res;
        memset(res.mat,0,sizeof(res.mat));
        for(int k=0;k<m;++k)
           for(int i=0;i<m;++i)
               for(int j=0;j<m;++j)
                  res.mat[i][j]=(res.mat[i][j]+(this->mat[i][k]*b.mat[k][j]))%MOD;
        return res;    
    }
};
Mat mat_pow(Mat A,ll k){
    Mat res;
    memset(res.mat,0,sizeof(res.mat));
    for(int i=0;i<m;++i)
        res.mat[i][i]=1;
    while(k>0)
    {
        if(k&1)res=res*A;
        A=A*A;
        k=k>>1;
    }
    return res;
}
void solve(){
  cin>>n>>m;
  if(n<m){
    cout<<1<<'\n';
    return;
  }
  Mat base,A;
  A.mat[0][0]=A.mat[0][m-1]=1;
  for(int i=1;i<m;++i)A.mat[i][i-1]=1;
  for(int i=0;i<m;++i)base.mat[i][0]=1;
  A=mat_pow(A,n-m+1);
  base=A*base;
  cout<<base.mat[0][0]<<'\n';
  return;
}

感觉自己还是好👎，哎，真的感觉没有自己的容身之所了，下去锻炼一下，回来继续背八股吧

LOADING

daily 3