CF1926(div4)题解

C - Vlad and a Sum of Sum of Digits

题意：
$ 一个数n的贡献为n的数位和 $
$ 给定一个数n,求1 ~\ n的所有数的贡献,每个样例限制0.5s $

思路：

• 预处理每个答案，$ O(1) $ 查询
  • 一个数的贡献为 $ f_i=f_{i/10}+i \%\ 10 ,求出前缀和即可，时间复杂度O(n) $
  • 暴力计算，时间复杂度 $ O(nlogn) $

    int f[N],g[N];
    void init(){
      for(int i=1;i<=200000;i++){
      f[i]=f[i/10]+i%10;
      g[i]=g[i-1]+f[i];
      }
    }
    void solve(){
      int n;
      cin>>n;
      cout<<g[n]<<"\n";
    }
    

    第二种方法：赛时想多了的做法，每个样例复杂度 $ O(logn) $
    枚举每一位数字，每次将n分成 $ l+x+r $ 的形式,l为该数位左边的数，r为右边，x为数位本身

• 0-9均出现了l次，1~(x-1)出现多一次,这些出现的次数pow即为这些数字的总贡献,即 $ [l45+x(x-1)/2]pow $
• 当前数位x的贡献还要加上r+1次

  void solve(){
    int n;
    cin>>n;
    ll res=0;
    ll ans=0;
    ll num=1;
    int nn=n;
    while(nn){
        int x=nn%10;
        ll l=n/(num*10);
        ll r=num==1?0:n%num;
        res+=(l*45+x*(x-1)/2)*num+x*(r+1);
        nn/=10;
        num*=10;
    }
    cout<<res<<"\n";
  }
  

  F - Vlad and Avoiding X

  题意：
  给定一个7x7的方针，有黑白两种方针，不允许出现黑色叉(自身，左上，左下，右上，右下为黑色)的最小改变次数

思路：

• 暴力dfs，从左到右，从上到下枚举左上端点为黑色的点，如果存在叉，则任意改变一个黑色，继续向前移动，时间复杂度 $ O(5^{5 \times 5}) $(最多枚举5*5面积，每个点修改5次)，过大，考虑优化
• 发现对角线上不同的奇偶互不影响，因此可以分开操作，时间复杂度变为 $ O(5^{13}+5^{12}) $大大降低了复杂度
• 可以发现修改当前点只能改变当前的叉，修改其他点能改变至少两个叉，因此可以不用修改当前点，复杂度降为 $ O(4^{13}+4^{12}) $

  char a[10][10];
  void solve(){
    for(int i=1;i<=7;i++){
        for(int j=1;j<=7;j++)cin>>a[i][j];
    }
    int ans=0;
    for(int p=0;p<2;p++){
        int res=100;
        function<void(int,int,int)> dfs=[&](int x,int y,int z){
            if(x==6){
                res=min(res,z);
                return;
            }
            if(y==6){
                dfs(x+1,1,z);
                return;
            }
            if((x+y)%2!=p){
                dfs(x,y+1,z);
                return;
            }
            if(a[x][y]=='B'&&a[x+1][y+1]=='B'&&a[x+2][y]=='B'&&a[x+2][y+2]=='B'&&a[x][y+2]=='B'){
                a[x+1][y+1]='W';
                dfs(x,y+1,z+1);
                a[x+1][y+1]='B';
                a[x+2][y+2]='W';
                dfs(x,y+1,z+1);
                a[x+2][y+2]='B';
                a[x+2][y]='W';
                dfs(x,y+1,z+1);
                a[x+2][y]='B';
                a[x][y+2]='W';
                dfs(x,y+1,z+1);
                a[x][y+2]='B';
                return;
            }
            dfs(x,y+1,z);
        };
        dfs(1,1,0);
        ans+=res;
    }
    cout<<ans<<"\n";
  }
  

  G - Vlad and Trouble at MIT(树形dp)

  题意：
  有三种人，P在演奏音乐,C不在乎，S在睡觉,一棵树，问最少需要多少块隔板将P和S分离 思路：
  忽略C，将两种人看作红蓝两种液体，即不让二者混合
  从下往上dp， $ dp_{i,0}表示在i处只允许S通过，dp_{i,1}表示只允许P通过 $

• 初始化
  • $ s_i=S,dp_{i,0}=0,dp_{i,1}=inf $
  • $ s_i=P,dp_{i,1}=0,dp_{i,0}=inf $
• 转移
  • $ dp_{i,0}+=min(dp_{v,0},dp_{v,1}+1) $
  • $ dp_{i,1}+=min(dp_{v,1},dp_{v,0}+1) $

    void solve(){
      int n;
      cin>>n;
      vector<int> adj[n+1];
      for(int i=2;i<=n;i++){
      int x;
      cin>>x;
      adj[x].push_back(i);
      adj[i].push_back(x);
      }
      string s;
      cin>>s;
      s=" "+s;
      vector<vector<ll>> dp(n+1,vector<ll>(2));//0表示允许睡觉通过，1表示允许音乐通过
      function<void(int,int)> dfs=[&](int u,int fa){
      if(s[u]!='P')dp[u][0]=0;
      else dp[u][0]=INF;
      if(s[u]!='S')dp[u][1]=0;
      else dp[u][1]=INF;
      for(auto v:adj[u]){
          if(v==fa)continue;
          dfs(v,u);
          dp[u][0]=dp[u][0]+min(dp[v][0],dp[v][1]+1);
          dp[u][1]=dp[u][1]+min(dp[v][1],dp[v][0]+1);
      }
      };
      dfs(1,0);
      cout<<min(dp[1][0],dp[1][1])<<"\n";
    }