Codeforces Round 1109 (Div. 3)

by JiuQiin Codeforces, 题解on Posted on
“THE PROLOGUE. When that the Knight had thus his tale told In all the rout was neither young nor old,”
— Geoffrey Chaucer · The Canterbury Tales. The Miller's Tale.
首页 » 题解 » Codeforces » Codeforces Round 1109 (Div. 3)

一些废话

呃，无语，很是无语，对于 AA 题把求最大值看成求最小值，而导致 WAWA 了两发这档子事，我都不愿意承认是我干的。可问题是，这是怎么通过样例的，四五个样例愣是没有一个把你拦下来是吧。这次打的一般般吧，不算很好，但没有差的离谱，算是稳定失常。DD 题想出来了我还是蛮高兴的，我当时以为要一直卡死的，但当时，突然，灵光一现，那一刻我其实还没有想通，但是有种感觉告诉我，我知道了，我马上就要想出来了，就是那种怦然心动的感觉，类似于。但之后又卡 EE 了，难受，这个 EE 给我的感觉就是不是做不出来，但就是差临门一脚，但对于这种赛制来说，只有 00 和 11 的区别，那就是等同于没做出来。呃，这个 FF，我补了之后发现他大可跟 EE 换个位置，FF 的难度全在读题理解上了

Contents hide
1 一些废话
2 A. Iskander and Drawings
2.1 题意
2.2 思路
2.3 代码
3 B. Nikita and Books
3.1 题意
3.2 思路
3.3 代码
4 C. Stepan and Permutation
4.1 题意
4.2 思路（裴蜀定理）
4.3 代码
5 D. Yaroslav and Productivity
5.1 题意
5.2 思路
5.3 代码
6 E. Masha and the Garland
6.1 题意
6.2 思路
6.3 官方思路
6.4 代码
7 F. Anya Loves Trees!
7.1 题意
7.2 思路
7.3 代码

A. Iskander and Drawings

题意

给出一个由 ‘*’ 和 ‘#’ 构成的字符串，问由连续的 ‘#’ 构成的最长长度

思路

模拟{\color{yellow}模拟}

直接遍历，找最长的连续 ‘#’ 的长度即可

代码

#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;
    string s;
    cin >> s;

    int ans = 0, cnt = 0;
    for (char c : s) {
        if (c == '*') {
            cnt = 0;
        }
        else {
            ++cnt;
        }
        ans = max(ans, (cnt + 1) / 2);
    }
    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. Nikita and Books

题意

给出一个数组 aa，若 ai>1a_i > 1，可进行以下操作：ai=ai−1,ai+1=ai+1+1a_i = a_i – 1, a_{i+1} = a_{i+1} + 1，问，给出的数组 aa 能否最终成为一个严格递增数组

思路

模拟{\color{yellow}模拟}

最可能使其成为严格递增数组的模样为 1 2 3 4 ... (n−1) (n−2) m ,m≥n1 \ 2 \ 3 \ 4 \ … \ (n – 1) \ (n – 2) \ m \: \ ,m \geq n

若 ai≥ia_i \geq i, 则将多余的数保存起来，留给后面用

若 ai<ia_i < i, 则将之前保存的数分配 (i−ai)(i – a_i) 这么多给 aia_i ，若将全部的之前保存的数都给了 aia_i ，但他仍小于 ii，则输出 NONO

代码

#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;

    vector<LL> a(n + 1);

    LL tmp = 0;
    for (LL i = 1; i <= n; ++i) {
        cin >> a[i];
    }

    for (LL i = 1; i <= n; ++i) {
        if (a[i] > i) {
            tmp += a[i] - i;
        }
        else {
            LL p = min(tmp, abs(i - a[i]));
            a[i] += p;
            tmp -= p;
            if (a[i] < i) {
                cout << "NO" << endl;
                return;
            }
        }
    }

    cout << "YES" << endl;
}

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

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

C. Stepan and Permutation

题意

给出一个长度为 nn 的排列 pp 和两个整数 x,yx, y，若下标 i,ji, j 满足以下任意一个条件，则可以交换元素 pi,pjp_i, p_j:

  • |i−j|=x|i – j| = x
  • |i−j|=y|i – j| = y

问，是否可以使用任意数量的此操作对此排列进行排序，最后形成一个递增数列

思路（裴蜀定理）

当时我是猜的，去找 z=gcd⁡(x,y)z = \gcd(x, y)，若需要交换的两个下标 k=|i−j|，kk = |i – j|，k 能够被 zz 整除，则能够排序，否则不能。后来我查了一下，需要用到裴蜀定理（BeˊzoutBézout 定理），以下是一个简要证明：

裴蜀定理（Beˊzout 定理）{\color{yellow}裴蜀定理（Bézout \ 定理）}

对于 ∀a,b,设 d=gcd(a,b),总 ∃x,y,使得 ax+by=kd 成立 对于\ \forall a, b,\\ 设 \ d = gcd(a, b), \\ 总 \ \exists x, y, \\ 使得 \ ax+by = kd \ 成立

设 s=(ax+by) 集合中最小的正整数设 \ s = (ax+by) \ 集合中最小的正整数

d|a, d|b⇒d|(ax+by)⇒d|sd|a, \ d|b \Rightarrow d| (ax+by) \Rightarrow d|s

以上这步可以多说一下，举个例子帮助理解 :

若 a=2×3×5, b=3×5×7, d=gcd(a,b)=3×5若 \ a = 2 \times 3 \times 5, \ b = 3 \times 5 \times 7, \ d = gcd(a, b) = 3 \times 5

s=ax+by=k1×(2×3×5)+k2×(3×5×7)=(2 ˙k1+7 ˙k2)×(3×5)s = ax+by = k1 \times(2\times3\times5) + k2 \times(3 \times 5 \times7) = (2 \.\ k1 + 7 \.\ k2) \times(3 \times5)

可以看出，d|sd|s ，当然，这只是举个例子帮助理解，并不是在严格证明

设 q=⌊as⌋, r为余数⇒a÷s=q......r设 \ q = \left \lfloor \frac{a}{s}\right \rfloor , \ r为余数 \Rightarrow a \div s = q ……r

⇔r=a−sq=a−q(ax+by)=a(1−qx)+b(−qy)\Leftrightarrow r = a – sq = a – q(ax+by) = a(1-qx) + b(-qy)

s=ax+by，两者是同线性方程组，而 0≤r<s，s 为最小正整数⇒r=0s = ax+by，两者是同线性方程组，而 \ 0 \leq r < s，s \ 为最小正整数 \Rightarrow r = 0

⇒a−sq=0⇒a=sq⇒s|a，同理，s|b\Rightarrow a – sq = 0 \Rightarrow a =sq \Rightarrow s|a ，同理，s|b

⇒s|gcd(a,b)，即 s|d\Rightarrow s | gcd(a, b)， 即 \ s | d

以上这步推导也可以多说一下：

a=2×3×5, b=3×5×7a = 2 \times3\times5, \ b = 3\times5\times7

ss 要整除 aa ，ss 要整除 bb ，ss 一定会整除 gcd⁡(a,b)\gcd(a, b)，若有非 gcd⁡(a,b)\gcd(a, b) 的部分存在于 ss 的因数中，就比如 ss 中有 22 的话，ss 可以整除 aa ，但是无法整除 bb，假设 ss 硬是要也可以整除 bb，则说明 bb 中也有 22，既然 a,ba, b 中都有 22，则 gcd⁡(a,b)\gcd(a, b) 中不可能没有 22，所以，依然是 ss 中硬多出来的 22 除以 gcd⁡(a,b)\gcd(a, b) 被带出来的 22

s|d, d|s 两者同时成立，⇒s=d，ENDs|d, \ d|s \ 两者同时成立，\Rightarrow s = d，END

用人话说，裴蜀定理就是给出两个数 a, ba, \ b, 他们两的线性组合一定是他们两的最大公因数的倍数

ax+by=k ˙gcd(a,b)\color{yellow}ax+by = k \.\ gcd(a, b)

代码

#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, x, y;
    cin >> n >> x >> y;
    LL z = gcd(x, y);

    vector<LL> a(n + 1);
    for (LL i = 1; i <= n; ++i) {
        cin >> a[i];
    }

    for (LL i = 1; i <= n; ++i) {
        if (a[i] != i)
        {
            LL tmp = abs(a[i] - i);
            if (tmp % z != 0) {
                cout << "NO" << endl;
                return;
            }
        }
    }

    cout << "YES" << endl;
}

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

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

D. Yaroslav and Productivity

题意

给出两个数组分别为 aa ，bb，bib_i 代表的含义是将 a1,a2,...abia_1, a_2, …a_{b_i}这个区间中的数字都乘以 −1-1，对于每个 bib_i 你可以选或不选，问，最后数组 aa 的和可能的最大值

思路

思维{\color{yellow}思维}

将 bb 进行排序，可以看出 bb 将 aa 划分划分成了 （m+1）（m +1）段，前 mm 中的每一段你都可以选择反转或不反转，设 l=bi−1,r=bi，s l = b_{i-1}, r = b_i，s 为 aa 的前缀和数组，若 sr−sl≥0 s_r – s_l \geq 0 ，则不反转，若 sr−sl<0s_r – s_l < 0，则反转，统一起来，即为 |sr−sl||s_r – s_l|。每一部分都会选择反转（11）或不反转（00），最后，对于 bb 数组来说，则为 0 1 1 1 0 0 1 0 1 1 0 0 1 的形式，我们一定可以用相应的 bb 数组实现该 010 1 构成的数组。

我们只需要知道一定是可以实现的即可，因为真正写的代码只需要获取每一部分（除第 (m+1)(m + 1)部分）的绝对值，因为你无论是变还是不变，加在答案中的都是绝对值

代码

#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, m;
    cin >> n >> m;

    vector<LL> s(n + 1, 0), b(m + 1, 0);

    LL ans = 0;

    for (LL i = 1; i <= n; ++i) {
        cin >> s[i];
        s[i] += s[i - 1];
    }
    for (LL i = 1; i <= m; ++i) {
        cin >> b[i];
    }
    sort(b.begin() + 1, b.end());

    for (LL i = 1; i <= m; ++i) {
        LL l = b[i - 1];
        LL r = b[i];
        ans += abs(s[r] - s[l]);
    }

    ans += s[n] - s[b.back()];

    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;
}

E. Masha and the Garland

题意

给出一个由 0 1 构成的字符串，你可以进行以下操作：

  • 选取 [l,r],1≤l≤r≤n[l, r], 1 \leq l \leq r \leq n, 使得该区间中的字符全部翻转

给出 qq 次询问，每次给出一个区间 [L,R][L, R] 和一个整数 kk，问能否在 kk 此操作中使得 [L,R][L, R] 区间成为一个 01 严格交错的区间（比如 0101010101… or 1010101010…）

思路

实在没看懂官方题解，我就讲我那笨笨的思路好吧

对于给出的 01 字符串来说，他想变成的样子无非是 0101010… 或者 10101010… 我们就先讨论其中第一个

将原串与目标串进行比较，相等则为 0，不等则为 1，则出现一个新的数组 r，我们想让原串变成目标串，等价于让 r 全部变成 0 ，所进行的最少操作数。将连续的 1 看成一组，答案等于 1 的组数和。比如 r1 : 0 0 1 1 1 0 1 1 0 0 有两组 1 ，一种方案是 [3, 5], [7, 8]，令一种方案是 [3, 8], [6, 6]，操作数都为 2。我想说明的是一组一组地合并 1 一定是不劣的，因为无论你按身什么顺序合并，操作一次，最多只能减少一组 1，这个是跟操作顺序无关的。所以答案为 1 的组数。但是我们发现，它还可以变成 1010101… ，这样数组 r2 就会变成 r1 的翻转数组：1 1 0 0 0 1 0 0 1 1，这样 1 的组数为 3，在这两者中取个 min, 即为最终答案

但是我们发现可以整合一下，把连续的一块看成一组，答案为 ⌊组数2⌋\left \lfloor \frac{组数}{2} \right \rfloor ，但是块是不好标记的，分界线却是好标记的，我们可以转换成用分界点来推出答案

当 ri≠ri−1r_i \neq r_{i – 1} 时，标记 si=1s_i = 1, 用前缀和数组 ss 维护，答案为 ⌈sr−sl2⌉\left \lceil \frac{s_r – s_l}{2}\right \rceil

这道题的确不是我喜欢的类型，我补完了都觉得跟没补没啥区别，既没学到什么，也没什么成就感，就他的每一步都透露出一丝不可言说的意味

官方思路

问了官老师，以下是他解释的官方思路，这玩意儿不比官方解释的好吗

题解的意思是：
第一段：将原字符串 s 按最大可能的”美丽串“划分方式，分割出所有美丽串
比如：s = 1000110100101
那么第一段会将 s 划分为：10-0-01-1010-0101，这 5 个 block

第二段：
如果我们翻转一段”内部 block“，那么 block 的数量就会减少 2，比如：
10-0-01-1010-0101
10[edge block]-0[internal block]-01[internal block]-1010[internal block]-0101[edge block]
如果我翻转了第 2 个 block ”0“，那么 block 的划分就会变成：
10101-1010-0101
因此 block 的个数会从 5 变为 3，减少了 2
如果我们翻转一段”边缘 block“，那么 block 的个数就会减少 1，比如：
10-0-01-1010-0101
翻转第 1 个 block ”10“，block 划分会变为：
010-01-1010-0101
block 个数从 5 变为 4，减少了 2
所以如果有内部 block 时选择边缘 block 翻转是更差的，优先选择内部 block 进行翻转

第三段：因此，最优策略是不断翻转第二个 block（如果存在内部 block，那么第 2 个 block 一定是内部 block，如果不存在内部 block，那么第 2 个 block 一定是边缘 block，所以只要翻转第二个 block，就自然保证了优先选择内部 block 进行翻转，其次选择边缘 block 翻转）
每选择一次第二个 block，block 数都会减少 2（这句话并不严谨，因为如果第二个 block 是边缘 block，那么翻转后 block 数只会减少 1）
所以最少操作次数是 cnt/2 下取整（虽然上一句话不严谨，但这个结论是对的）

第四段：用前缀和快速计算区间 block 数，算出最少翻转次数，与 k 进行大小比较

代码

#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, q;
    cin >> n >> q;
    string str, t = " ";
    cin >> str;
    str = ' ' + str;

    for (int i = 1; i <= n; ++i)
    {
        t += char(i % 2) + '0';
    }

    string r = "#";
    for (int i = 1; i <= n; ++i)
    {
        r += char(str[i] == t[i] ? 0 : 1) + '0';
    }

    vector<int> s(n + 1);
    for (int i = 1; i <= n; ++i)
    {
        s[i] = s[i - 1] + (r[i] != r[i - 1]);
    }

    while (q--)
    {
        int l, r, k;
        cin >> l >> r >> k;
        int ans = (s[r] - s[l] + 1) / 2;
        if (k >= ans)
        {
            cout << "YES" << endl;
        }
        else
        {
            cout << "NO" << endl;
        }
    }
}

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

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

F. Anya Loves Trees!

题意

给出一棵 nn 个节点的树， 第 ii 个节点有其对应的价值 aia_i，对于一个节点来说，他的孩子节点可以做无数次循环左移（从第二个点到后面每个点都往左移一个，第一个点移到最后），问，最后将所有叶子结点按从左到右的顺序，他们对应的 aia_i 能否成为一个单调递增序列（保证每个 aia_i 都不相同）

思路

树形递归{\color{yellow}树形递归}

说真的，我当时读这题的时候就火大，感觉他说的不清不楚，但没办法，我好像也说不清楚，我只能建议你多读几遍，读清楚了，后面的才好理解。

对于节点 uu 来说，假设他的孩子可能是一段一段的，最小值 LiL_i 和最大值 RiR_i，找到在 LiL_i 中最小的那个，因为循环左移后，左端点最小值一定是第一个，然后再进行遍历，若出现第 ii 个的左端点小于第 i−1i – 1 个的右端点，则无论如何移动，都无法得到单调递增序列，直接输出 falsefalse, 退出递归。若成功遍历完，则对于 uu 来说只需保留最小的左端点和最大的右端点，然后重复操作

对于一层来说时间复杂度是 O(n)O(n)，共有 log⁡n\log n 层，所以总的时间复杂度是 O（nlog⁡n）O（n \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;

struct Node {
    LL l, r;
};

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

    vector<vector<LL>> G(n + 1);
    vector<LL> p(n + 1);

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

    for (LL i = i = 1; i <= n; ++i) {
        cin >> p[i];
    }

    vector<Node> t(n + 1);

    auto dfs = [&](auto &&dfs, LL u) -> bool
    {
        vector<Node> s;
        for (LL v : G[u])
        {
            if(!dfs(dfs, v))
                return false;
            s.push_back({t[v]});
        }

        LL l = INF, r = -1, L;
        LL m = s.size();
        for (LL i = 0;i  < m; ++i) {
            if (s[i].l < l) {
                L = i;
            }
            l = min(l, s[i].l);
            r = max(r, s[i].r);
        }

        if (s.size() == 0)
        {
            t[u].l = p[u];
            t[u].r = p[u];
        }
        else
        {
            t[u].l = l;
            t[u].r = r;
        }

        for (LL i = 1; i < m; ++i)
        {
            if (s[(i + L) % m].l < s[(i - 1 + L) % m].r)
            {
                return false;
            }
        }

        return true;
    };

    if (dfs(dfs, 1)) {
        cout << "YES" << endl;
    }
    else {
        cout << "NO" << endl;
    }
}

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

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

Leave a Comment

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