Contestant. Rank 978. Rating -34.

A. Cover in Water

题意

给定一个水槽，水槽中某些格子不可以放水，从而由 "每个格子是否可以放水" 构成给定字符串 \(s\)，\(s_i = \mathtt{.}\) 时即为可放水。

现在，需要将水槽填满水，并无视不可以放水的格子，有下面两种操作：

1. 在指定格子上填水；

2. 将某个格子的水取走，填入另一个格子中

定义若一个格子的两边都有水，那么这个格子也会自动被填上水。

输出操作 \(1\) 的最小次数。

思路

首先，只要能构成题意中的特殊情况，我们就有无限水了，从而不需要操作一。

那么，我们只需将字符串按照 非 \(\mathtt{.}\) 字符 分段，如果存在长度 \(\geq 3\) 的分段，那么我们就只需执行两次操作 \(1\)，否则所有空的位置都需要执行一次操作 \(1\) 才能填满。

从而，前者需要 \(2\) 次，后者的次数为字符串中 \(\mathtt{.}\) 的个数。

时间复杂度：\(O(n)\)

对应AC代码

#include <bits/stdc++.h>

using namespace std;

//#define FLOATING_OCEAN

#define int long long
#define pii pair<int, int>
#define pdd pair<double, double>
#define pipi pair<pii, pii>
#define tpi tuple<int, int, int>
#define fs first
#define sc second
#define pb emplace_back
#define ep emplace
#define rall(x) x.rbegin(),x.rend()
#define all(x) x.begin(),x.end()

const int N = 2e5 + 10, M = 2e5 + 10, mod = 1e9 + 7, inf = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-9, PI = acos(-1);

void solve() {
    int n;
    cin >> n;
    string s;
    cin >> s;
    int ans = 0, cnt = 0;
    for(int i=0;i<n;i++){
        if(s[i] == '.') ans ++, cnt ++;
        else if(s[i] == '#'){
            if(cnt > 2){
                ans = 2;
                break;
            }
            cnt = 0;
        }
    }
    if(cnt > 2) ans = 2;
    cout << ans << '\n';
}

signed main() {
# ifdef FLOATING_OCEAN
    freopen("1.in","r",stdin);
    freopen("1.out","w",stdout);
# endif
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
//    init();
    int t = 1;
    cin >> t;
    while (t--) solve();
}

玩 MC 玩的

B. Laura and Operations

题意

对于一个由 \(1, 2, 3\) 组成的序列，定义操作为选择两个不同的数，将其从序列中取出，并添加一个和这两个数不同的数。

输出任意次操作后，是否可以将整个序列变为全是 \(1\)，全是 \(2\)，全是 \(3\)。

思路

我们考虑序列中包含 \(a, b, c\)，并需要将序列变为全是 \(a\) 的情况：

首先，我们不妨将 \(b, c\) 取出，直到某一方数量变为 \(0\)；

假设现在 \(b\) 的数量为 \(0\)，而 \(c\) 的数量不为 \(0\)，那么我们需要更多的 \(b\) 去和 \(c\) 配对。从而我们考虑将 \(a, c\) 取出，直到 \(b\) 的数量和 \(c\) 的数量相等，此时我们再依次将 \(b, c\) 取出，最后就能全都变成 \(a\) 了。

上述操作存在一个问题：\(a\) 的数量可能会不够。

从而，我们考虑加入一个 \(b\) 后，立即和 \(c\) 配对，这样只要序列中有一个 \(a\)，上述操作就一定能执行。而 \(a\) 的数量不为 \(0\)。

可以发现，我们上面的操作等价于把剩余的 \(c\) 拆成两半，一部分和 \(a\) 配对，一部分和 \(b\) 配对。

从而，无解的条件就是 剩余的数量为奇数。

时间复杂度：\(O(1)\)

对应AC代码

#include <bits/stdc++.h>

using namespace std;

//#define FLOATING_OCEAN

#define int long long
#define pii pair<int, int>
#define pdd pair<double, double>
#define pipi pair<pii, pii>
#define tpi tuple<int, int, int>
#define fs first
#define sc second
#define pb emplace_back
#define ep emplace
#define rall(x) x.rbegin(),x.rend()
#define all(x) x.begin(),x.end()

const int N = 2e5 + 10, M = 2e5 + 10, mod = 1e9 + 7, inf = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-9, PI = acos(-1);

void solve() {
    int a, b, c;
    cin >> a >> b >> c;
    cout << 1 - abs(b - c) % 2 << ' ' << 1 - abs(a - c) % 2 << ' ' << 1 - abs(b - a) % 2 << '\n';
}

signed main() {
# ifdef FLOATING_OCEAN
    freopen("1.in","r",stdin);
    freopen("1.out","w",stdout);
# endif
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
//    init();
    int t = 1;
    cin >> t;
    while (t--) solve();
}

个人感觉 B 比 A 简单（

C. Anji's Binary Tree

题意

给定一棵二叉树，以及一个由 'U', 'L', 'R' 组成的字符串 \(s\)，其中 \(s_i\) 为第 \(i\) 个点的标记。

输出至少需要修改多少个点的标记，才能使从 \(1\) 开始，按照标记移动后，能移动到叶节点。

其中，'U' 代表向根节点移动，'L' 代表向左儿子移动，'R' 代表向右儿子移动。

思路

显然，如果我们不修改 'U'，那么我们无法到达这个结点更深的地方。

那么，我们不妨 \(\mathtt{dfs}\) 一下，遍历所有路径的时候，顺便记录有多少个点需要进行修改即可。

具体来说，我们可以先将所有边的边权设为 \(1\)，然后在往儿子 \(\mathtt{dfs}\) 的时候，如果当前结点标记的方向和我们往下走的方向一致，那么将这条边的边权视为 \(1\)，从而便于统计答案。

最后，所有到叶节点的路径中，最短路长度即为答案。

时间复杂度：\(O(n)\)

对应AC代码

#include <bits/stdc++.h>

using namespace std;

//#define FLOATING_OCEAN

#define int long long
#define pii pair<int, int>
#define pdd pair<double, double>
#define pipi pair<pii, pii>
#define tpi tuple<int, int, int>
#define fs first
#define sc second
#define pb emplace_back
#define ep emplace
#define rall(x) x.rbegin(),x.rend()
#define all(x) x.begin(),x.end()

const int N = 8e4 + 10, M = 2e5 + 10, mod = 1e9 + 7, inf = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-9, PI = acos(-1);

void solve() {
    int n;
    cin >> n;
    string s;
    cin >> s;
    s = " " + s;
    vector<pii> e(n + 1);
    for(int i=1;i<=n;i++) cin >> e[i].fs >> e[i].sc;
    int ans = inf;
    auto dfs = [&](auto dfs, auto x, auto now) -> void{
        if(e[x].fs == 0 && e[x].sc == 0) ans = min(ans, now);
        else {
            if(e[x].fs > 0) dfs(dfs, e[x].fs, now + (s[x] == 'L' ? 0 : 1));
            if(e[x].sc > 0) dfs(dfs, e[x].sc, now + (s[x] == 'R' ? 0 : 1));
        }
    };
    dfs(dfs, 1, 0ll);
    cout << ans << '\n';
}

signed main() {
# ifdef FLOATING_OCEAN
    freopen("1.in","r",stdin);
    freopen("1.out","w",stdout);
# endif
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
//    init();
    int t = 1;
    cin >> t;
    while (t--) solve();
}

一开始看错题了，难绷

D. Small GCD

题意

给定一个序列 \(a_i\)，遍历所有三元组 \(<a_i, a_j, a_k>, i \neq j \neq k\)，统计最小值和次小值的 \(\gcd\) 之和。

思路1 欧拉函数

首先，我们可以发现，序列的顺序是不影响最后的结果的，那么我们不妨将序列排个序。

从而，我们列出整体的式子，可以通过合并同类项，得到下面的求和式：

\(\displaystyle \sum_{i=1}^{n-1} \sum_{j=1}^{j - 1} \gcd(a_i, a_j) \cdot (n - i)\)

下面我们进行式子的化简：

\(\because\) 由欧拉函数的性质，\(\displaystyle x = \sum_{d|x} \varphi(d)\)，

\(\therefore \displaystyle \gcd(a_i, a_j) = \sum_{d|\gcd(a_i, a_j)} \varphi(d)\)；

\(\because d|\gcd(a_i, a_j), \gcd(a_i, a_j) | a_i, \gcd(a_i, a_j) | a_j\)，

\(\therefore d|a_i, d|a_j\)，

\(\therefore \displaystyle \gcd(a_i, a_j) = \sum_{d|a_i, d|a_j} \varphi(d)\)，

\(\therefore \displaystyle \sum_{i=1}^{n-1} \sum_{j=1}^{j - 1} \gcd(a_i, a_j) \cdot (n - i) = \displaystyle \sum_{i=1}^{n-1} \sum_{j=1}^{j - 1} \sum_{d|a_i, d|a_j} \varphi(d) \cdot (n - i)\)

那么接下来，我们观察到 \(n - i\) 和 \(j\) 是无关的，从而不妨提前考虑约束 \(d|a_j\) ，因为枚举 \(a_j\) 的因数是完全没必要的。

为何？因为 \(j < i\)，而 \(a_i\) 的所有因数早已在前面被枚举过了。

那么，我们不妨令 \(\text{cnt}(i, x)\) 为因数 \(x\) 在前 \(i\) 个数中出现的次数，从而继续我们的化简：

\(\displaystyle \sum_{i=1}^{n-1} \sum_{j=1}^{j - 1} \sum_{d|a_i, d|a_j} \varphi(d) \cdot (n - i) = \sum_{i=1}^{n-1} \sum_{d|a_i} \text{cnt}(i - 1, d) \cdot \varphi(d) \cdot (n - i)\)

那么，我们就只需先预处理欧拉函数，这可以用线性筛处理。然后枚举前 \(n - 1\) 小的数，用根号复杂度枚举因数即可。

时间复杂度：\(O(\text{MAX} + n \sqrt{\text{MAX}})\)

对应AC代码

#include <bits/stdc++.h>

using namespace std;

//#define FLOATING_OCEAN

#define int long long
#define pii pair<int, int>
#define pdd pair<double, double>
#define pipi pair<pii, pii>
#define tpi tuple<int, int, int>
#define fs first
#define sc second
#define pb emplace_back
#define ep emplace
#define rall(x) x.rbegin(),x.rend()
#define all(x) x.begin(),x.end()

const int N = 1e5 + 10, M = 2e5 + 10, mod = 1e9 + 7, inf = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-9, PI = acos(-1);

//线性筛求积性函数
void sieve_mul_func(int n, bool not_pri[], int pr[], int &cnt, auto &&new_pri, auto &&stop, auto &&on) {
    for (int i = 2; i <= n; i++) {
        if (!not_pri[i]) pr[cnt++] = i, new_pri(i);
        for (int j = 0; j < cnt && i * pr[j] <= n; j++) {
            not_pri[i * pr[j]] = true;
            if (i % pr[j] == 0) {
                stop(i, pr[j]);
                break;
            }
            on(i, pr[j]);
        }
    }
}

//线性求欧拉函数: phi[] 欧拉函数, pr[] 所有素数
void get_phi(int n, bool not_pri[], int pr[], int &cnt, int phi[]) {
    phi[1] = 1;
    sieve_mul_func(n, not_pri, pr, cnt, [&](int i) { phi[i] = i - 1; },
                   [&](int i, int pr) { phi[i * pr] = pr * phi[i]; },
                   [&](int i, int pr) { phi[i * pr] = phi[i] * (pr - 1); });
}

bool not_pri[N];
int pr[N], phi[N], cnt_;

void init() {
    get_phi(1e5, not_pri, pr, cnt_, phi);
}

void solve() {
    int n;
    cin >> n;
    vector<int> a(n + 1);
    for(int i=1;i<=n;i++) cin >> a[i];
    sort(all(a));
    vector<int> cnt(N);
    int ans = 0;
    for(int i=1;i<n;i++){
        int now = 0;
        for(int j=1;j*j<=a[i];j++){
            if(a[i] % j != 0) continue;
            now += (cnt[j] ++) * phi[j];
            if(j != a[i] / j) now += (cnt[a[i] / j] ++) * phi[a[i] / j];
        }
        ans += (n - i) * now;
    }
    cout << ans << '\n';
}

signed main() {
# ifdef FLOATING_OCEAN
    freopen("1.in","r",stdin);
    freopen("1.out","w",stdout);
# endif
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    init();
    int t = 1;
    cin >> t;
    while (t--) solve();
}

思路2 莫比乌斯反演

同样的，我们可以化简得到如下式子：

\(\displaystyle \sum_{i=1}^{n-1} \sum_{j=1}^{j - 1} \gcd(a_i, a_j) \cdot (n - i)\)

注意到此处为 \(\gcd\) 求和问题，我们考虑使用莫比乌斯反演来解决。

接下来给出化简过程：

\(\because\) \(\displaystyle \sum_{i=1}^{n-1} \sum_{j=1}^{j - 1} \gcd(a_i, a_j) \cdot (n - i)\)

$ = {i=1}^{n-1} {j=1}^{j - 1} _{k=1}^{M}k (n - i) $

\(= \displaystyle \sum_{i=1}^{n-1} \sum_{j=1}^{j - 1} \sum_{k=1}^{M}k \cdot [\gcd(\frac{a_i}{k}, \frac{a_j}{k})=1] \cdot (n - i)\)

\(\therefore\) 由莫比乌斯反演：

\(= \displaystyle \sum_{i=1}^{n-1} \sum_{j=1}^{j - 1} \sum_{k=1}^{M}k \sum_{d|\gcd(\frac{a_i}{k}, \frac{a_j}{k})} \mu(d) \cdot (n - i)\)

\(= \displaystyle \sum_{i=1}^{n-1} \sum_{j=1}^{j - 1} \sum_{k=1}^{M}k \sum_{kd|a_i, kd|a_j} \mu(d) \cdot (n - i)\)

\(= \displaystyle \sum_{i=1}^{n-1} \sum_{j=1}^{j - 1} \sum_{k=1}^{M}k \sum_{d=1}^{\lfloor\frac{M}{k}\rfloor} \mu(d) \cdot [kd|a_i]\cdot[kd|a_j] \cdot (n - i)\)

\(= \displaystyle \sum_{k=1}^{M}\sum_{d=1}^{\lfloor\frac{M}{k}\rfloor} k \cdot \mu(d) \sum_{i=1}^{n-1} \sum_{j=1}^{j - 1} [kd|a_i]\cdot[kd|a_j] \cdot (n - i)\)

显然，后者只有一个参数 \(kd\)，那么我们不妨令：

\(\displaystyle \text{f}(x) = \sum_{i=1}^{n-1} \sum_{j=1}^{j - 1} [x|a_i]\cdot[x|a_j] \cdot (n - i)\)

从而代入得到：

\(= \displaystyle \sum_{k=1}^{M}\sum_{d=1}^{\lfloor\frac{M}{k}\rfloor} k \cdot \mu(d) \cdot \text{f}(kd)\)

我们可以用线性筛求出莫比乌斯函数 \(\mu(x)\)，而对于后者，我们可以通过暴力枚举每个数，并枚举他的所有倍数，从而进行配对，计算个数。

时间复杂度：\(O(\text{MAX} \log{\text{MAX}})\)

对应AC代码

#include <bits/stdc++.h>

using namespace std;

//#define FLOATING_OCEAN

#define int long long
#define pii pair<int, int>
#define pdd pair<double, double>
#define pipi pair<pii, pii>
#define tpi tuple<int, int, int>
#define fs first
#define sc second
#define pb emplace_back
#define ep emplace
#define rall(x) x.rbegin(),x.rend()
#define all(x) x.begin(),x.end()

const int N = 1e5 + 10, M = 2e5 + 10, mod = 1e9 + 7, inf = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-9, PI = acos(-1);

//线性筛求积性函数
void sieve_mul_func(int n, bool not_pri[], int pr[], int &cnt, auto &&new_pri, auto &&stop, auto &&on) {
    for (int i = 2; i <= n; i++) {
        if (!not_pri[i]) pr[cnt++] = i, new_pri(i);
        for (int j = 0; j < cnt && i * pr[j] <= n; j++) {
            not_pri[i * pr[j]] = true;
            if (i % pr[j] == 0) {
                stop(i, pr[j]);
                break;
            }
            on(i, pr[j]);
        }
    }
}

//线性求莫比乌斯函数 μ: mu[] μ函数, pr[] 所有素数
void get_mu(int n, bool not_pri[], int pr[], int &cnt, int mu[]) {
    mu[1] = 1;
    sieve_mul_func(n, not_pri, pr, cnt, [&](int i) { mu[i] = -1; },
                   [&](int i, int pr) { mu[i * pr] = 0; },
                   [&](int i, int pr) { mu[i * pr] = mu[i] * mu[pr]; });
}

bool np[N];
int mu[N], pr[N], cnt;

void init() {
    get_mu(1e5, np, pr, cnt, mu);
}

void solve() {
    int n;
    cin >> n;
    vector<int> a(n + 1);
    for(int i=1;i<=n;i++) cin >> a[i];
    sort(all(a));
    vector<int> l(N, -1), r(N, -1), f(N);
    for(int i=1;i<=n;i++){
        if(l[a[i]] == -1) l[a[i]] = i;
        r[a[i]] = i;
    }
    for(int i=1;i<=1e5;i++){
        int now = 0;
        for(int j=i;j<=1e5;j+=i){
            if(l[j] == -1) continue;
            for(int k=l[j];k<=r[j];k++){
                f[i] += (n - k) * now;
                now ++;
            }
        }
    }
    int ans = 0;
    for(int k=1;k<=1e5;k++){
        for(int d=1;d<=1e5/k;d++){
            ans += k * mu[d] * f[k * d];
        }
    }
    cout << ans << '\n';
}

signed main() {
# ifdef FLOATING_OCEAN
    freopen("1.in","r",stdin);
    freopen("1.out","w",stdout);
# endif
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    init();
    int t = 1;
    cin >> t;
    while (t--) solve();
}

赛时就缺个不会筛（