526互联

Codeforces Round 911 (Div. 2)

发布时间 2023-11-27 19:14:08作者: value0

Codeforces Round 911 (Div. 2)

A - Cover in Water

解题思路:

如果存在三个以上相邻的格子需要填，那么答案为二，否则有多少空格答案为多少。

代码:

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
typedef pair<int, int> pii;
#define fi first
#define se second

void solve()
{
    int n;
    cin >> n;
    string s;
    cin >> s;
    int cnt = 0;
    ll ans = 0;
    bool f = false;
    for (auto c : s)
    {
        if (c == '.')
        {
            cnt++;
        }
        else
        {
            if (cnt == 1)
            {
                ans += 1;
            }
            else if (cnt == 2)
            {
                ans += 2;
            }
            else if (cnt > 2)
            {
                ans = 2;
                f = true;
                break;
            }
            cnt = 0;
        }
    }
    if (!f)
    {
        if (cnt == 1)
        {
            ans += 1;
        }
        else if (cnt == 2)
        {
            ans += 2;
        }
        else if (cnt > 2)
        {
            ans = 2;
        }
    }
    cout << ans << endl;
}

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

B - Laura and Operations

解题思路:

有\(a,b,c\),假设我们要探讨\(a\)所代表的数能否有留存。

\(b,c\)中较大数减去较小数，较小数化为0。设留存数为\(d\).

此时，我们有\(a,d\)，若\(d\)为奇数，那么无论无论如何也化不完。否则就可以。

代码:

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
typedef pair<int, int> pii;
#define fi first
#define se second

bool check(int a, int b, int c)
{
    if (b >= c)
    {
        a += c;
        b -= c;
        c = 0;
        if (b == 0)
        {
            return true;
        }
        else
        {
            if (b & 1)
            {
                return false;
            }
            else
            {
                if (a > 0)
                {
                    return true;
                }
                return false;
            }
        }
    }
    else
    {
        a += b;
        c -= b;
        b = 0;
        if (c == 0)
        {
            return true;
        }
        else
        {
            if (c & 1)
            {
                return false;
            }
            else
            {
                if (a > 0)
                {
                    return true;
                }
                return false;
            }
        }
    }
}

void solve()
{
    int a, b, c;
    cin >> a >> b >> c;
    int fa = check(a, b, c);
    int fb = check(b, a, c);
    int fc = check(c, a, b);
    cout << fa << ' ' << fb << ' ' << fc << endl;
}

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

C - Anji's Binary Tree

解题思路:

一次\(dfs\)即可。我们找到从根节点到叶子结点的最小需要修改路径即可。

路径中，若非叶子结点为\(U\),那么一定要修改。

走左儿子时，如果结点标记为\(R\)要修改，走右儿子同理。

代码:

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
typedef pair<int, int> pii;
#define fi first
#define se second

void solve()
{
    int n;
    cin >> n;
    string s;
    cin >> s;
    s = ' ' + s;
    vector<int> l(n + 1), r(n + 1);
    vector<bool> leaf(n + 1);
    for (int i = 1; i <= n; i++)
    {
        cin >> l[i] >> r[i];
        if (l[i] == 0 && r[i] == 0)
        {
            leaf[i] = true;
        }
    }
    ll ans = 1e9;
    ll cur = 0;
    auto dfs = [&](auto self, int u) -> void
    {
        // cout << u << endl;
        if (leaf[u])
        {
            ans = min(ans, cur);
            return;
        }
        if (s[u] == 'U')
        {
            cur++;
        }
        if (l[u] > 0)
        {
            if (s[u] == 'R')
            {
                cur++;
            }
            self(self, l[u]);
            if (s[u] == 'R')
            {
                cur--;
            }
        }
        if (s[u] == 'U')
        {
            cur--;
        }
        if (s[u] == 'U')
        {
            cur++;
        }
        if (r[u] > 0)
        {
            if (s[u] == 'L')
            {
                cur++;
            }
            self(self, r[u]);
            if (s[u] == 'L')
            {
                cur--;
            }
        }
        if (s[u] == 'U')
        {
            cur--;
        }
    };
    // cout << 1 << endl;
    dfs(dfs, 1);
    cout << ans << endl;
}

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

D - Small GCD

解题思路:

根据式子，不难看出就是遍历三元组全集，所以顺序无关，直接排序同样遍历三元组全集即可。

对排序后的数组取三元组\((a[i],a[j],a[k]),(i < j <k)\)，所以\(a[i] \leq a[j] \leq a[k]\)。那么\((a[i],a[j])\)能够做出贡献的次数为\(n - j\)。

如上，按升序遍历每个元素的因子，记录\(f[i]\)。

\(f[i]:最大公因数为i的倍数的数对数量\)。

\(c[x]:为枚举到当前，所有元素中因子x出现的次数\).由于\(c[x]\)的系数随着遍历位置而改变，所以我们边累计\(f[x]\)边更新\(c[x]\)。

\(f[x] = \sum_{i = 1}^{n}(c_i[x] * (n - i))\)。

然后，经典容斥更新\(f[i]\)得到新\(f[i]\)。

\(f[i]:最大公因数恰好为i的数对数量\).

设\(ans[i]:最大公因数恰好为i的数对数量\)。\(maxval 为值域最大值\)。

\(ans[i] = f[i] - ans[2 * i] - ans[3 * i] - ... -ans[k * i],((k + 1) * i > maxval)\)。

最终答案为\(\sum_{i= 1}^{maxval}(f[i] *i)\)

代码:

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
typedef pair<int, int> pii;
#define fi first
#define se second
const int mod = 1e9 + 7;
const int N = 1e5 + 10;
vector<int> b[N];
void solve()
{
    int n;
    cin >> n;
    vector<ll> a(n + 1);
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
    }
    sort(a.begin() + 1, a.end());
    vector<ll> c(1e5 + 10);
    // 枚举每个a[i]的因子,计算最大公因数为x的倍数的数对数量
    // f[i]:最大公因数为i的倍数的数对数量
    vector<ll> f(1e5 + 10, 0);
    for (int i = 1; i <= n; i++)
    {
        for (auto x : b[a[i]])
        {
            // 此处a[i]为三元组中第二大的数，数组经过排序
            //  所以能组成的合法三元组为(n - i)个
            f[x] += c[x] * (n - i);
            // 边计数边累加
            c[x]++;
        }
    }

    // 经典容斥求得 f[i] : 最大公因数恰好为i的数对数量
    ll ans = 0;
    for (int i = 1e5; i; i--)
    {
        for (int j = i * 2; j <= 1e5; j += i)
        {
            f[i] -= f[j];
        }
        // 每个数对的贡献值就是i
        ans += f[i] * i;
    }
    // cout << 1 << endl;
    cout << ans << endl;
}

int main()
{
    int t = 1;
    cin >> t;
    // 筛出j的所有因子
    for (int i = 1; i <= N - 5; i++)
    {
        for (int j = i; j <= N - 5; j += i)
        {
            b[j].push_back(i);
        }
    }
    // cout << 1 << endl;
    while (t--)
    {
        solve();
    }
    return 0;
}