牛客周赛132

C

a[i] = 1 是一定会被修改的，如果a[i] != 1, 修改a[i] = a[i-1] * a[i+1],那a[i+1]就不用修改了

因此，如果gcd(a[i], a[i-1]) = 1, 状态的转移方程就为

$dp[i] = \begin{cases} dp[i-1] + 1 & a[i] = 1 \\ dp[i-2] + 1 & a[i] \neq 1 \end{cases}$

如果gcd(a[i], a[i-1]) > 1, dp[i] = dp[i-1].

void solve() {
    int n;
    cin >> n;

    vector<int> a(n+10);
    for(int i = 1;i <= n; i++) cin >> a[i];
    vector<int> dp(n+10);
    if(a[1] == 1) dp[1] = 1;
    for(int i = 2;i <= n; i++){
        if(a[i] != 1){
            if(__gcd(a[i], a[i-1]) == 1){
                dp[i] = dp[i-2] + 1;
            }else{
                dp[i] = dp[i-1];
            }
        }else{
            dp[i] = dp[i-1] + 1;
        }
    }
    cout << dp[n] << "\n";
}

D

求 $H(a) = \sum_{i=1}^n\sum_{j=i+1}^n\left\lfloor \frac{a_i + a_j}{2}\right\rfloor$

会发现a[i]与a[j]奇偶性不一样时，他们的平均值相对于实际值要少1，我们就找出有多少个这样的情况减去即可，记得开long long

void solve() {
    int n;
    cin >> n;
    vector<i64> a(n);
    for(auto &x : a) std::cin >> x;
    i64 ans = 0;
    vector<i64> add(n+1), even(n+1);
    for(int i = n-1;i >= 0; i--){
        if(a[i] & 1){
            add[i] = add[i+1] + 1;
            even[i] = even[i+1];
        }else{
            add[i] = add[i+1];
            even[i] = even[i+1] + 1;
        }
        ans += (n-1) * a[i];
    }
    for(int i = 0;i < n; i++){
        if(a[i] & 1){
            ans -= even[i];
        }else{
            ans -= add[i];
        }
    }
    cout << ans/2 << "\n";
}

E

经典的bfs，由于T最大100，就算k = 1，x加到1000000也完全不会超时

$x = \begin{cases} reverse(x) & a[i]不能被10整除 \\ x + k & all \end{cases}$

用vis来标记访问过的数，如果反转后的数字或+k之后的数字大于1000000或访问过就不在遍历这个数了

int vis[1000100];
i64 chance(i64 x){
    i64 y = 0;
    while(x){
        y = y * 10 + x % 10;
        x /= 10;
    }
    return y;
}
template<class T>
void solve() {
    i64 a, b, k;
    cin >> a >> b >> k;
    memset(vis, 0, sizeof(vis));
    //for(int i = 1;i <= 1000000; i++) vis[i] = false;
    queue<pair<i64, i64>> q;
    q.push({a, 0});
    vis[a] = 1;
    while(!q.empty()){
        i64 x = q.front().first;
        i64 step = q.front().second;
        i64 y = x + k;
        q.pop();
        if(x == b){
            cout << step << "\n";
            return ;
        }
        if(y <= 1000000 && !vis[y]){
            vis[y] = 1;
            q.push({y, step+1});
        }
        if(x % 10 != 0){
            i64 z = chance(x);
            if(z <= 1000000 && !vis[z]){
                q.push({z, step+1});
                vis[z] = 1;
            }
        }
    }
    cout << "-1\n";
}

F

求 $D_i = \sum_{\substack{j=1\\j\neq i}}^n \text{diff}(s_i, s_j)$ 的最小值

用dp[i][j][k]来表示转移的状态， i，j表示第i个字符串第j位字符,k = 0,表示前面的字符都没翻转，k = 1,表示该字符正在我选的区间翻转中，k = 2表示已经过了翻转的区间，从现在开始就不需要翻转了。

a记录所有字符串中每一位1的总个数，b记录所有字符串中每一位0的总个数

如果s[i][j] = '1'

k = 0, dp[i][j][0] = dp[i][j-1][0] + b[j]

k = 1, $dp[i][j][1] = \min\begin{cases} dp[i][j-1][0] + a[j] - 1 \\ dp[i][j-1][1] + a[j] - 1 \end{cases}$

k = 2, $dp[i][j][2] = \min\begin{cases} dp[i][j-1][1]+ b[j] \\ dp[i][j-1][2] + b[j] \end{cases}$

反之，s[i][j] = '0'一样的道理，不详细说了

void solve() {
    int n, m;
    cin >> n >> m;
    vector<string> s(n);
    vector<int> a(m+1), b(m+1);
    for(int i = 0;i < n; i++){
        cin >> s[i];
        s[i] = ' ' + s[i];
        for(int j = 1;j <= m; j++){
            if(s[i][j] == '1'){
                a[j] = a[j] + 1;
            }else{
                b[j] = b[j] + 1;
            }
        }
    }
    vector<vector<vector<int>>> dp(n, vector<vector<int>>(m+1, vector<int>(3, 0)));
    for(int i = 0;i < n; i++){
        for(int j = 1;j <= m; j++){
            if(s[i][j] == '1'){
                dp[i][j][0] = b[j] + dp[i][j-1][0];
                dp[i][j][1] = min(dp[i][j-1][0] + a[j] - 1, dp[i][j-1][1] + a[j] - 1);
                dp[i][j][2] = min(dp[i][j-1][1] + b[j], dp[i][j-1][2] + b[j]);
            }else{
                dp[i][j][0] = a[j] + dp[i][j-1][0];
                dp[i][j][1] = min(dp[i][j-1][0] + b[j] - 1, dp[i][j-1][1] + b[j] - 1);
                dp[i][j][2] = min(dp[i][j-1][1] + a[j], dp[i][j-1][2] + a[j]);
            }
        }
        cout << min({dp[i][m][0], dp[i][m][1], dp[i][m][2]}) << "\n";
    }
}