Codeforces Round 1106 (Div. 2)

by JiuQiin Codeforces, 题解on Posted on
“I dream my painting and I paint my dream.”
— Vincent van Gogh
反思

果然，又是只做了前三题，第二题当时还卡住了，我发现了，我是真的不擅长数学，我努力地靠近了，可是他不爱我 (╥﹏╥)，我当时想了二十多分钟想不出来，没法，只能打表，还好俺猜答案的能力一绝，妈的，都是因为数学不好练出来的。所以最后找规律过了。

然后，到第三题，又被卡了，因为没想清楚就开写，结果写着写着偏离了原方案，只能边写边改，写完后发现有个 bug 是实现的问题，结果又推翻重写，还是原思路，但是成功实现了，过了。

得，这次还剩半小时看 D，不冤，这次真不冤，这个 D 我看了题解自己也想了很久才想通。不是我的问题，是他写的太烂，嗯，一定是这样。我一直觉得举例说明是最容易讲清楚的，就像物理的发展，大部分都是从特殊到一般，从大量的例子中归纳出一般规律，结果就形成了公式，甚至很多公式就是直接观测出来的结果，你问为什么，没有为什么，至少现在没有，所以，我想说的是从特例中找出一般思路是人常规的思维模式。当时我看题解怎么都看不明白，自己实现了一个样例结果就知道了

Contents hide
1 A. Another Puzzle from Papyrus
1.1 题意
1.2 思路
1.3 代码
2 B. Crimson Triples
2.1 题意
2.2 思路
2.3 代码（打表）
3 C. Village Guilds
3.1 题意
3.2 思路
3.3 代码
4 D. Storming Arasaka
4.1 题意
4.2 思路

A. Another Puzzle from Papyrus

题意

给出两个长度为 n 的数组 a， b，可执行以下操作：

  • 选择任意的 1≤i≤n，ai=ai−11 \leq i \leq n，a_i = a_i – 1，该操作的代价为 1
  • 将 a 数组进行排序，该操作的代价为 c

问，将 a 变成 b 的最小代价，若不能变成，则输出 -1

思路

首先，若任意的 1≤i≤n,ai≥bi1 \leq i \leq n, a_i \geq b_i，则答案为 ∑i=1nai−bi\sum_{i = 1}^{n}a_i – b_i，与 aia_i 和 bib_i 的相对大小无关，比如 a={9, 7}，b={5, 3}，ans=(a1−b1)+(a2−b2)=(9−5)+(7−3)=4+4=8a = \{9 ,\:\ 7\}，b = \{5 ,\:\ 3\}，ans = (a_1 – b_1) + (a_2 – b_2) = (9 – 5) + (7 – 3) = 4 + 4 = 8, 交换相减，ans=(a1−b2)+(a2−b1)=（9−3）+（7−5）=6+2=8ans =(a_1 – b_2) + (a_2 – b_1) = （9 – 3） + （7 – 5） = 6 + 2 = 8，这是因为将括号打开后，ans=∑i=1nai−bi=∑i−1nai−∑i=1nbians = \sum_{i = 1}^{n}a_i – b_i = \sum_{i – 1}^na_i – \sum_{i = 1}^nb_i，与下标无关

但如果，存在一个 1≤i≤n，ai>bi1 \leq i \leq n，a_i > b_i，则必须交换位置，答案加 cc

但是，有一种情况会输出 −1-1，将数组 aa 和 bb 分别从小到大进行排序，若 ∃1≤i≤n,ai<bi\exists 1 \leq i \leq n, a_i < b_i，后面的 bjb_j 更会大于 aia_i，不可行，而前面的 bjb_j 已经一对一被更小的 aja_j 消耗掉了，所以这种情况不可行

代码

#include <bits/stdc++.h>
using namespace std;
#define lowbit(x) (x & (-x))
#define endl '\n'
typedef long long LL;
#define PLL pair<LL, LL>
const LL MOD = 998244353;
const LL MAX = 1e6 + 100;
const LL INF = 0x3f3f3f3f3f3f3f;

void solve()
{
    int n, c;
    cin >> n >> c;
    vector<int> a(n + 1), b(n + 1), vis(n + 1, 0);

    int ans = 0;
    for (int i = 1; i <= n; ++i)
    {
        cin >> a[i];
    }
    int f = 0;
    for (int i = 1; i <= n; ++i)
    {
        cin >> b[i];
        if (a[i] < b[i])
        {
            f = 1;
        }
    }
    if (f)
    {
        ans += c;
    }
    
    sort(a.begin() + 1, a.end());
    sort(b.begin() + 1, b.end());

    for (int i = 1; i <= n; ++i)
    {
        if (a[i] < b[i])
        {
            cout << -1 << endl;
            return;
        }
        ans += abs(a[i] - b[i]);
    }

    cout << ans << endl;
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    LL T;
    cin >> T;
    while (T--)
    {
        solve();
    }
    return 0;
}

B. Crimson Triples

题意

给出数字 nn ，问有多少个三元组（a,b,c）（a, b, c）满足 gcd⁡(lcm(a,b),lcm(b,c))=gcd⁡(a,c)1≤a,b,c≤n\gcd( lcm (a, b), lcm(b, c)) = \gcd(a, c) \quad 1 \leq a, b, c \leq n ，只要 a1≠a2 or b1≠b2 or c1≠c2a_1 \neq a_2 \ or\ b_1 \neq b_2 \ or \ c_1 \neq c_2，则称这两个三元组是不同的

思路

你真要问我的思路，打表找规律

当然，题解给出的思路就有道理多了，但我总觉得他也是猜的，首先只要 aa 和 cc 都能被 bb 整除，则 lcm(a,b)=a，lcm(b,c)=clcm(a, b) = a ，lcm(b, c) = c，自然 gcd(lcm(a,b),lcm(b,c))=gcd(a,c)gcd(lcm(a, b), lcm(b, c)) = gcd(a, c)，毫无疑问成立，那如果有其中一项不满足呢？反证法，假设 aa 不能被 bb 整除，由于 lcm(a,b)lcm(a, b) 能被 bb 整除，lcm(b,c)lcm(b, c) 能被 bb 整除，他们两都有共同的一部分 bb ，所以 gcd(lcm(a,b),lcm(b,c))gcd(lcm(a, b), lcm(b, c)) 也能被 bb 整除，即 gcd(a,c)gcd(a, c) 也能被 bb 整除，既然 aa 的一部分都能被 bb 整除，但 aa 却不能被 bb 整除，矛盾

代码（打表）

#include <bits/stdc++.h>
using namespace std;
#define lowbit(x) (x & (-x))
#define endl '\n'
typedef long long LL;
#define PLL pair<LL, LL>
const LL MOD = 998244353;
const LL MAX = 1e6 + 100;
const LL INF = 0x3f3f3f3f3f3f3f;

void solve() {
    LL n;
    cin >> n;

    LL ans = 0;

    // LL n = 10;
    // for (LL i = 1; i <= n; ++i)
    // {
    //     for (LL j = 1; j <= n; ++j)
    //     {
    //         for (LL k = 1; k <= n; ++k)
    //         {
    //             if (gcd(lcm(i, j), lcm(j, k)) == gcd(i, k))
    //             {
    //                 cout << i << " " << j << " " << k << endl;
    //                 ++ans;
    //             }
    //         }
    //     }
    // }
    // cout << n << " " << ans << endl;

    ans = 0; 
    for (LL i = 1; i <= n; ++i) {
        for (LL j = 1; j * j <= i; ++j) {
            if (i % j == 0) {
                ans += n / j;
                if (j != i / j)
                {
                    ans += n / (i / j);
                }
                // cout << i << endl;
                // cout << j << " " << n/ j<< endl;
                // cout << i / j << " " << n / (i / j) << endl;
            }
        }
    }
    cout << ans << endl;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    LL T;
    cin >> T;
    while (T--) {
        solve();
    }
    return 0;
}

C. Village Guilds

题意

由 n 个点构成的一棵以 1 为根的树，若有一组节点有共同的祖先，且他们到该祖先的距离相等，则，这些点构成一种方案，问一共有多少种方案，两个方案中至少有一个节点不同

思路

贡献法{\color{Yellow}贡献法}

设 u 为祖先，它本身就有一次贡献 h = 0, 在他的子树中，离他距离 h = 1 的孩子合并为一组，贡献为 1，离他距离 h = 2 的孩子合并为一组，贡献为 1 …… 往下一直找，直到只有一个孩子时，则无法合并，所以我们维护当前点距离叶子最远的那条链的距离即可，举例，在以下图中，对于 h = 0 到 h = 5 当前祖先（红点）都分别有一次贡献，但当 h = 6 时，没有两个及以上的点合并，所以不行

等一下，以上这个图没画好，有个易错点没说明，以下这张图说明了，即使是两个及以上的点也可能不行，因为他们可能在之前已经合并过了，比如 h = 6 时，在 h = 5 时就已经合并了

去找当前子树中第二长的链，答案为这条链的长度，为什么呢？

因为最长的那条链它的长度不可靠，可能在之前后面的点就已经合并过了，不，是一定合并过了，不然不可能在他的其中一颗子树中，而找第二长的链，他一定可以和在另一颗子树中的最长的那条链中的点进行合并，而越往上，越容易合并，所以，每个点都去维护当前最长链的长度，祖先 u 就去找他的子树中第二长的链的长度，但是更新的时候是用最长的那条链来进行更新

对于每个节点都要对他的子节点进行排序，所以时间复杂度为 O（n⋅log⁡n⋅log⁡(log⁡n))）O（n \cdot \log n \cdot \log(\log n)) ）

代码

#include <bits/stdc++.h>
using namespace std;
#define lowbit(x) (x & (-x))
#define endl '\n'
typedef long long LL;
#define PLL pair<LL, LL>
const LL MOD = 998244353;
const LL MAX = 1e6 + 100;
const LL INF = 0x3f3f3f3f3f3f3f;

void solve() {
    int n;
    cin >> n;

    vector<vector<int>> G(n+  1);

    for (int i = 2; i <= n; ++i) {
        int u;
        cin >> u;
        G[u].push_back(i);
    }

    vector<int> dep(n + 1, 0);

    int ans = 0;
    auto dfs = [&](auto dfs, int u) -> void
    {
        vector<int> d;
        for (int v : G[u])
        {
            dfs(dfs, v);
            d.push_back(dep[v]);
        }

        sort(d.begin(), d.end(), greater<int>());

        if (d.empty()) {
            dep[u] = 1;
        }
        else {
            dep[u] = d[0] + 1;
        }

        ++ans;
        if (d.size() >= 2) {
            ans += d[1];
        }
    };

    dfs(dfs, 1);

    cout << ans << endl;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    LL T;
    cin >> T;
    while (T--) {
        solve();
    }
    return 0;
}

D. Storming Arasaka

题意

给出一个整数 n ，将 n 的所有约数划分成几个非空层（没有 1，但有 n），每一层必须满足：

  • 当前层中的数字的约数必须在之前层出现过
  • 同一层中的相邻数字的最大公约数必须大于一

问，最少有多少层

思路

有两个关键点需要明确：

  1. 质因数只能单独一层，反证法，假设 aa 为 nn 的其中一个质因数，bb 与 aa 相邻，b=a⋅kb = a \cdot k，则 aa 为 bb 的约数，必须在之前层出现，矛盾
  2. 第 (i+1)(i + 1) 层的数字是由第 ii 层的数字乘以一个质因数得到的

举例说明

我说不清楚为何这样就是层数最少的，为何就一定能保证同层相邻的数字的最大公因数一定大于一，但这样一定能写完 n 所有的约数，因为我们实际上是在根据约束的个数在枚举

我只能隐约感觉出来这很像动态规划的思想，后面的利用前面的条件推出来

随便说说吧，就比如当讨论两个因数的时候，我想在这一层放三个因数，这样才有可能缩小层数，假设我放 3⋅63 \cdot 6 ，因为 6=2⋅36 = 2 \cdot 3，所以 66 的因数在之前层都已经出现过了，但是，他分开来看也等于 3⋅（3⋅2）3 \cdot （3 \cdot 2），万一我想要得到 3⋅33 \cdot 3 呢，那必须把括号拆掉，就是先有 （3⋅3）（3 \cdot 3），再有 （3⋅3）⋅2（3 \cdot 3） \cdot 2，那不就又回到最开始，下一层利用上一层的因数组合了吗，除非你可以永远捆绑 （3⋅2）（3 \cdot 2），否则，他们必定会被拆开，那就又会多一层，依旧回到两个因数到三个因数的模式。再说相邻的数 gcdgcd 大于一的问题，就比如上面的例子，先是列出 2352 \:3 \: 5，三个质因数，然后再分别乘一个质数，这个乘其实也是有顺序的，先把 22 拿来乘， 2⋅2, 2⋅3, 2⋅52 \cdot 2, \ 2 \cdot 3, \ 2 \cdot 5 ，内部可以任意交换，然后是 33，3⋅3, 3⋅53 \cdot 3, \ 3 \cdot 5，由于刚刚 22 有一个是 2⋅32 \cdot 3，这个就将 22 和 33 连接在了一起，所以就将 2⋅32 \cdot 3 放在以 2 为中心去乘的一组的最后一个，作为 22 和 33 的连接点，同理 33 也可将 3⋅53 \cdot 5 作为 33 与 55 的连接点，然后后面其实不用操心了，既然之前都是相邻的 gcdgcd 大于一，后面也是根据同一个或者是相邻的再乘以一个质因数，更加大于一

Post authorWritten by

Leave a Comment

您的邮箱地址不会被公开。 必填项已用 * 标注