在这个随笔中，会有笔者的一些做题笔记，包括但不限于暴力的思想、解题技巧、代码实现等。

CF850B Arpa and a list of numbers

TAG: \(\texttt{暴力，数学}\)

题意

Arpa and a list of numbers

题面翻译

我们认为一个序列是坏序列，当且仅当该序列非空且 \(\operatorname{gcd}\) 是 \(1\)。现在有两种操作：

1. 删除一个数，代价为 \(x\)。
2. 给一个数 \(+1\)，代价为 \(y\)。

现给出该序列和 \(x，y\)，求将给定序列变为好序列的最小代价。

\(n\leq 10^5\)。

题解

\(dp_{i,S,P}\) 为 \(i\) 的子树内是否存在 S 和 P 的状态。

转移方程为：

当 \(s_i\) 为 C 时

dp[x][0][0] += min({ dp[v][1][0] + 1, dp[v][0][1] + 1, dp[v][0][0] });
dp[x][1][0] += min({ dp[v][0][0], dp[v][1][0], dp[v][0][1] + 1 });
dp[x][0][1] += min({ dp[v][0][0], dp[v][1][0] + 1, dp[v][0][1] });

当 \(s_i\) 为 S 时

dp[x][1][0] += min({ dp[v][1][0], dp[v][0][1] + 1, dp[v][0][0] });

当 \(s_i\) 为 P 时

dp[x][0][1] += min({ dp[v][1][0] + 1, dp[v][0][1], dp[v][0][0] });

代码
\(\texttt{Link}\): https://codeforces.com/problemset/submission/1926/276856210

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e5 + 9;
int n, x;
int dp[N][2][2];
string s;
vector<int> edge[N];

void dfs(int x) {
    dp[x][0][0] = dp[x][1][0] = dp[x][1][1] = dp[x][0][1] = 0;
    if (s[x] == 'S') dp[x][0][1] = dp[x][0][0] = 1e9;
    if (s[x] == 'P') dp[x][1][0] = dp[x][0][0] = 1e9;
    for (int i : edge[x]) {
        dfs(i);
        if (s[x] == 'C') {
            dp[x][0][0] += min({ dp[i][1][0] + 1, dp[i][0][1] + 1, dp[i][0][0] });
            dp[x][1][0] += min({ dp[i][0][0], dp[i][1][0], dp[i][0][1] + 1 });
            dp[x][0][1] += min({ dp[i][0][0], dp[i][1][0] + 1, dp[i][0][1] });
        }
        if (s[x] == 'S') 
            dp[x][1][0] += min({ dp[i][1][0], dp[i][0][1] + 1, dp[i][0][0] });
        if (s[x] == 'P') 
            dp[x][0][1] += min({ dp[i][1][0] + 1, dp[i][0][1], dp[i][0][0] });
    }
}

void solve() {
    cin >> n;
    for (int i = 1; i <= n; i++) edge[i].clear();
    for (int i = 2; i <= n; i++) {
        cin >> x;
        edge[x].push_back(i);
    }
    cin >> s; s = " " + s;
    dfs(1);
    cout << min({ dp[1][1][0], dp[1][0][1], dp[1][0][0] }) << "\n";
}

signed main() {
    int t;
    cin >> t;
    while (t--) solve();
    return 0;
}