Blog - Floating Ocean
0%

Codeforces - Round 344 Div 2

发表于 更新于
本文字数： 5.5k 阅读时长 ≈ 10 分钟
阅读次数： Valine：

Practice.

什么陈年老题目（（

A. Interview

题意

给定两个长度相等的序列，任选一段区间，输出区间内各序列值进行按位或之后的和。

思路

考虑到数据范围，直接暴力即可。

时间复杂度：

对应AC代码

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define pii pair<int, int>

const int N = 2e5 + 10, inf = 0x3f3f3f3f;

int a[N], b[N];

signed main() {
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    int n;
    cin >> n;
    for(int i=0;i<n;i++) cin >> a[i];
    for(int i=0;i<n;i++) cin >> b[i];
    int ans = 0;
    for(int i=0;i<n;i++){
        int ca = 0, cb = 0;
        for(int j=i;j<n;j++){
            ca |= a[j];
            cb |= b[j];
            ans = max(ans, ca + cb);
        }
    }
    cout << ans << '\n';
}

过于打卡

B. Print Check

中文版：题目详情 - 简单题 - FJNU (fjnuacm.top)

题意

给定一个 的矩阵，对于 个操作，输出操作后的矩阵。

定义操作为选择一行或一列，将该行或该列的值改为指定值，存在覆盖的情况。

思路

首先，不可以模拟，只要 够大，一定会 。

其次，对于一个点，它最后的值只和最后一次对它所在的行或列的操作有关。

因而，我们不妨记录每行的操作，以及操作时间，在最后输出的时候，判断涉及到该点的行操作和列操作的时间，并输出最后操作后的值。

时间复杂度：

对应AC代码

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define pii pair<int, int>

const int N = 2e5 + 10, inf = 0x3f3f3f3f;

pii r[N], c[N];

signed main() {
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    int n, m, k;
    cin >> n >> m >> k;
    for(int i=1;i<=k;i++){
        int x, p, a;
        cin >> x >> p >> a;
        if(x == 1) r[p] = {i, a};
        else c[p] = {i, a};
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cout << (r[i].first > c[j].first ? r[i].second : c[j].second) << ' ';
        }
        cout << '\n';
    }
}

怎么就做到原题了（（

C. Report

题意

给定一个数组 ，输出操作后数组的结果。

定义一次操作为选择一个右端点 ，将 内的数升序或降序排列，排列方式取决于输入， 为非降序， 为非升序。

思路

剪枝

首先，这些操作存在覆盖，也就是说，后面的操作可以使前面的操作无效。

对于最后一个操作，若前面的操作的区间比它小，那么这些操作均无效。推广可得，我们只需从后往前拿出包含最后一个操作且操作区间递增的操作，其余不考虑即可。

输出

考虑到直接暴力排序的时间复杂度过大，我们不妨观察一下每次操作的特点：

当我们对大区间操作后，其与次大值区间的补集就唯一确定了，不会随着后续操作而改变，所以我们不妨直接从后往前放数字。

对于一个区间内的数，我们不妨直接将其升序排序，若这个补集需要非降序，那么把右端点的数字取出，否则把左端点的数字取出，依次放入这个补集所在的区域即可。

当然，最大的操作之后的数直接输出，不参与排序。

时间复杂度：

对应AC代码

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define pii pair<int, int>

const int N = 2e5 + 10, inf = 0x3f3f3f3f;

int a[N];
pii op[N], opt[N];

signed main() {
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    int n, tm, m = 0;
    cin >> n >> tm;
    for(int i=0;i<n;i++) cin >> a[i];
    for(int i=0;i<tm;i++) cin >> opt[i].second >> opt[i].first;
    int st = -1;
    for(int i=tm-1;i>=0;i--){
        if(st != -1 && opt[i].first <= st) continue;
        st = opt[i].first;
        op[m ++] = opt[i];
    }
    sort(op, op + m, greater<>());
    vector<int> ans(n);
    for(int i=n-1;i>=op[0].first;i--) ans[i] = a[i];
    sort(a, a + op[0].first);
    int l = 0, r = op[0].first - 1;
    for(int i=0;i<m-1;i++){
        for(int j=op[i].first-1;j>=op[i+1].first;j--){
            if(op[i].second == 2) ans[j] = a[l ++];
            else ans[j] = a[r --];
        }
    }
    for(int j=op[m - 1].first-1;j>=0;j--){
        if(op[m - 1].second == 2) ans[j] = a[l ++];
        else ans[j] = a[r --];
    }
    for(int i=0;i<n;i++) cout << ans[i] << ' ';
}

能用数据结构么

D. Messenger

题意

定义对只有小写字母的字符串的一种压缩方式为选取任意连续相等的子序列，将其替换为 个数字母。

如 可替换为 ，也可以替换为 。

给定两个压缩后的字符串 ，对于两者的原字符串，输出 在 中出现了几次。

思路

首先，若要在 的复杂度内解出字符串的查找，我们需要用到 算法。

其次，我们不能直接调用 ，因为可能出现开头或结尾的字母数量小于 对应字母的数量的情况。如 和 。

但是，我们可以确定的是，去掉两端的字母，中间的序列是一定相同的，所以我们不妨去掉两端的字母后调用 算法，找出所有满足条件的区间 。

当然，考虑到字符串并未彻底压缩，会影响到查找，所以我们需要预处理，将 之类压缩到最小。

不过，此时还有一个问题没有解决：类似于 和 的子串会被意外匹配，而它们的数量是不相同的。这时我们不妨在所有数字的起始处加一个特殊字符（如 ）。此时，形如 的字符串将会变为 ，即可避免意外匹配。

考虑到对于求得的区间，我们需要快速定位其左右端点对应的内容，所以我们需要用类似于 的容器记录每个元素的起始位置对应的元素。此时，对于 对应的元素的前一个元素和 对应的元素，我们只需比对其与 字符串的两端的元素的字母是否相同、以及数量是否符合条件即可。

当然，上述操作针对的是预处理后 只剩三个元素的情况，其余情况都可以暴力，只是元素为一个的时候，元素是可以在一个大区间内移动的，它的左右端点不像元素多的时候那样是固定的。

时间复杂度：

对应AC代码

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define pii pair<int, int>

class KMP { //交一个套板子的（（
public:
    static vector<int> prefix_function(string s) {
        int n = (int) s.length();
        vector<int> pi(n);
        for (int i = 1; i < n; i++) {
            int j = pi[i - 1];
            while (j > 0 && s[i] != s[j]) j = pi[j - 1];
            if (s[i] == s[j]) j++;
            pi[i] = j;
        }
        return pi;
    }

    static vector<pii > find_occurrences(const string &text, const string &pattern) {
        string cur = pattern + '#' + text;
        int sz1 = text.size(), sz2 = pattern.size();
        vector<pii > v;
        vector<int> lps = prefix_function(cur);
        for (int i = sz2 + 1; i <= sz1 + sz2; i++) {
            if (lps[i] == sz2)
                v.emplace_back(i - 2 * sz2, i - sz2 - 1);
        }
        return v;
    }
};

vector<pair<int, char>> merge(int tn, int &n) {
    vector<pair<int, char>> a;
    char pre = -1;
    int cnt = 0;
    while (tn--) {
        string cur;
        cin >> cur;
        int x = 0, i = 0;
        while (cur[i] != '-') {
            x = x * 10 + (cur[i] - '0');
            i++;
        }
        if (pre == -1) pre = cur[i + 1];
        if (pre != cur[i + 1]) {
            a.emplace_back(cnt, pre);
            n++;
            pre = cur[i + 1];
            cnt = x;
        } else cnt += x;
    }
    a.emplace_back(cnt, pre);
    n++;
    return a;
}

signed main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int tn, tm, n = 0, m = 0;
    cin >> tn >> tm;
    vector<pair<int, char>> a = merge(tn, n), b = merge(tm, m);
    int cnt = 0;
    if (m >= 3) {
        string origin, dest;
        map<int, int> ind;
        for (int i = 0; i < n; i++) {
            ind[origin.size()] = i;
            origin += "$" + to_string(a[i].first);
            origin += a[i].second;
        }
        for (int i = 1; i < m - 1; i++) {
            dest += "$" + to_string(b[i].first);
            dest += b[i].second;
        }
        vector<pii > oc = KMP::find_occurrences(origin, dest);
        for (auto e: oc) {
            if (e.second + 1 >= origin.size()) continue;
            int x1 = ind[e.first], x2 = ind[e.second + 1];
            if (x1 == 0) continue;
            if (a[x1 - 1].second == b[0].second && a[x2].second == b[m - 1].second
                && a[x1 - 1].first >= b[0].first && a[x2].first >= b[m - 1].first)
                cnt++;
        }
    } else if (m == 2) {
        for (int i = 0; i < n - 1; i++) {
            if (a[i].second != b[0].second || a[i + 1].second != b[1].second) continue;
            if (a[i].first >= b[0].first && a[i + 1].first >= b[1].first) cnt++;
        }
    } else {
        for (int i = 0; i < n; i++) {
            if (a[i].second != b[0].second) continue;
            if (a[i].first >= b[0].first) cnt += a[i].first - b[0].first + 1;
        }
    }
    cout << cnt << '\n';
}

有点难解释，反正大概做法是这样（（