Codeforces Round 1107 (Div. 3)

by JiuQiin Codeforces, 题解on Posted on
「有死之隙是因为惧怕死亡，惧怕死亡是因为有挂念的事与人吧。」
— 流月针武器故事 · 原神
反思

我不知道是这场比赛有什么大病还是我有什么大病，是，我是因为期末周两周没写代码了（因为本人不是计算机相关的专业），但是，我在打这场虚拟赛的时候，卡 B 就算了，不是，卡 A 就有点过分了吧。还好还好，当时忙着复习，没打这场，我把后面C， D，E 做了再回过头来看，他妈的，还是不会 A，B。真的难绷。是，我是数学不好，但他妈起码也是在平均水平吧，我现在真的有点怀疑了

Contents hide
1 A. Divide and Conquer
1.1 题意
1.2 思路
1.3 代码
2 B. Good times Good times
2.1 题意
2.2 思路
2.3 代码
3 C. RemovevomeR
3.1 题意
3.2 思路
3.3 代码
4 D. An Alternative Way
4.1 题意
4.2 思路
4.3 代码
5 E. Fair and Square
5.1 题意
5.2 思路
5.3 代码
6 F. A Bit Odd
6.1 题意
6.2 思路
6.3 代码

A. Divide and Conquer

什么意思？！Codeforces BetterCodeforces \ Better 你什么意思？你自己来读读这两段话，这 tmtm 是一个意思吗？什么叫除以，什么叫约数

题意

给出 xx, yy，可做任意次 xz (xmod  z≡ 0)\frac{x}{z} \ (x \mod \ \ z \equiv \ 0)，若最后能让 x=yx = y，则输出 YESYES，否则输出 NONO

思路

直接判断 xx 能否被 yy 整除，若能，则输出 YESYES，否则输出 NONO

代码

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
typedef long long LL;

void solve() {
    int x, y;
    cin >> x >> y;
    if (x % y == 0) {
        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;
}

B. Good times Good times

题意

好整数的定义：在十进制下，只含有两种及以下的数字

给出一个好整数 xx，请在另找到一个好整数 yy ，使得 x×yx \times y 也是好整数

思路

妙啊，真的很妙啊。设 dd 为 xx 的位数，y=10d+1, z=x×y=x×(10d+1)=x×10d+xy = 10 ^d +1, \ z = x \times y = x \times(10^d + 1) = x \times 10^d + x，其含义就是将 xx 整体向左移 dd 位，腾出位置，再加上原 xx 值，那整体看上去，用字符串来理解就是 “x+x““x + x”

很多时候，像这种关于位的构造，其数据范围或多或少会给出点提示，就比如 1≤x≤1e8, 2≤y≤1e91 \leq x \leq 1e8, \ 2 \leq y \leq 1e9，yy 比 xx 多的一位就是用来放置 11 的

代码

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
typedef long long LL;

void solve() {
    int x, y =1;
    cin >> x;

    while (x) {
        y *= 10;
        x /= 10;
    }

    y += 1;
    cout << y << endl;
}

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

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

C. RemovevomeR

题意

每次可任选一个回文子串，删除其中一个字符，问最后至少能剩多少个字符

思路

先猜，最后答案要么为 1 要么为 2，为啥？都说是猜的了

假设 0 的个数大于等于 1，先删 0 ，只要有两个相同的 0 ，不一定挨在一起，因为这两个 0 之间无论有多少个 1 ，都是一个回文串，删除其中一个 0，重复进行该操作，最后一定还剩一个 0 ，只要这个 0 不是第一个或者最后一个，并且 1 的个数大于等于 2（呃，1 的个数一定大于等于 2，不然 0 就在两端了），那一定可以删掉这个 0，然后就变成了只剩一种字符的情况。无脑去删，最后一定至少剩一个 1

以上，已经说明了 1 和 2 分别存在的情况，每次删 0 ，你都有意识地去删两端的 0 ，尽可能使最后剩下的 0 不位于两端，这样最后的答案为 1。但如果每次删两端的 0 ，但最后仍剩下一个 0 位于第一个或者最后一个的话，答案就是 2。什么时候会出现这种情况？111110000 or 0000111111111110000 \ or\ 0000111111 ，1 在一堆，0 在一堆，其余情况答案都为 1。先删 1 也是同样的做法

代码

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
typedef long long LL;

void solve() {
    int n;
    cin >> n;
    string s;
    cin >> s;
    vector<char> a;

    for (char c : s) {
        if (!a.empty() && a.back() == c) {
            continue;
        }
        a.push_back(c);
    }

    if (a.size() == 2) {
        cout << 2 << endl;
    }
    else {
        cout << 1 << endl;
    }
}

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

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

D. An Alternative Way

题意

给出两个数组 aa 和 bb ，可进行以下操作任意次：

选择一个区间 [l,r][l, r] ，对于区间中的下标 ii，若 （i−l）（i – l）为偶数，则 ai+=1a_i += 1， 若 (i−l)(i – l) 为奇数，则 ai−=1a_i -= 1，问最后 aa 数组能否变成 bb 数组

思路

发现，对于一个区间 [l,r][l, r] 来说，第一个数的下标 (i−l)(i – l) 总是等于 00，为偶数，总是 ai+=1a_i += 1 ，其含义就是，我们可以对任意的 aia_i 加任意次，但如果要减的话，就必须带上前一个数，意思就是必须从前一个开始，或者前三个，或者前五个……只有保证 (i−l)(i – l) 为奇数，aia_i 才能减去某个值，我们不往前看那么多步，就单看前一步，如果当前必须要减，则我们将前一个下标作为 ll ，即 l=i−1l = i – 1，则 aia_i 减多少， ai−1a_{i – 1} 就要相应的加上多少，现在 ai=bia_i = b_i，左移，去讨论 ai−1a_{i – 1}。只要当前 ai>bia_i > b_i ，则进行 ai−=x, ai−1+=xa_i -= x, \ a_{i – 1} += x ，但如果 ai≤bia_i \leq b_i ，则跳过，最后看 a0a_0 是否有值，如果有的话，说明后面一定有要减去的值，迫使 a0a_0 必须要加，但 a0a_0 明显做不了任何操作，所以输出 NONO，反之，则输出 YESYES

代码

#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),b(n + 1);

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

    LL tmp = 0;
    for (LL i = n; i >= 1; --i) {
        if (a[i] > b[i]) {
            tmp = a[i] - b[i];
        }
        else {
            tmp = 0;
        }
        a[i - 1] += tmp;
    }

    if (a[0]) {
        cout << "NO" << endl;
    }
    else {
        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;
}

E. Fair and Square

题意

给出一个由 nn 个顶点构成的双向连边的树，给出点的权值 aia_i，定义 p(u,v)p(u, v) 为 uu 到 vv 这条路径上点权值的乘积和。定义一个无序三元组 p(u,v,w)=p(u,v)⋅p(v,w)⋅p(u,w)p(u, v, w) = p(u, v) \cdot p(v, w) \cdot p(u, w)，p(u,v,w)p(u, v, w) 为完全平方，问有多少个满足条件的无序三元组

思路

发现，将三条路相乘，看最后是否是完全平方取决于相交点是否是完全平方，在相交点他们会经过三次，其余点都只经过两次，分类讨论（一种颜色代表一条路径， 标红星的为 aia_i）：

  • 三个点分别位于三个不同的子树中
  • 两点位于 aia_i 不同的子树中，一点位于 aia_i 或非 aia_i 的点集中
  • 一点位于一颗子树中，一点位于 aia_i ，一点位于非 aia_i 子树的点集中

我当时想的时候是这么一个顺序，但写的话就得反着来，先预处理出每个点子树总的大小 sz[u]sz[u] 以及每棵子树具体的大小

  • 一点位于一颗子树中，一点位于 aia_i ，一点位于非 aia_i 子树的点集中
ans=(sz[u]−1)⋅(n−sz[u])ans = (sz[u] – 1) \cdot (n – sz[u])

  • 两点位于 aia_i 不同的子树中，一点位于 aia_i 或非 aia_i 子树的点集中

处理到第 vv 棵子树，第 vv 棵必选，即一定会从第 vv 棵子树中选取一个，另一个在其前面的子树中选取一个，用前缀和 ss 数组预处理出前面的子树大小，方案数为 son[u][v]⋅s[v]son[u][v] \cdot s[v]

  • 三个点分别位于三个不同的子树中

在第二种情况的基础上可以得出处理到第 vv 棵树时，分别从两颗子树中选取两个点的方案数，第 vv 棵必选，若再对第二种情况的结果进行前缀和，得到的则是分别从两颗子树中选取两个点的方案数，第 vv 棵可选可不选，然后再将其结果乘以 sun[u][v]sun[u][v] ，得到第 vv 棵必选，分别从三棵不同的子树中选取三个点的方案数

代码

#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), sz(n + 1, 0);

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

    vector<vector<LL>> G(n + 1), son(n + 1);
    for (LL i = 1; i < n; ++i) {
        LL u, v;
        cin >> u >> v;
        G[u].push_back(v);
        G[v].push_back(u);
    }

    auto dfs = [&](auto &&dfs, LL u, LL par) -> void
    {
        sz[u] += 1;
        son[u].push_back(0);
        for (auto v : G[u])
        {
            if (v == par)
                continue;
            dfs(dfs, v, u);
            sz[u] += sz[v];
            son[u].push_back(sz[v]);
        }
    };

    dfs(dfs, 1, 0);

    auto check = [](LL x) {
        LL y = sqrt(x);
        return y * y == x;
    };

    LL ans = 0;
    for (LL u = 1; u <= n; ++u) {
        if (!check(a[u]))
            continue;
        LL m = son[u].size() - 1;
        if (m >= 1) {
            ans += (sz[u] - 1) * (n - sz[u]);
        }
        vector<LL> s(m + 1, 0), s1(m + 1, 0);
        if (m >= 2) {
            LL tmp = 0;
            for (LL v = 1; v <= m; ++v) {
                s[v] = s[v - 1] + son[u][v];
                    tmp += son[u][v] * s[v- 1];
                    s1[v] = tmp;
            }
            ans += tmp * (n - sz[u] + 1);
        }
        if (m >= 3) {
            LL tmp = 0;
            for (LL v = 3; v <= m; ++v) {
                tmp += son[u][v] * s1[v - 1];
            }
            ans += tmp;
        }
    }

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

F. A Bit Odd

题意

有一个长度为 nn 的二进制字符串，AliceAlice 和 BobBob 轮流删子序列，每次可以删的标准是：子序列的逆序对个数和为奇数，AliceAlice 先手，问最后谁赢

思路

发现，如果一开始就是全 0 或者全 1，先手必败；那如果先手走后，留下的是此必败的局面，则先手必胜，那怎么样才能留下全 0 或者全 1 的局面呢？先假设剩下的全是 0，则会删除全部的 1，在 1 与 1 之间有若干个 0 可选可不选，若选取该 0 ，则逆序对的个数增加该 0 前面 1 的个数之和，所以，要使逆序对个数为奇数，只要有一个 0 的前面的 1 的个数之和为奇数，则选取该 0，剩下的则全是 0 或者空集，先手必胜。若先选取全部的 0 剩下的全是 1 也是同样的道理，只要有一个 1 ，他后面的 0 的个数之和为奇数则先手必赢（由于逆序对的原因，所以这个 1 只会对后面的 0 有贡献，前面的 0 无法跟这个 1 形成逆序对，所以没有影响）

但，若所有的 0 前面 1 的个数都为偶数，所有的 1 后面 0 的个数也都为偶数，则无法形成全 1 或者全 0 的局面，这是种什么情况呢？

(0)02a112b102a212b2⋯(1)(ai,bi≥1)(0)0^{2a_1}1^{2b_1}0^{2a_2}1^{2b_2}\cdots(1) \qquad (a_i, b_i \geq 1)

其含义就是偶数个 0 与偶数个 1 交替出现，但开始的 0 和最后的 1 的个数可能为奇数，但这并不影响，因为这两处不对逆序对的个数做出贡献，所以，更严格一点来说，排除掉开头的 0 和末尾的 1 的影响，最后的形式应该是

12a102b112a202b2⋯(ai,bi≥1)1^{2a_1}0^{2b_1}1^{2a_2}0^{2b_2}\cdots \qquad(a_i, b_i \geq 1)

这种情况就是先手必败态，为啥？

将各自挨在一起的偶数个 0 看成一组，各自挨在一起的偶数个 1 看成一组，以此类推，形成一组一组 01 交错的的形式。假设该组都是 0 ，先手只要选取一组中奇数个 0，则一定剩下奇数个 0, 但如果选取偶数个 0 ，则剩下偶数个 0，选取 1 的时候也是同理。简单点来说，就是 AliceAlice 选啥，BobBob 就会跟着选啥 ，所以只要 AliceAlice 最后选出来的子序列逆序对为奇数，则剩下的字符串的逆序对也一定为奇数，所以只要AliceAlice 删完子序列后，BobBob 一定可以删完全部的字符串，则后手必赢

代码

#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;
    s = " " + s;

    int l = 1, r = n;
    while (l <= n && s[l] == '0')
        ++l;
    while (r >= 1 && s[r] == '1')
        --r;

    if (l > r) {
        cout << "Bob" << endl;
        return;
    }
    
    int cnt = 1, f = 0;
    for (int i = l; i < r; ++i) {
        if (s[i + 1] == s[i]) {
            ++cnt;
        }
        else {
            if (cnt % 2) {
                f = 1;
                break;
            }
            cnt = 1;
        }
    }

    if (cnt % 2) {
        f = 1;
    }

    cout << (f ? "Alice" : "Bob") << endl;
}

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

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

Leave a Comment

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