AtCoder Beginner Contest 360

A - A Healthy Breakfast (abc360 A)

题目大意

给定一个字符串包含RMS,问R是否在S的左边。

解题思路

比较RS的下标,谁小即谁在左边。

神奇的代码
#include <bits/stdc++.h>
using namespace std;
using LL = long long;

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    string s;
    cin >> s;
    cout << (s.find('R') < s.find('M') ? "Yes" : "No") << '\n';

    return 0;
}



B - Vertical Reading (abc360 B)

题目大意

给定两个字符串\(s,t\),找到一个 \(1 \leq c \leq w < |s|\),使得将 \(s\)拆开,每个子串有\(w\)个字母, 对每个子串取第\(c\)位字母出来(不存在则不取),使其组成 \(t\)

解题思路

由于\(|s| \leq 100\),直接花 \(O(|s|^2)\)枚举 \(c,w\),然后拆开子串、拼接、比较即可。时间复杂度是 \(O(n^3)\)

神奇的代码
#include <bits/stdc++.h>
using namespace std;
using LL = long long;

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    string s, t;
    cin >> s >> t;
    bool ok = false;
    for (int i = 1; i < s.size(); i++) {
        vector<string> sub;
        for (int j = 0; j < s.size(); j += i) {
            sub.push_back(s.substr(j, i));
        }
        for (int j = 0; j < i; ++j) {
            string ans;
            for (auto& x : sub) {
                if (j < x.size())
                    ans += x[j];
            }
            if (ans == t) {
                ok = true;
            }
        }
    }
    if (ok)
        cout << "Yes" << '\n';
    else
        cout << "No" << '\n';

    return 0;
}



C - Move It (abc360 C)

题目大意

给定 \(n\)个箱子。再给定\(n\)个球所在的箱子位置,球有重量。

移动球到其他箱子里,代价是球的重量。

求最小的代价,使得每个箱子各有一个球。

解题思路

对于一个有多个球的盒子,因为最终会有一个球留在盒子里,为了最小代价,那最重的球不移动,而移动其他的球。

因此最终的代价就是每个盒子除最重球的球重量的和。

神奇的代码
#include <bits/stdc++.h>
using namespace std;
using LL = long long;

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n;
    cin >> n;
    vector<vector<int>> box(n);
    vector<int> pos(n);
    for (auto& i : pos)
        cin >> i;
    for (int i = 0; i < n; ++i) {
        int w;
        cin >> w;
        box[pos[i] - 1].push_back(w);
    }
    int ans = 0;
    for (auto& i : box) {
        if (i.empty())
            continue;
        sort(i.begin(), i.end(), greater<int>());
        ans += accumulate(i.begin(), i.end(), 0) - i[0];
    }
    cout << ans << '\n';

    return 0;
}



D - Ghost Ants (abc360 D)

题目大意

一维数轴,蚂蚁移动,有方向,速度一样。碰撞时不改变方向,继续保持原方向行走。

经过\(t\)时刻后,问碰撞的蚂蚁对数。

解题思路

同方向的蚂蚁不会碰撞,因此仅考虑不同向的。

考虑往右的蚂蚁会与哪些往左的蚂蚁碰撞。

由于所有蚂蚁速度一样,因此由相向运动得知,假设当前往右的蚂蚁位置为\(x\),那么所有往左的位于\([x, x + 2t]\)的蚂蚁都会与其相撞。

根据蚂蚁前进方向对坐标排序,二分一下就能找到往左的位于 \([x, x + 2t]\)的蚂蚁数量。

所有数量累加即为答案。时间复杂度是 \(O(n \log n)\)

神奇的代码
#include <bits/stdc++.h>
using namespace std;
using LL = long long;

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n, t;
    string dir;
    cin >> n >> t >> dir;
    array<vector<int>, 2> pos;
    for (int i = 0; i < n; ++i) {
        int p;
        cin >> p;
        pos[dir[i] - '0'].push_back(p);
    }
    for (auto& x : pos)
        sort(x.begin(), x.end());
    LL ans = 0;
    for (int i = 1; i < 2; ++i) {
        auto& cur = pos[i];
        auto& nxt = pos[i ^ 1];
        for (auto x : cur) {
            LL l = x;
            LL r = x + t * (i == 1 ? 1 : -1) * 2ll;
            if (l > r)
                swap(l, r);
            auto ll = lower_bound(nxt.begin(), nxt.end(), l);
            auto rr = upper_bound(nxt.begin(), nxt.end(), r);
            ans += rr - ll;
        }
    }
    cout << ans << '\n';

    return 0;
}



E - Random Swaps of Balls (abc360 E)

题目大意

\(n\)个球,其中第一个是黑球,其余是白球。

进行以下操作 \(k\)次:

  • 随机两次独立选取 \(i,j\),交换第 \(i\)个球和第 \(j\)个球。

问黑球位置的期望值。

解题思路

假设最终黑球位于第\(i\)个球的概率是\(p_i\),根据期望定义,答案就是 \(\sum_{i=1}^{n} i p_i\)。考虑如何求\(p_i\)

容易发现第 \(2,3,...,n\)个球没有本质区别,其概率都是一样的,因此最终我们需要求的就两个数

  • \(p_1\)即位于第一个球的概率
  • \(p_2\)即位于非第一个球的概率

容易发现经过第\(k\)次操作的概率,仅依赖于第 \(k-1\)次的情况,因此可以迭代球,即设 \(dp[k][0/1]\)表示经过 \(k\)次操作后,球位于第一个球/不位于第一个球的概率。

转移就考虑本次操作是否将球移动到第一个球或非第一个球。设移动概率\(move = 2\frac{1}{n}\frac{n-1}{n}\),不移动概率\(stay = 1 - move\),移动到某一个位置的概率为 \(move1 = \frac{move}{n-1} = \frac{2}{n^2}\)

\(dp[i][0] = dp[i - 1][0] \times stay + dp[i - 1][1] \times move1\),不动或者从非一球移动到一球。
\(dp[i][1] = dp[i - 1][0] \times move + dp[i - 1][1] \times (1 - move1)\),从一球移动或者从非一球移动到非移动(全概率-移动到一球的概率)

最后\(p_1 = dp[k][0],p_2 = p_3 = ... = p_n = \frac{dp[k][1]}{n-1}\),答案就是\(\sum_{i=1}^{n} i p_i = dp[k][0] + \frac{(n+2)(n-1)}{2} \frac{dp[k][1]}{n-1}\)

时间复杂度为\(O(k)\)

神奇的代码
#include <bits/stdc++.h>
using namespace std;
using LL = long long;

const int mo = 998244353;

long long qpower(long long a, long long b) {
    long long qwq = 1;
    while (b) {
        if (b & 1)
            qwq = qwq * a % mo;
        a = a * a % mo;
        b >>= 1;
    }
    return qwq;
}

long long inv(long long x) { return qpower(x, mo - 2); }

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n, k;
    cin >> n >> k;
    int invn = inv(n);
    int invn1 = inv(n - 1);
    int move = 2ll * invn * (n - 1) % mo * invn % mo;
    int stay = (1ll - move + mo) % mo;
    int move1 = 1ll * move * invn1 % mo;
    array<int, 2> dp{};
    dp[0] = 1;
    for (int i = 0; i < k; i++) {
        array<int, 2> dp2{};
        dp2[0] = (1ll * dp[0] * stay % mo + 1ll * dp[1] * move1 % mo) % mo;
        dp2[1] = (1ll * dp[0] * move % mo +
                  1ll * dp[1] * ((1 - move1 + mo) % mo) % mo) %
                 mo;
        dp.swap(dp2);
    }
    int ans =
        (dp[0] + 1ll * (n + 2) * (n - 1) / 2 % mo * dp[1] % mo * invn1 % mo) %
        mo;
    cout << ans << '\n';

    return 0;
}



F - InterSections (abc360 F)

题目大意

给定\(n\)个区间,若俩区间\([l_a, r_a],[l_b,r_b]\)有交叉 ,则有\(l_a < l_b < r_a < r_b\)

\(f(l,r)\)表示与 \([l,r]\)有交叉的区间数。

求最大值。

解题思路

<++>

神奇的代码



G - Suitable Edit for LIS (abc360 G)

题目大意

给定一个数组,进行一次操作,使得最长上升子序列的长度最大。

操作为,将任意一个数改为任意一个数。

解题思路

这种有一次修改的,可以从修改处考虑,其修改处左右两边是一个正常的最长上升子序列问题。

因此事先求出\(pre[i]\)表示从左到右,选了第 \(i\)个数字的最长上升子序列长度,\(suf[i]\)表示从右到左,选了第 \(i\)个数字的最长下降子序列长度,需要使用\(O(n\log n)\)的方法。考虑如何将 \(pre\)\(suf\)组合。

注意到是严格上升,如果枚举 \(suf_i\),思考 \(\max(pre_j + suf_i + 1)\)有什么条件,以及 \(j\)如何找。

枚举 \(i\),考虑 \(j\),则有 \(k \in (j, i), a_k\)需要修改,因此 \(j < i - 1\),同时由于严格递增, \(a_i > a_j + 1\) ,这样\(a_k\)才能更改成对应的数,使得 \(pre_j\)\(suf_i\)拼接起来得到一个更长的最长上升子序列。

即需要解决这么一个问题\(\max_{j < i - 1 \& a_i > a_j + 1} (pre_j + suf_i + 1)\)。容易发现这就是一个朴素的二维偏序问题,用线段树求解即可。注意需要对\(a_i\)离散化。

\(O(n \log n)\)的一种最长上升子序列的求法,即\(pos[i]\)表示最长上升子序列长度为 \(i\)的末尾数字(最大数字)的最小值。注意到 \(pos\)是一个递增的数组,因此对于当前数字\(a_i\) ,可以二分找到它可以接在哪个数字\(a_j\)的后面,进而知道了当前的\(dp[i]\),然后更新 \(pos\)数组。或者朴素的 \(O(n^2)\)\(dp\),分析转移式可以注意到也是一个二维偏序问题,也可以用线段树解决。

用线段树解二维偏序,下标是\(a_j\),值是\(dp[j]\)。即当前\(dp[j]\)求出来后,将 \(dp[j - 1]\)插入到线段树里,即将 \(a_j\)位置的值赋予 \(dp[j]\)

这样在求\(dp[i]\)时,线段树里的值都是 \(j < i - 1\)\(dp[j]\)的值,自然满足第一个 \(j < i - 1\)的条件,因为线段树的下标是 \(a_j\),而 \(a_i > a_j + 1\)相当于一个区间 \([1, a_i - 2]\),要求的就是这个区间的\(dp\)最大值,因为线段树维护的就是\(dp[j]\),故区间查询最大值、单点修改即可。而由于\(a_i\)很大,为作为线段树的下标,需要离散化。

神奇的代码
#include <bits/stdc++.h>
using namespace std;
using LL = long long;

const int inf = 1e9 + 8;

const int N = 2e5 + 8;

class segment {
#define lson (root << 1)
#define rson (root << 1 | 1)
  public:
    int maxx[N << 2];

    void build(int root, int l, int r) {
        if (l == r) {
            maxx[root] = 0;
            return;
        }
        int mid = (l + r) >> 1;
        build(lson, l, mid);
        build(rson, mid + 1, r);
        maxx[root] = max(maxx[lson], maxx[rson]);
    }

    void update(int root, int l, int r, int pos, int val) {
        if (l == r) {
            maxx[root] = max(maxx[root], val);
            return;
        }
        int mid = (l + r) >> 1;
        if (pos <= mid)
            update(lson, l, mid, pos, val);
        else
            update(rson, mid + 1, r, pos, val);
        maxx[root] = max(maxx[lson], maxx[rson]);
    }

    LL query(int root, int l, int r, int L, int R) {
        if (L <= l && r <= R) {
            return maxx[root];
        }
        int mid = (l + r) >> 1;
        int resl = -inf, resr = -inf;
        if (L <= mid)
            resl = query(lson, l, mid, L, R);
        if (R > mid)
            resr = query(rson, mid + 1, r, L, R);
        return max(resl, resr);
    }
} sg;

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n;
    cin >> n;
    vector<int> a(n);
    for (auto& x : a)
        cin >> x;
    auto solve = [&](vector<int>& a) -> vector<int> {
        vector<int> dp(n, 1);
        vector<int> pos(n + 1, inf);
        pos[0] = -inf;
        for (int i = 0; i < n; i++) {
            auto it = lower_bound(pos.begin(), pos.end(), a[i]) - pos.begin();
            dp[i] = it;
            pos[it] = min(pos[it], a[i]);
        }
        return dp;
    };
    auto pre = solve(a);
    reverse(a.begin(), a.end());
    transform(a.begin(), a.end(), a.begin(), [](int x) { return -x; });
    auto suf = solve(a);
    reverse(suf.begin(), suf.end());
    reverse(a.begin(), a.end());
    transform(a.begin(), a.end(), a.begin(), [](int x) { return -x; });

    vector<int> b(a.begin(), a.end());
    b.push_back(-inf);
    sort(b.begin(), b.end());
    b.erase(unique(b.begin(), b.end()), b.end());
    auto rank = [&](int x) {
        return lower_bound(b.begin(), b.end(), x) - b.begin() + 1;
    };
    int ans = 0;
    int m = b.size();
    sg.build(1, 1, m);
    for (int i = 0; i < n; ++i) {
        int cnt = sg.query(1, 1, m, 1, rank(a[i] - 1) - 1);
        ans = max(ans, suf[i] + cnt + (i != 0));
        if (i > 0)
            sg.update(1, 1, m, rank(a[i - 1]), pre[i - 1]);
    }
    cout << ans << '\n';

    return 0;
}



热门相关:婚婚欲睡:腹黑老公请节制   一世倾心:误惹腹黑师弟   我真是非洲酋长   逍遥小镇长   穹顶之上