Codeforces Round 911 (Div. 2)

C. Anji's Binary Tree

思路

树形dp

ac代码

#include <bits/stdc++.h>

using namespace std;
using i64  = long long;
const i64 inf = 8e18;
typedef pair<int, int> pii;
const int N = 3e5 + 10;

char w[N];//存U、L、R
int ls[N], rs[N];//存左孩子，右孩子

int dfs(int u) {
    if (!ls[u] && !rs[u]) return 0;
    int res = N;
    if (ls[u]) res = min(res, f(ls[u]) + (w[u] != 'L'));
    if (rs[u]) res = min(res, f(rs[u]) + (w[u] != 'R'));
    return res;
}

void solve() {
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> w[i];
    for (int i = 1; i <= n; i++) cin >> ls[i] >> rs[i];

    cout << dfs(1) << endl;
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);

    int t = 1;
    cin >> t;
    while (t --) solve();

    return 0;
}

D. Small GCD

思路

题目要求输出的是数组中的每对\((i, j, k)\)的\(f(a_i,a_j,a_k)\)，所以我们可以先给数组按从小到大排个序。我们意识到：\(f(a_i,a_j,a_k)\)的值和\(a_i,a_j,a_k\)最大的数是无关的。我们假设\(a_k\)是这三个数里最小的，\(a_i\)是第二小，固定\(a_i\)、\(a_j\)，则\(a_k\)的取值有\(n - i\)个。
开一个b数组，\(b_i\)里存\(i\)的所以因子；再开一个c数组\(c_i\)表示因子i的的出现次数；再开一个f数组，\(f_i\)表示gcd(x, y) == i 的倍数的数对个数。容斥一下得到，gcd(x, y) == i 的数对个数等于\(f_i\) - \(f_2\)\(_i\) - \(f_3\)\(_i\) - \(f_4\)\(_i\) ... - \(f_x\)\(_i\) ，\(x * i\) <= 最大的因子

ac代码

#include <bits/stdc++.h>

using namespace std;
using i64  = long long;
const i64 inf = 8e18;
typedef pair<int, int> pii;
const int N = 3e5 + 10;

vector<int> b[100010];

void solve() {
    int n;
    cin >> n;
    vector<i64> a(n + 1), c(N), f(N);
    for (int i = 1; i <= n; i++) cin >> a[i];
    sort(a.begin() + 1, a.end());
    for (int i = 1; i <= n; i++) {
        for (auto x : b[a[i]]) {
            f[x] += c[x] * (n - i);
            c[x] ++;
        }
    }
    i64 ans = 0;
    for (int i = 100000; i > 0; i--) {
        for (int j = i + i; j <= 100000; j += i) {
            f[i] -= f[j];
        }
        ans += f[i] * i;
    }

    cout << ans << endl;
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);

    for (int i = 1; i <= 100000; i++) {
        for (int j = i; j <= 100000; j += i)
            b[j].push_back(i);
    }

    int t = 1;
    cin >> t;
    while (t --) solve();

    return 0;
}