Educational Codeforces Round 192 (Rated for Div. 2)

by JiuQiin Codeforces, 题解on Posted on
“山谷的最低点正是山的起点。”
— 林清玄 · 林清玄

一些废话

这场打的很不好，我真不知道自己擅长啥，数学不好，思维也不好，现在连实现代码也实现不了了是吗。CC 题最开始读题读的还是对的，写着写着莫名跑偏了，直接理解错题意了，导致写了三版都是错的，最后耐下性子再读一遍，在足够多的样例的帮助下，总算，半猜半想，写出来了。得，我知道我擅长啥了，猜。tmdtmd，问题是这道题也不难啊，想了四五版，最后一版居然还是跟第一版思路最接近的，感情说，绕了一大圈，终是回到了原地，也算是不忘初心了。

Contents hide
1 一些废话
2 A. Bigrams
2.1 题意
2.2 思路
2.3 代码
3 B. Predominant Frequency Division
3.1 题意
3.2 思路
3.3 代码
3.4 正解代码
4 C. Unstable Elements
4.1 题意
4.2 思路
4.3 代码
4.4 正解代码
5 D. Two Digit Strings
5.1 题意
5.2 思路
5.3 代码

A. Bigrams

题意

给出 kk 个数字，每个数字代表一种字符出现的次数，这 kk 种字符都不同，将这些字符构成一个字符串，问是否存在两个双字符相同

思路

有两种情况一定构成双字符：

  • 至少有两种字符的个数大于等于 22，比如 abababab 可构成相同的双字符 abab
  • 至少有一种字符的个数大于等于 33，比如 aaaaaa 可构成相同的双字符 aaaa

代码

#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 f = 0, cnt =0 ;
    for (LL i = 1; i <= n; ++i) {
        LL x;
        cin >> x;
        if (x >= 3) {
            f = 1;
        }
        if (x == 2) {
            ++cnt;
        }
        if (cnt >= 2) {
            f = 1;
        }
    }
    if (f) {
        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. Predominant Frequency Division

题意

给出由 1，2，31， 2， 3 构成的数组 aa，问能否将数组 aa 分成三部分，满足以下要求：

  • 对于第 ii 部分，大于 ii 的个数要小于等于该部分的一半
  • 第三部分不能为空集

思路

1 和 3 放在第一部分或者放在第二部分都是等价的，1 比 1 抵消，如果有多的 3，最好是放在第三部分，但是如果第一部分的 1 有多余，并且可以帮助消耗掉一些 3，那就帮助第二部分消耗掉一些，这是在帮助第二部分，并不是在抢夺第三部分，因为如果第二部分的 3 多了，会让第二部分的 1 和 2 也相应变多，抢夺第三部分。但是第一部分遇到的是 2，就应该放给第二部分，因为对于第一部分来说，一个 1 只能消耗一个 3 ，1 还会用来消耗 2，但是第二部分的 1 和 2 都会用来消耗掉 3，把 2 放在第二部分明显更容易结束战局，开启第三部分，呃，有点混乱

我们还是来说正解的思路吧，分别给 1231 \:2 \: 3 附上权值：

对于第一部分，w1(ai)={1,ai=1−1,ai=2 or ai=3w_1(a_i)= \begin{cases} 1, &a_i = 1\\ -1, & a_i =2 \ or \ a_i = 3 \end{cases}

对于第二部分，w2(ai)={1,ai=1 or ai=2−1,ai=3w_2(a_i)= \begin{cases} 1, &a_i = 1 \ or \ a_i = 2\\ -1, & a_i = 3 \end{cases}

对于第三部分，只要不是空集就好

对于第一部分和第二部分分别做一个前缀和，s1is1_i, s2is2_i，只要当 s1i≥0s1_i \geq0 时，去判断是否存在j>i,s2j−s2i≥0 j > i, s2_j – s2_i \geq 0 ，并且 j<n j < n，即可。但问题是，如果每次遇到 s1i≥0s1_i \geq 0 都要去判断一下 s2j−s2i≥0s2_j – s2_i \geq0 ，时间复杂度是 O(n2)O(n^2) ，发现，对于 s2js2_j 其实有很多重合部分，我们其实只是想知道是否存在 s2j−s2i≥0s2_j – s2_i \geq 0，不一定要在 s1i≥0s1_i \geq 0 的时候去判断，只需去保存最小的 s2is2_i ，jj 仍然往后走，ii 只要我们保证他是在 s1i≥0s1_i \geq 0 的时候出现的即可

代码

#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<int> a(n+ 1, 0), c(5, 0);

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

    int f = 0, idx =0 ;
    for (int i = 1;i  <= n; ++i) {
        if (c[1] > c[2] + c[3] && c[1] != 0 && a[i] != 3) {
            f = 1;
            idx = i;
            break;
        }
        if (c[1] == c[2] + c[3] && c[1] != 0) {
            f = 1;
            idx = i;
            break;
        }
        ++c[a[i]];
    }

    if (!f) {
        cout << "NO" << endl;
        return;
    }

    
    c[1] = c[2] = c[3] = 0, f = 0;
    for (int i = idx; i <= n; ++i) {
        if (c[1] + c[2] >= c[3] && c[1] + c[2] != 0)
        {
            f = 1;
            idx = i;
            break;
        }
        ++c[a[i]];
    }

    if (!f)
    {
        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;
}

正解代码

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

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

    for (LL i = 1; i <= n; ++i) {
        s1[i] = s1[i - 1] + (a[i] == 1 ? 1 : -1);
        s2[i] = s2[i - 1] + (a[i] == 3 ? -1 : 1);
    }

    LL mn = INF;
    for (LL i = 1; i < n; ++i) {
        if (s2[i] - mn >= 0) {
            cout << "YES" << endl;
            return;
        }
        if (s1[i] >= 0) {
            mn = min(mn, s2[i]);
        }
    }

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

C. Unstable Elements

题意

给出一个数组 a 和一个整数 k，每次可以执行以下操作：

  • 标记该数组中每个与其左邻不相等的数字，如所有满足 ai≠ai+1 的 i
  • 要么统一删除满足以上要求的 ai，要么统一复制满足以上要求的 ai

保证输入规则：a1≤a2 . . .≤an,ai≤n

思路

发现，每次整体删除数字，直到遇到一组出现次数相同的被删完，然后再复制回去才有可能出现新的方案，所以我们先记录每个数字出现的次数，然后保存同一种出现次数对应的数字的个数，这个是为了反推回去，然后我们从 1 开始递增判断出现次数大于等于 i 的种数。唉，我没招了，我真没招了，我不知道怎么讲才能讲得清楚，所以最后录了个视频，我可是专门为了你，发布了哔站第一个视频啊（呃，其实是为了视频不占内存）

【C. Unstable Elements-哔哩哔哩】

以上是我的思路，以下是正解的思路，我个人是觉得正解的更好理解

维护三个东西：

  • lenslens : 每个数字出现的次数
  • dd : 被破坏的组分别乘以他们对应数字的出现次数之和（将相同数字看成一组）
  • qq : 还剩多少组

每次都去试探将一种出现次数的数字都置为 11 次，看剩余的数字总数（n−d−x⋅q）（n – d – x \cdot q）是否会小于等于 kk，如果是，然后再返回去看看是否能到达 kk，我觉得有句话很形象地描述了该点：事前留一线（都置为 11），事后好相见（是否为 kk）

代码

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

    int sm = 0;
    vector<int> a(n + 1, 0), b(n + 1, 0), cnt(n + 1, 0), cnt1(n+ 1, 0);
    for (int i = 1; i <= n; ++i) {
        int x;
        cin >> x;
        a[x]++;
        sm++;
    }

    for (int i = 1; i <= n; ++i) {
        if (a[i]) {
            cnt[a[i]]++;
        }
    }

    vector<int> sf(n + 2, 0);
    for (int i = n; i >= 1; --i) {
        sf[i] = sf[i + 1] + cnt[i];
    }

    set<int> res;
    for (int i = 1; i <= n && sm >= 0; ++i) {
        if (sf[i] != 0 && k >= sm && (k - sm) % sf[i] == 0) {
            res.insert(sf[i]);
        }
        sm -= sf[i];
    }

    cout << res.size() << endl;
}

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

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

正解代码

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

    vector<int> a(n), lens;
    for (int i = 0;i < n; ++i)
        cin >> a[i];

    int cur = 1;
    for (int i = 1; i < n; ++i) {
        if (a[i] != a[i - 1]) {
            lens.push_back(cur);
            cur = 1;
        }
        else {
            ++cur;
        }
    }
    lens.push_back(cur);

    sort(lens.begin(), lens.end());

    int m = lens.size();
    int i = 0, d =0, ans =0;
    while (i < m) {
        int len = lens[i];
        int x = len - 1;
        int q = m - i;
        int curLen = n - d - x * q;
        if (curLen <= k && (k - curLen) % q == 0) {
            ++ans;
        }
        int j = i;
        while (j < m && lens[j] == len) {
            d += lens[j];
            ++j;
        }
        i = j;
    }

    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. Two Digit Strings

题意

给出两个字符串 aa 和 bb，你可以进行将任意两个相邻的数字合并为模 10 的余数的操作任意次，直到 aa 和 bb 相等，问 aa 和 bb 相等的最长长度，若永远不能相等，则输出 −1-1

思路

对数组 aa 和 bb 分别作在模 1010 的条件下的前缀和，发现，每次进行合并操作实则是在前缀和数组中进行删除操作，所以，问题就转换成了在两个前缀和数组中选择尽可能多的相同的数字，问最多有多少个，即求最长公共子序列问题

为什么可转换成在模 1010 意义下的前缀和数组呢？

egeg.

idx012345
a[i]057246
s[i]052484
合并 a[1], a[2] 后的 s[i]02484
合并 a[2], a[3] 的s[i]05484
合并 a[3], a[4] 后的 s[i]05284
合并 a[4], a[5] 后的 s[i]05244

那为什么前缀和数组相同就代表最后的 aa ， bb 两个数组相同呢？

(sai−sai−1+10)mod10=ai(sa_i – sa_{i – 1} + 10) \mod\: 10 = a_i，每个 aia_i 都依赖前一个 ai−1a_{i – 1}，只要 a0a_0 固定，数组 sasa 固定，则 数组 aa 固定

代码

#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() {
    string a, b;
    cin >> a >> b;

    LL na = a.size(), nb = b.size();
    a = ' ' + a;
    b = ' ' + b;

    vector<LL> fa(na + 1, 0), fb(nb + 1, 0);
    for (LL i = 1; i <= na; ++i) {
        fa[i] = (fa[i - 1] + (a[i] - '0')) % 10;
    }
    for (LL i = 1; i <= nb; ++i) {
        fb[i] = (fb[i - 1] + (b[i] - '0')) % 10;
    }

    if (fa.back() != fb.back()) {
        cout << -1 << endl;
        return;
    }

    vector<vector<LL>> dp(na + 1, vector<LL>(nb + 1, 0));
    for (LL i = 1; i <= na; ++i) {
        for (LL j = 1; j <= nb; ++j) {
            dp[i][j] = max(dp[i][j], dp[i - 1][j]);
            dp[i][j] = max(dp[i][j], dp[i][j - 1]);
            if (fa[i] == fb[j])
                dp[i][j] = max(dp[i][j], dp[i - 1][j - 1] + 1);
        }
    }
        
    cout << dp[na][nb] << 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

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