链接：https://codeforces.com/contest/2195

A. Sieve of Erato67henes

算法：

数学。

思路：

由于 \(67\) 为质数，所有就是判断数组中有没有 \(67\)。

关键代码：

void miyan()
{
    int n;
    cin >> n;
    set<int> S;
    for (int i = 0; i < n; ++i)
    {
        int x;
        cin >> x;
        S.insert(x);
    }

    if (S.count(67))
        cout << "YES" << endl;
    else
        cout << "NO" << endl;
}

B. Heapify 1

算法：

贪心。

思路：

定义 \(b\) 为最终排列。

由题可知 \(x, 2 \times x, 3 \times x, 4 \times x, ….. k \times x\) 同为一组，容易想到他们直接可以相互交换，那么只需判断 \(a\) 中的某个无序组集合与 \(b\) 中的对应的有序组集合是否相等即可。

关键代码：

void miyan()
{
    int n;
    cin >> n;
    vector<int> a(n);
    for (auto &x : a)
        cin >> x;

    auto b = a;
    ranges::sort(b);

    vector<int> st(n, 0);
    for (int i = 1; i <= n; ++i)
    {
        if (st[i - 1])
            continue;

        set<int> S1, S2;
        for (int j = i; j <= n; j *= 2)
        {
            S1.insert(a[j - 1]);
            S2.insert(b[j - 1]);
            st[j - 1] = 1;
        }

        if (S1 != S2)
        {
            cout << "NO" << endl;
            return;
        }
    }

    cout << "YES" << endl;
}

C. Dice Roll Sequence

算法：

贪心。

思路：

\(x\) 与 \(7 – x\) 不相邻。

当 \(a_i\) 与 \(a_{i + 1}\) 不相邻时，考虑变换 \(a_{i + 1}\)，由于 \(a_{i + 1}\) 有 \(4\) 种选择，我们只需选择与 \(a_{i + 2}\) 不一样且相邻的，可知在变换 \(a_{i + 1}\) 后，无需再考虑 \(a_{i + 1}\)，直接考虑 \(a_{i + 2}\) 即可，答案就为该策略下的变换次数。

关键代码：

void miyan()
{
    int n;
    cin >> n;
    vector<int> a(n);
    for (auto &x : a)
        cin >> x;

    vector<int> d(7);
    for (int i = 1; i <= 6; ++i)
        d[i] = 7 - i;

    ll ans = 0;
    for (int i = 0; i < n - 1; ++i)
        if (a[i] == d[a[i + 1]] || a[i] == a[i + 1])
            ++ans, ++i;

    cout << ans << endl;
}

D. Absolute Cinema

算法：

数学。

思路：

手玩样例发现：\(a_i = f(i – 1) – 2 \times f(i) + f(i + 1)\)，因此可以确定 \([2, n – 1]\) 的答案。

考虑 \(a_1\) 与 \(a_n\)：

• 因为 \(f(1) = a_2 + 2 \times a_3 + ….. + (i – 1) \times a_n\)，而我们已知 \([2, n – 1]\) 的全部值，那么易得 \(a_n\)；
• 又因为 \(f(n) = (n – 1) \times a_1 + (n – 2) \times a_2 + ….. + a_{n – 1}\)，同理，易得 \(a_1\)。

关键代码：

void miyan()
{
    int n;
    cin >> n;
    vector<ll> a(n);
    for (auto &x : a)
        cin >> x;

    vector<ll> ans(n, 0);
    for (int i = 0; i < n - 2; ++i)
        ans[i + 1] = (a[i] - 2 * a[i + 1] + a[i + 2]) / 2;

    ll cur = a[0];
    for (int i = 0; i < n - 1; ++i)
        cur -= ans[i] * i;

    ans[n - 1] = cur / (n - 1);

    cur = a[n - 1];
    for (int i = n - 1; i > 0; --i)
        cur -= ans[i] * (n - i - 1);

    ans[0] = cur / (n - 1);

    for (auto &x : ans)
        cout << x << ' ';
    cout << endl;
}

E. Idiot First Search

算法：

树形 \(dp\)。

思路：

定义 \(cnt(u)\) 为从点 \(u\) 出发遍历完整颗子树，再回到点 \(u\) 所需的时间。

注意到，对于子树 \(u\)，如果从点 \(u\) 出发遍历完整颗子树，再回到点 \(u\)，其共经过 \(cnt(v_1) + cnt(v_2) + g(u) \times 2\) 秒。

容易想到对于点 \(1\)，其答案为 \(1 + cnt(1)\)，对于点 \(1\) 的子节点 \(u\)，其答案为为 \(2 + cnt(1) + cnt(u)\)，易得对于任意点 \(u\)，其答案为从点 \(1\) 到 \(u\) 点所经历的简单路径中点的个数加上路径上点的 \(cnt\)。

关键代码：

void miyan()
{
    int n;
    cin >> n;
    vector<vector<int>> g(n + 1);
    g[0].push_back(1);
    for (int u = 1; u <= n; ++u)
    {
        int l, r;
        cin >> l >> r;

        if (l == 0)
            continue;

        g[u].push_back(l);
        g[u].push_back(r);
    }

    vector<ll> cnt(n + 1, 0);
    vector<ll> dep(n + 1, 0);
    vector<ll> ans(n + 1, 0);
    auto dfs1 = [&](auto &&self, int u) -> void
    {
        for (auto v : g[u])
        {
            dep[v] = (dep[u] + 1) % MOD;

            self(self, v);

            cnt[u] = (cnt[u] + cnt[v]) % MOD;
        }

        cnt[u] = (cnt[u] + g[u].size() * 2ll) % MOD;
    };

    ll cur = 0;
    auto dfs2 = [&](auto &&self, int u) -> void
    {
        cur = (cur + cnt[u]) % MOD;
        ans[u] = (cur + dep[u]) % MOD;

        for (auto v : g[u])
            self(self, v);

        cur = (cur - cnt[u] + MOD) % MOD;
    };

    dfs1(dfs1, 0);
    dfs2(dfs2, 1);

    for (int i = 1; i <= n; ++i)
        cout << ans[i] << ' ';

    cout << endl;
}

F. Parabola Independence

还没补。