发布时间：2024-02-21

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即为这些数字的总贡献,即 $[l*45+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";
}