Educational Codeforces Round 144 (Rated for Div. 2)【A - D】

路漫漫啊……

A. Typical Interview Problem

题解

字符串以 $lcm(3, 5) = 15$ 个数为周期进行循环，循环节为 FBFFBFFB 。

代码

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    string s;

    for (int i = 1; i <= 50; i++) {
        if (i % 3 == 0) {
            s += 'F';
        }
        if (i % 5 == 0) {
            s += 'B';
        }
    }

    int t;
    cin >> t;

    while (t--) {
        int n;
        cin >> n;

        string str;
        cin >> str;

        cout << (s.find(str) != s.npos ? "YES" : "NO") << "\n";
    }

    return 0;
}

B. Asterisk-Minor Template

题解

• 如果首部或尾部字母相同，那么一个 * 即可

• 否则首部尾部各有一个 * ，为了使 * 的数目较少，至少要有两对字母相同，此时为 *a...a* 的形式：

  • 如果两对字母内相同的字母不与两个字母相邻，那么为 *a*a*a* 的形式，不符合条件

  • 所以两个字母内相同的字母必须与两个字母之一相邻，即为 *aa*a* 或 *a*aa* 的形式，此时可以归为 *aa* 的形式

所以可以发现最少只需要 a* 、 *a 、 *aa* 三种形式的字符串。

代码

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin >> t;

    while (t--) {
        string a, b;
        cin >> a >> b;

        int n = a.size(), m = b.size();

        if (a.front() == b.front()) {
            cout << "YES" << "\n";
            cout << a.front() << "*" << "\n";
            continue;
        }

        if (a.back() == b.back()) {
            cout << "YES" << "\n";
            cout << "*" << a.back() << "\n";
            continue;
        }

        bool ok = false;
        string ans;
        
        for (int i = 0; i + 1 < n; i++) {
            for (int j = 0; j + 1 < m; j++) {
                if (a[i] == b[j] and a[i + 1] == b[j + 1]) {
                    ok = true;
                    ans = string("*") + a.substr(i, 2) + string("*");
                }
            }
        }

        if (not ok) {
            cout << "NO" << "\n";
        } else {
            cout << "YES" << "\n";
            cout << ans << "\n";
        }
    }

    return 0;
}

C. Maximum Set

题解

一些 observation ：

• 满足条件的集合中，较小的数的质因子幂次是较大的数的子集
• 最长的集合一定都是某个数乘以 2 的幂次，即 $a_0 \cdot 2^0, a_0 \cdot 2^1, a_0 \cdot 2^2, \dots, a_0 \cdot 2^k$
• 首项的最小值 $min_{a_0} = l$

所以最大幂次的值 $k = \lfloor log_2\lfloor \frac{r}{l} \rfloor \rfloor$ ，集合的最大长度为 $k + 1$ ，同时反推出首项的最大值 $max_{a_0} = \lfloor \frac{r}{2^{k}} \rfloor$ ，所以首项不同的集合共有 $max_{a_0} - l + 1$ 个。

注意到一个性质： $a_0 \cdot 2^k\cdot 2 \gt r$ ，即 $a_0 \cdot 2^{k - 1} \cdot 4 \gt r$ ，所以可能存在 $a_0 \cdot 2^{k - 1} \cdot 3 \le r$ ，即将倒数一些数因子中的一个 $2$ 换为 $3$ 仍可能满足条件，此时末项为 $b_k = a_0 \cdot 2^{k - 1} \cdot 3$ ，首项的最大值 $max_{b_0} = \lfloor \frac{r}{2^{k - 1} \cdot 3} \rfloor$ ，由于可以将连续倒数 $1 \sim k$ 个数中的因子替换，所以这种类型的集合共有 $k \cdot (max_{b_0} - l + 1)$ 个。

所以集合的最大长度为 $k + 1$ ，总数为 $(max_{a_0} - l + 1) + k \cdot (max_{b_0} - l + 1)$ 。

Tips： $max_{b_0} - l + 1$ 可能小于 $0$ 。

代码

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin >> t;

    while (t--) {
        int l, r;
        cin >> l >> r;

        int k = __lg(r / l);

        int ans = 0;
        ans += r / (1 << k) - l + 1;
        ans += max(0, r / (1 << (k - 1)) / 3 - l + 1) * k;
        
        cout << k + 1 << ' ' << ans << "\n";
    }

    return 0;
}

D. Maximum Subarray

题解

先令 $a_i = a_i - x$ ，然后令 $x = 2x$ ，此时问题即变为选 $k$ 个数加上 $x$ 后计算最大连续子段和：

• 若 $x \ge 0$ ，那么这 $k$ 个数要尽量选满在最大区间内

• 若 $x \lt 0$ ，那么这 $k$ 个数要尽量选在两边，远离最大区间

这两种情况可以分别归纳为：先选前 $k$ 个，然后将所选区间循环 右移/左移 的情况。

此时问题变为单点修改，区间查询最大连续子段和，用线段树即可。

Tips：当 $x \lt 0$ 时，也可以令 $x = -x, k = n - k$ ，此时只需要循环右移即可。

代码

#include <bits/stdc++.h>
using namespace std;

const int N = 2e5 + 10;

int n, m;
int w[N];
struct node {
    int l, r;
    long long tmax, lmax, rmax, sum;
} tr[N * 4];

void pushup(node &u, node &l, node &r) {
    u.sum = l.sum + r.sum;
    u.lmax = max(l.lmax, l.sum + r.lmax);
    u.rmax = max(r.rmax, r.sum + l.rmax);
    u.tmax = max(l.rmax + r.lmax, max(l.tmax, r.tmax));
}

void pushup(int u) {
    pushup(tr[u], tr[u << 1], tr[u << 1 | 1]);
}

void build(int u, int l, int r) {
    if (l == r) tr[u] = {l, r, w[r], w[r], w[r], w[r]};
    else {
        tr[u] = {l, r};
        int mid = (l + r) >> 1;
        build(u << 1, l, mid);
        build(u << 1 | 1, mid + 1, r);
        pushup(u);
    }
}

void modify(int u, int x, int v) {
    if (tr[u].l == x && tr[u].r == x) tr[u] = {x, x, v, v, v, v};
    else {
        int mid = (tr[u].l + tr[u].r) >> 1;
        if (x <= mid) modify(u << 1, x, v);
        else modify(u << 1 | 1, x, v);
        pushup(u);
    }
}

node query(int u, int l, int r) {
    if (tr[u].l >= l && tr[u].r <= r) return tr[u];

    int mid = (tr[u].l + tr[u].r) >> 1;
    if (r <= mid) return query(u << 1, l, r);
    else if (l > mid) return query(u << 1 | 1, l, r);
    else {
        auto left = query(u << 1, l, r);
        auto right = query(u << 1 | 1, l, r);
        node res;
        pushup(res, left, right);
        return res;
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin >> t;

    while (t--) {
        int k, x;
        cin >> n >> k >> x;

        if (x < 0) {
            x = -x;
            k = n - k;
        }

        for (int i = 1; i <= n; i++) {
            cin >> w[i];
            w[i] -= x;
        }
        
        x *= 2;

        build(1, 1, n);

        if (k == 0) {
            cout << max(0LL, query(1, 1, n).tmax) << "\n";
            continue;
        }

        for (int i = 1; i <= k - 1; i++) {
            modify(1, i, w[i] + x);
        }

        long long ans = 0;
        for (int i = k; i <= n; i++) {
            if (i - k >= 1) {
                modify(1, i - k, w[i - k]);
            }
            modify(1, i, w[i] + x);
            ans = max(ans, query(1, 1, n).tmax);
        }
        cout << ans << "\n";
    }

    return 0;
}