daily 2

CF 909C

let ${dp[i][j]}$ represent the answer of the first i line with j indentation. so we have the following two options

first, if ${a[i-1]}==f$ then we should let ${dp[i][j]=dp[i-1][j-1]}$ since we could only add the current line to previous ${f}$

second, if ${a[i-1]==s}$ then we could add it to whatever indentation we want, so ${dp[i][j]=\sum_{k=j}^{n-1}dp[i][k]}$ we could optimize the right side to ${dp[i][j+1]+dp[i-1][j]}$
and the answer cum out.

void solve(){
  int n;
  cin>>n;
  vector<int>a(n+1);
  for(int i=1;i<=n;++i){
    char c;
    cin>>c;
    a[i]=(c=='f');
  }
  vector dp(n+3,vector<ll>(n+3));
  dp[0][0]=1;
  for(int i=1;i<=n;++i){
    if(a[i-1]){
        for(int j=1;j<n;++j){
            dp[i][j]=dp[i-1][j-1];
        }
    }else{
        for(int j=i-1;j>=0;--j){
            dp[i][j]=(dp[i][j+1]+dp[i-1][j])%MOD;
        }
    }
  }
  ll ans=0;
  for(int i=0;i<n;++i){
    ans=(ans+dp[n][i])%MOD;
  }
  cout<<ans<<'\n';
  return;
}

CF 909E

Clearly, it is a top sort problem, we could use two queue indicate the main process queue and the copeocessor queue. and do the following.

void solve(){
  int n,m;
  cin>>n>>m;
  vector<int>a(n+1),deg(n+1);
  vector<vector<int>>E(n+1);

  for(int i=1;i<=n;++i)cin>>a[i];
  for(int i=1;i<=m;++i){
    int u,v;
    cin>>u>>v;
    ++u,++v;
    E[v].push_back(u);
    deg[u]++;
  }
  queue<int>qmain,qco;
  for(int i=1;i<=n;++i){
    if(!deg[i]){
        if(!a[i]){
            qmain.push(i);
        }else{
            qco.push(i);
        }
    }
  }
  int ans=0;
  while(!qmain.empty()||!qco.empty()){
    while(!qmain.empty()){
        auto cur=qmain.front();
        qmain.pop();
        for(int v:E[cur]){
            --deg[v];
            if(!deg[v]){
                if(!a[v]){
                    qmain.push(v);
                }else{
                    qco.push(v);
                }
            }
        }
    }
    if(!qco.empty()){
        ++ans;
    }
    while(!qco.empty()){
        auto cur=qco.front();
        qco.pop();
        for(int v:E[cur]){
            --deg[v];
            if(!deg[v]){
                if(!a[v]){
                    qmain.push(v);
                }else{
                    qco.push(v);
                }
            }
        }
    }
  }
  cout<<ans<<'\n';
  return;
}