Codeforces Round 849 (Div. 4)

A. Codeforces Checking

思路：

• 直接枚举，或者用库函数查找

时间复杂度：\(O(1)\)

void solve() {
    std::string s = "codeforces";
    char c;
    std::cin >> c;

    std::cout << (s.find(c) != -1 ? "YES" : "NO") << "\n";
}

B. Following Directions

思路：

• 根据给定的字符串指令模拟，观察在这个过程中是否经过糖果所在位置即可

时间复杂度：\(O(n)\)

void solve() {
    int n;
    std::cin >> n;

    std::string s;
    std::cin >> s;

    bool ok = false;
    int A = 0, B = 0;
    for (int i = 0; i < n; i++) {
        if (s[i] == 'U') {
            A++;
        } else if (s[i] == 'D') {
            A--;
        } else if (s[i] == 'L') {
            B--;
        } else {
            B++;
        }
        if (A == 1 && B == 1) {
            ok = true;
        }
    }
    std::cout << (ok ? "YES\n" : "NO\n");
}

C. Prepend and Append

思路：

• 直接双指针，分别从头尾扫描，直到出现两个字符都相同就停止

时间复杂度：\(O(n)\)

void solve() {
    int n;
    std::cin >> n;

    std::string s;
    std::cin >> s;

    int len = n;
    for (int i = 0, j = n - 1; i <= j; ) {
        if (s[i] ^ s[j]) {
            i++, j--;
            len -= 2;
        } else {
            break;
        }
    }
    std::cout << len << "\n";
}

D. Distinct Split

题目大意：对于一个字符的价值，我们将其叫做 \(f(s)\)，其定义为：一个字符串中字符出现的种类数。现在，我们可以把字符串 \(s\)，分为两个子串 \(a, b\)，求 \(f(a) + f(b)\) 的最大价值。

思路：

• 我们可以用双指针，分别从前后扫描，记录从前向后与从后向前的目前子串的种类数，然后我们枚举边界，直接取 \(max\) 即可

时间复杂度：\(O(n)\)

void solve() {
    int n;
    std::cin >> n;

    std::string s;
    std::cin >> s;

    std::set<char> A, B;
    std::vector<int> a(n + 1), b(n + 1);
    for (int i = 0, j = n - 1; i < n; i++, j--) {
        A.insert(s[i]);
        B.insert(s[j]);
        a[i] = A.size();
        b[j] = B.size();
    }

    int max = -1;
    for (int i = 0; i + 1 < n; i++) {
        max = std::max(max, a[i] + b[i + 1]);
    }
    std::cout << max << "\n";
}

E. Negatives and Positives

思路：

• 由于是改变两个相邻的位置，那么我们一定可以让至少 \(n - 1\) 个数都是正数。
• 如果负数的个数为奇数：那么我们可以贪心的使得最小的那个数为负数，这样可以使得答案最大。那么，答案就是 \(\Sigma_{i = 1}^{n}|a_i| - 2 \times min(|a_i|)\) ，为啥是 \(2 \times min(|a_i|)\) 呢？因为我们求 \(\Sigma_{i = 1}^{n}|a_i|\) 时，多加了一个 \(min(|a_i|)\)，所以要多减去一个。
• 如果负数的个数为偶数：那么我们可以让所有的数都是正数，直接输出所有元素的绝对值之和即可。

时间复杂度：\(O(n)\)

void solve() {
    int n;
    std::cin >> n;

    std::vector<int> a(n);
    for (int i = 0; i < n; i++) {
        std::cin >> a[i];
    }

    i64 neg = 0, sum = 0;
    for (int i = 0; i < n; i++) {
        if (a[i] < 0) {
            neg++;
            a[i] = -a[i];
        }
        sum += a[i];
    }
    i64 min = *min_element(a.begin(), a.end());
    if (neg & 1) {
        std::cout << sum - 2 * min << "\n";
    } else {
        std::cout << sum << "\n";
    }
}

F. Range Update Point Query

思路：

• 我是直接用线段树写的，这题涉及到区间修改和单点查询，可以直接用线段树做，每个节点记得开一个bool标记，如果 \(\le 10\) 就不能在进行修改了。

时间复杂度：\(O(n + q \times logn)\)

constexpr int N = 2E5 + 10;
class SegmentTree {
public:
    int n;
    std::vector<int> a;
    struct node {
        int l, r;
        int val;
        bool ok;
    }tr[N << 2];

    SegmentTree() {}
    SegmentTree(std::vector<int> init_) {
        init(init_);
    }
    void init(std::vector<int> init_) {
        a = init_;
        n = a.size();
        build(1, 1, n);
    }

    void pushup(node &u, node &l, node &r) {
        u.ok = l.ok & r.ok;
    }

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

    int cal(int x) {
        int res = 0;
        while (x) {
            res += x % 10;
            x /= 10;
        }
        return res;
    }

    void build(int u, int l, int r) {
        tr[u] = {l, r, 0, 0};
        if (l == r) {
            tr[u].val = a[l];
            if (a[l] < 10) {
                tr[u].ok = true;
            }
            return ;
        }
        int mid = l + r >> 1;
        build(u << 1, l, mid); build(u << 1 | 1, mid + 1, r);
        pushup(u);
    }

    void modify(int u, int l, int r) {
        if (tr[u].ok) return ;
        if (tr[u].l == tr[u].r) {
            tr[u].val = cal(tr[u].val);
            if (tr[u].val < 10) tr[u].ok = true;
            return ;
        }
        int mid = tr[u].l + tr[u].r >> 1;
        if (l <= mid) modify(u << 1, l, r);
        if (r > mid) modify(u << 1 | 1, l, r);
        pushup(u);
    }

    int query(int u, int x) {
        if (tr[u].l == tr[u].r) return tr[u].val;
        int mid = tr[u].l + tr[u].r >> 1;
        if (x <= mid) return query(u << 1, x);
        return query(u << 1 | 1, x);
    }
};

void solve() {
    int n, q;
    std::cin >> n >> q;

    std::vector<int> a(n + 1);
    for (int i = 1; i <= n; i++) {
        std::cin >> a[i];
    }   
    SegmentTree seg(a);

    while (q--) {
        int op;
        std::cin >> op;

        if (op == 1) {
            int l, r;
            std::cin >> l >> r;

            seg.modify(1, l, r);
        } else {
            int x;
            std::cin >> x;

            std::cout << seg.query(1, x) << "\n";
        }
    }
}

G1. Teleporters (Easy Version)

思路：

• 直接存一下从起点 \(0\) 到其他位置的花费，然后从小到大排序，直到用完所有的硬币。

时间复杂度：\(O(nlogn)\)

void solve() {
    int n, c;
    std::cin >> n >> c;

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

    std::vector<i64> s(n + 1);
    for (int i = 1; i <= n; i++) {
        s[i] = i + a[i];
    }

    std::sort(s.begin() + 1, s.end());

    int ans = 0;
    for (int i = 1; i <= n; i++) {
        if (c - s[i] < 0) {
            break;
        }
        c -= s[i];
        ans++;
    }
    std::cout << ans << '\n';
}

G2. Teleporters (Hard Version)

思路：

时间复杂度：