Educational Codeforces Round 192 (Rated for Div. 2)

“山谷的最低点正是山的起点。”

— 林清玄 · 林清玄

一些废话

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

Contents hide

3 B. Predominant Frequency Division

4 C. Unstable Elements

5 D. Two Digit Strings

5.1 题意

5.2 思路

5.3 代码

A. Bigrams

题意

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

思路

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

至少有两种字符的个数大于等于 $2$ ，比如 $abab$ 可构成相同的双字符 $ab$
至少有一种字符的个数大于等于 $3$ ，比如 $aaa$ 可构成相同的双字符 $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() {
    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;
}

#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， 3$ 构成的数组 $a$ ，问能否将数组 $a$ 分成三部分，满足以下要求：

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

思路

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

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

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

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

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

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

#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$ ，每次可以执行以下操作：

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

保证输入规则： $a_{1} \leq a_{2} . . . \leq a_{n}, a_{i} \leq n$

思路

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

【C. Unstable Elements-哔哩哔哩】

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

维护三个东西：

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

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

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

#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

题意

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

思路

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

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

$eg$ .

idx	1	2	3	4	5
a[i]	5	7	2	4	6
s[i]	5	2	4	8	4
合并 a[1], a[2] 后的 s[i]		2	4	8	4
合并 a[2], a[3] 的s[i]	5		4	8	4
合并 a[3], a[4] 后的 s[i]	5	2		8	4
合并 a[4], a[5] 后的 s[i]	5	2	4		4

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

$(sa_i – sa_{i – 1} + 10) \mod\: 10 = a_i$ ，每个 $a_i$ 都依赖前一个 $a_{i – 1}$ ，只要 $a_0$ 固定，数组 $sa$ 固定，则数组 $a$ 固定

代码

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

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

一	二	三	四	五	六	日
		1	2	3	4	5
6	7	8	9	10	11	12
13	14	15	16	17	18	19
20	21	22	23	24	25	26
27	28	29	30	31

一些废话

A. Bigrams

题意

思路

代码

B. Predominant Frequency Division

题意

思路

代码

正解代码

C. Unstable Elements

题意

思路

代码

正解代码

D. Two Digit Strings

题意

思路

代码

Leave a Comment Cancel