AtCoder Beginner Contest 360

A

判断R和H谁先出现即可

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

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

    for (auto ch : s) {
        if (ch == 'R') {
            std::cout << "Yes\n";
            return 0;
        } else if (ch == 'M') {
            std::cout << "No\n";
            return 0;
        }
    }
}

B

按题意模拟即可，注意边界条件

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

    std::string s, t;
    std::cin >> s >> t;

    for (int w = 1; w < s.size() - 1; w++) {
        for (int c = 0; c <= w; c++) {
            std::string ans;
            for (int i = 0; w * i + c < s.size(); i++) {
                ans += s[w * i + c];
            }

            if (ans == t) {
                std::cout << "Yes\n";
                return 0;
            }
        }
    }

    std::cout << "No\n";
}

C

贪心，把除了最大值的多余值累计求和即可

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

    int n;
    std::cin >> n;

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

    std::map<int, std::vector<int>> M;
    for (int i = 0; i < n; i++) {
        int w;
        std::cin >> w;
        M[a[i]].push_back(w);
    }

    int ans = 0;
    for (auto &[_, v] : M) {
        ans += std::accumulate(v.begin(), v.end(), 0) -
               *std::max_element(v.begin(), v.end());
    }

    std::cout << ans << "\n";
}

D

向左和向右分组，不难发现向左和向右差在$2T$之内的对符合条件

维护一个有序下标权值序列，前缀和二分就行，需要离散化

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

    int n, t;
    std::string s;

    std::cin >> n >> t >> s;

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

    std::sort(all.begin(), all.end());

    auto find = [&](int x) {
        return std::upper_bound(all.begin(), all.end(), x) - all.begin();
    };

    std::vector<int> a(n), sum(n + 1);
    for (int i = 0; i < n; i++) {
        if (s[i] == '0') {
            a[find(x[i]) - 1]++;
        }
    }
    for (int i = 0; i < n; i++) {
        sum[i + 1] = sum[i] + a[i];
    }

    ll ans = 0;
    for (int i = 0; i < n; i++) {
        if (s[i] == '1') {
            ans += sum[find(std::min(2000000000LL, x[i] + 2LL * t))] -
                   sum[find(x[i]) - 1];
        }
    }

    std::cout << ans << "\n";
}

E

$p1$是从白球在$1$号位到其他位置的概率，$p2$是白球在其他位置到$1$号位的概率

$a$是当前轮白球在$1$号位的概率（在其他位置的概率满足对称性都一样）

于是转移方程就得到了，还可以用快速幂优化，不过本题不需要

最终期望就是在$1$号位的期望$1a$，和在其他位置的期望$\frac{1-a}{n-1}(2+n)(n-1)/2=(1-a)(2+n)/2$相加

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

    int n, k;
    std::cin >> n >> k;

    Z a = 1;
    Z p1 = Z(2) * (n - 1) / n / n, p2 = Z(2) / n / n;

    while (k--) {
        a = a * (1 - p1) + (1 - a) * p2;
    }

    std::cout << a + (1 - a) * (2 + n) / 2 << "\n";
}

F

找到与给定区间相交最多的字典序最小的区间

考虑对于一个给定区间$[l,r]$，与之相交的区间的$L,R$范围有两种情况

1. $0\le L\le l-1,l+1\le R\le r-1$
2. $l+1\le L\le r-1,r+1\le R \le 1e9+1$

我们任意选取一个$R$，都有唯一的对应满足相交条件做多的且字典序最小的$L$

答案就在所有相交最多且$L,R$最小的点中产生，这里$L$的范围其实就是$1$的贡献，可以用权值线段树来维护

每个可能的$L$只出现在$l,r$附近，于是可以用离散化统计，实现需要注意边界、特殊值

struct Tag {
    int add = 0;
    void apply(const Tag &t) { add += t.add; }
};

struct Info {
    int v = 0;
    int p;
    friend Info operator+(const Info &lhs, const Info &rhs) {
        return lhs.v >= rhs.v ? lhs : rhs;
    }
    void apply(const Tag &t) { v += t.add; }
};

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

    int n;
    std::cin >> n;

    std::vector<std::array<int, 4>> event;
    std::vector<int> all{0, 1000000001};
    for (int i = 0; i < n; i++) {
        int l, r;
        std::cin >> l >> r;
        if (r - l == 1) {
            continue;
        }

        if (l) {
            event.push_back({0, l - 1, l + 1, 1});
            event.push_back({0, l - 1, r, -1});
            all.emplace_back(l - 1);
        }
        event.push_back({l + 1, r - 1, r + 1, 1});
        event.push_back({l + 1, r - 1, 1000000001, -1});
        all.emplace_back(l + 1);
        all.emplace_back(r - 1);
        all.emplace_back(r + 1);
    }

    std::sort(all.begin(), all.end());
    all.erase(std::unique(all.begin(), all.end()), all.end());

    std::sort(event.begin(), event.end(), [](auto &l, auto &r) {
        return l[2] < r[2] ? true : l[2] == r[2] ? l[3] < r[3] : false;
    });

    const int N = all.size();
    std::vector<Info> info(N + 1);
    for (int i = 0; i < N; i++) {
        info[i + 1] = {0, all[i]};
    }
    auto find = [&](int x) {
        return std::upper_bound(all.begin(), all.end(), x) - all.begin();
    };

    int max = 0;
    PII ans = {0, 1};
    LazySegtree<Info, Tag> seg(N, info);
    for (auto &[l, r, R, v] : event) {
        l = find(l);
        r = find(r);
        seg.modify(l, r, Tag{v});
        auto [m, p] = seg.all();
        if (m > max) {
            max = m;
            ans = {p, R};
        }
    }

    std::cout << ans.first << " " << ans.second << "\n";
}

G

维护两个LIS数组，分别是修改过的LIS和没修改过的LIS

每个LIS内部分别正常用二分维护LIS

外部有没修改过的LIS到修改过的LIS的转移，考虑遍历数组元素时遍历到的当前元素$a_i$，把$a_i$修改为之前的最长上升子序列的末尾元素$+1$是最优措施

证明：假设不是最优措施，也就是把$a_i$修改为更小的数时，有两种情况

1. 之前的序列紧密（每一个元素都在LIS中），此时修改为更小的数没有用
2. 之前的序列不紧密，因为只能修改一次，那么与其修改$a_i$不如修改之前的元素，使得LIS最优

而且因为如此操作，之前的LIS序列已经是最优的，而且考虑到每个位置的修改，可以涵盖所有情况

最后注意边界条件处理，$inf\gt 1e9+1$，才能保证如果最后修改一个值为$1e9+1$时能正确统计答案

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

    int n;
    std::cin >> n;

    std::vector<int> a(n);
    for (auto &i : a) {
        std::cin >> i;
    }

    const int inf = 2e9;
    std::vector<int> f(n + 1, inf), g(n + 1, inf);
    f[0] = g[0] = -1;
    for (auto i : a) {
        auto p1 = std::lower_bound(f.begin(), f.end(), i);
        auto p2 = std::lower_bound(g.begin(), g.end(), i);
        auto e = std::lower_bound(f.begin(), f.end(), inf) - f.begin();
        *p1 = i;
        *p2 = i;
        g[e] = std::min(g[e], f[e - 1] + 1);
    }

    std::cout << std::lower_bound(g.begin(), g.end(), inf) - g.begin() - 1 << "\n";
}