跳转至

ABC360(A-F)

A - A Healthy Breakfast

题目大意

给你一个长度为 \(3\) 的字符串，字符串由 R、M 和 S 三种字符组成，判断字符 R 是否在字符 M 的左边。

参考代码 
#include <iostream>

using namespace std;

int main()
{
    string s;
    cin >> s;
    int x = -1, y = -1;
    for(int i = 0; i < 3; i++)
        if(s[i] == 'R')
            x = i;
        else if(s[i] == 'M')
            y = i;
    cout << (x < y ? "Yes" : "No") << endl;
    return 0;
}

B - Vertical Reading

题目大意

给你两个字符串 \(S\) 和 \(T\)，其中 \(1 \le |T| \le |S| \le 100\)。判断是否存在数对 \((c, w)\) 满足以下条件：

  • \(1 \le c \le w \le |S|\)
  • 将 \(S\) 每隔 \(w\) 个字符隔开，可以得到若干个长度为 \(w\) 的子串（最后一个子串的长度可能不足 \(w\)），从这些子串中依次选择第 \(w\) 个字符，拼接成一个新的字符串，且这个字符串等于 \(T\)

如果存在这样的 \((c, w)\) 则输出 Yes，否则输出 No

解题思路

直接枚举就可以了。

参考代码 
#include <iostream>

using namespace std;

int main()
{
    string s, t;
    cin >> s >> t;
    int n = s.size();
    bool flag = false;
    for(int c = 1; c < n && !flag; c++)
    {
        for(int w = c; w < n; w++)
        {
            string now;
            for(int i = c - 1; i < n; i += w)
                now += s[i];
            if(now == t)
            {
                flag = true;
                break;
            }
        }
    }
    cout << (flag ? "Yes" : "No") << endl;
    return 0;
}

C - Move It

题目大意

有 \(N(1 \le N \le 10^5)\) 个物品和 \(N\) 个箱子，第 \(i\) 个物品位于第 \(A_i\) 个箱子中。第 \(i\) 个物品的重量是 \(W_i\)。你可以将一个物品从一个箱子移动到另一个箱子，这会花费等同于物品重量的体力。初始的时候，有一些箱子可能没有物品，有一些箱子可能不止一个物品。问：最少花费多少体力才能让每个箱子只有一个物品？

解题思路

贪心即可。

参考代码 
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main()
{
    int n;
    cin >> n;
    vector<int> w(n+1);
    vector<vector<int>> box(n+1);
    for(int i = 1, a; i <= n; i++)
    {
        cin >> a;
        box[a].emplace_back(i);
    }
    for(int i = 1; i <= n; i++)
        cin >> w[i];
    int ans = 0;
    for(int i = 1; i <= n; i++)
    {
        if(box[i].size() > 1)
        {

            sort(box[i].begin(), box[i].end(), [&w](int x, int y) -> bool {return w[x] < w[y];});
            for(int j = 0, k = box[i].size(); j < k-1; j++)
                ans += w[box[i][j]];
        }
    }
    cout << ans << endl;
    return 0;
}

D - Ghost Ants

题目大意

在数轴上有 \(N(2 \le N \le 2 \times 10^5)\) 只蚂蚁，第 \(i\) 只蚂蚁的初始位置是 \(X_i\)。每只蚂蚁都有行动方向，\(S_i\) 为 0 表示第 \(i\) 只蚂蚁朝着负半轴移动，\(S_i\) 为 1 表示第 \(i\) 只蚂蚁朝着正半轴移动。每一秒，所有蚂蚁会移动 \(1\) 单位距离。当两只蚂蚁相遇的时候，它们会经过彼此，继续前进。

问：在 \(T(1 \le T \le 10 ^ 9)\) 秒后，总共有多少对蚂蚁相遇？

解题思路

因为蚂蚁会穿过彼此，所以往右走的蚂蚁只可能碰见往左走的蚂蚁。

将蚂蚁分成向左走和向右走两类，对坐标排序，固定考虑向右走的蚂蚁，最远能和向左走的哪只蚂蚁相遇，设 \(x\) 表示向右走的蚂蚁坐标，\(y\) 表示向左走的蚂蚁坐标，则 \(T\) 秒内可相遇的条件是 \(y \ge x\) 且 \(y-x \le 2T\)，于是对每一个 \(x\) 直接二分出 \(y\)，或者直接双指针就可以了。

参考代码 
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main()
{
    int n;
    cin >> n;
    vector<int> w(n+1);
    vector<vector<int>> box(n+1);
    for(int i = 1, a; i <= n; i++)
    {
        cin >> a;
        box[a].emplace_back(i);
    }
    for(int i = 1; i <= n; i++)
        cin >> w[i];
    int ans = 0;
    for(int i = 1; i <= n; i++)
    {
        if(box[i].size() > 1)
        {

            sort(box[i].begin(), box[i].end(), [&w](int x, int y) -> bool {return w[x] < w[y];});
            for(int j = 0, k = box[i].size(); j < k-1; j++)
                ans += w[box[i][j]];
        }
    }
    cout << ans << endl;
    return 0;
}

E - Random Swaps of Balls

题目大意

有 \(N-1(1 \le N \le 998244352)\) 个白球和 \(1\) 个黑球排成一行，初始的时候黑球在最左端。

执行以下操作 \(K(1 \le K \le 10 ^ 5)\) 次：

  • 随机选择两个 \([1, N]\) 之间的数字 \(i\) 和 \(j\)，如果 \(i \neq j\)，交换第 \(i\) 和第 \(j\) 个球的位置。

问：在 \(K\) 次操作后，黑球所在位置的数学期望是多少？答案对 \(998244353\) 取模。

解题思路

设 \(f[i][j]\) 表示操作 \(i\) 次后位置 \(j\) 是黑球的概率，初始的时候 \(f[0][1] = 1\)，其余的 \(f[0][j] = 0\)。

很容易发现，无论操作多少次，\(f[i][2], f[i][3], \cdots, f[i][N]\) 都是相等的，于是我们只需要考虑位置 \(1\) 和其他位置。

设 \(f[i]\) 表示操作 \(i\) 次后位置 \(1\) 是黑球的概率，则位置 \(2\) 到位置 \(N\) 是黑球的概率是 \(\frac{1-f[i]}{N-1}\)

考虑 \(f[i]\) 如何转移，分两种情况讨论：

  • \(i-1\) 次操作后，位置 \(1\) 是黑球，且这一次操作黑球没有被换走。设随机交换的位置是 \(x\) 和 \(y\)，没有被换走有两种情况：

    • \(x \neq 1\) 且 \(y \neq 1\) ，相当于交换两颗白球，这种情况的概率是 \(f[i-1] \cdot \frac{N-1}{N}\cdot\frac{N-1}{N}\)。
    • \(x = y = 1\)，这种情况的概率是 \(f[i-1] \cdot\frac{1}{N}\cdot\frac{1}{N}\)。

    因此总的概率是 \(f[i-1]\cdot \frac{N^2-2N+2}{N^2}\)

  • \(i-1\) 次操作后，位置 \(1\) 不是黑球。则设位置 \(p\) 是黑球，这种情况下要想 \(1\) 位置是黑球，随机的情况只有 \((x, y) = (1, p)\) 或 \((x, y) = (p, 1)\)，概率是 \(2\cdot \frac{1}{N}\cdot\frac{1}{N}\)，又因为位置 \(2\) 到位置 \(N\) 每个位置是黑球的概率是相等的，因此这种情况的概率是 \(\frac{1-f[i-1]}{N-1}\cdot (N-1) \cdot2\cdot \frac{1}{N}\cdot\frac{1}{N} = \frac{2(1-f[i-1])}{N^2}\)

综上，\(f[i] = f[i-1]\cdot \frac{N^2-2N+2}{N^2} + \frac{2(1-f[i-1])}{N^2} = f[i-1] \cdot \frac{N^2-2N}{N^2} + \frac{2}{N^2}\)

令 \(P = \frac{N^2-2N}{N^2}\)，\(Q = \frac{2}{N^2}\)，则 \(f[i] = Pf[i-1] + Q\)，可以在 \(O(K)\) 时间内算出 \(f[K]\) 的值，也可以把这个式子化成等比数列的形式，根据通项公式和快速幂在 \(O(logK)\) 内求出。

算出概率之后，求期望就很简单了。

参考代码 
#include <iostream>

using namespace std;
using LL = long long;

const LL mod = 998244353;

pair<LL, LL> exgcd(LL a, LL b)
{
    if (b == 0)
        return {1, 0};
    auto [x, y] = exgcd(b, a % b);
    return {y, x - a/b*y};
};

LL inv(LL a)
{
    auto [x, y] = exgcd(a, mod);
    if(x < 0)
        x += mod;
    return x;
}

int main()
{
    LL n, k;
    cin >> n >> k;
    if(n == 1)
    {
        cout << 1 << endl;
        return 0;
    }
    LL nn = n * n % mod;
    LL nn_inv = inv(nn);
    LL p = (nn - 2 * n % mod + mod) % mod * nn_inv % mod;
    LL q = 2 * nn_inv % mod;
    LL f = 1;

    while(k--)
        f = (p * f % mod + q) % mod;

    LL ans = f + (1-f+mod)%mod * (n+2) % mod * inv(2) % mod;
    ans %= mod;
    cout << ans << endl;
    return 0;
}

F - InterSections

题目大意

有 \(N(1 \le N \le 10 ^ 5)\) 个区间，第 \(i\) 个区间是 \([L_i, R_i]\)。

对于两个区间 \([l_a, r_a]\) 和 \([l_b, r_b]\)，若满足 \(l_a < l_b < r_a < r_b\) 或 \(l_b < l_a < r_b < r_a\)，则称这两个区间是相交的。

找出一个区间 \([l, r]\) 满足 \(0 \le l < r \le 10^9\) ，且与给定的 \(N\) 个区间相交次数最多，若有多个区间符合条件，输出 \(l\) 最小的区间，若仍然有多个区间符合条件，输出 \(r\) 最小的区间。

解题思路

设某个区间是 \([x, y]\)，则 \([x, y]\) 与某个区间 \([L_i, R_i]\) 相交的条件是 \(L_i < x < R_i < y\) 或 \(x < L_i < y < R_i\)，

考虑 \(0 \le x < y \le 10^9\) 的限制，可得 \(L_i < x < R_i < y \le 10^9\) 或 \(0 \le x < L_i < y < R_i\)，即：

\(\left\{\begin{matrix}L_i < x < R_i\\R_i < y \le 10^9\end{matrix}\right.\) 或 \(\left\{\begin{matrix}0 \le x < L_i\\L_i < y < R_i\end{matrix}\right.\)

将小于号变成小于等于号，即：

\(\left\{\begin{matrix}L_i + 1 \le x \le R_i - 1\\R_i + 1 \le y \le 10^9\end{matrix}\right.\) 或 \(\left\{\begin{matrix}0 \le x \le L_i - 1\\L_i + 1 \le y \le R_i - 1\end{matrix}\right.\)

第一个条件相当于区间拆成了左下角为 \((L_i + 1, R_i + 1)\)，右上角为 \((R_i - 1, 10 ^ 9)\) 的矩形，第二个条件相当于区间拆成了左下角为 \((0, L_i + 1)\)，右上角为 \((L_i - 1, R_i - 1)\) 的矩形。

可以证明对于同一个 \([L_i, R_i]\) 这两个条件拆出来的矩形在平面上是不重合的。

于是问题转化成，在平面上存在若干个矩形，找出一个点 \((x, y)\) 被最多的矩形包围。这可以通过扫描线算法在 \(O(NlogN)\) 的时间内实现。注意一些细节：

  • 题目要求相同条件下 \(x\) 最小，所以按照 \(x\) 坐标从左往右扫描。
  • 线段树中存储对应的 \(y\) 区间中出现次数的最大值，以及取得最大值对应的 \(y\) 值。
  • 每扫描到矩形的左侧的线段，就将对应的 \(y\) 区间 \([y_1, y_2]\) 范围的次数 \(+1\)，扫描到右侧线段就 \(-1\)。查询的时候直接查根节点。
  • 注意剔除一些不合法的矩形，合法的第一种矩形必须满足 \(L_i + 1 \le R_i-1\) 且 \(R_i + 1 \le 10 ^9\)，合法的第二种矩形必须满足 \(0 \le L_i-1\) 和 \(L_i + 1 \le R_i-1\)。由于可以取等号，所以严格意义上来讲平面上会有一些不是矩形的“线段”存在，这也是合法的。
  • 如果没有合法的矩形，答案应该输出 \((0, 1)\)
  • 扫描的时候，同样的 \(x\) 坐标，先扫矩形的左边，所有的矩形左边扫完之后才开始扫右边，这样答案才是对的，加个排序规则就好。
参考代码 
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

struct Line
{
    int x, y1, y2, k, id;
    bool operator<(const Line &other) const
    {
        if (x != other.x)
            return x < other.x;
        return k > other.k;
    }
};

struct SegTree
{
    vector<int> M, add, y;
    SegTree(int n) : M(4 * n), add(4 * n), y(4 * n)
    {
        auto build = [&y = this->y](auto &&self, int p, int beg, int end)
        {
            y[p] = beg;
            if (beg == end)
                return;
            int mid = (beg + end) / 2;
            int lch = p * 2, rch = p * 2 + 1;
            self(self, lch, beg, mid);
            self(self, rch, mid + 1, end);
        };

        build(build, 1, 1, n);
    }

    void pushdown(int p)
    {
        int lch = p * 2, rch = p * 2 + 1;
        if (add[p])
        {
            int k = add[p];
            add[p] = 0;
            M[lch] += k;
            M[rch] += k;
            add[lch] += k;
            add[rch] += k;
        }
    }

    void update(int p, int beg, int end, int l, int r, int k)
    {
        if (end < l || beg > r)
            return;
        if (beg >= l && end <= r)
        {
            M[p] += k;
            add[p] += k;
            return;
        }
        pushdown(p);
        int mid = (beg + end) / 2;
        int lch = p * 2, rch = p * 2 + 1;
        update(lch, beg, mid, l, r, k);
        update(rch, mid + 1, end, l, r, k);
        if (M[lch] >= M[rch])
        {
            M[p] = M[lch];
            y[p] = y[lch];
        }
        else
        {
            M[p] = M[rch];
            y[p] = y[rch];
        }
    }

    pair<int, int> query() const { return {M[1], y[1]}; }
};

int main()
{
    const int maxr = 1E9;
    int n;
    cin >> n;
    vector<int> L(n), R(n);
    vector<int> ys{maxr};
    for (int i = 0; i < n; i++)
    {
        cin >> L[i] >> R[i];
        ys.emplace_back(R[i] + 1);
        ys.emplace_back(L[i] + 1);
        ys.emplace_back(R[i] - 1);
    }
    sort(ys.begin(), ys.end());
    while (ys.back() > maxr)
        ys.pop_back();
    ys.erase(unique(ys.begin(), ys.end()), ys.end());

    auto get_rank = [&ys](int R) -> int
    {
        return lower_bound(ys.begin(), ys.end(), R) - ys.begin() + 1;
    };

    int len = ys.size();

    vector<Line> lines;
    lines.reserve(4 * n);
    for (int i = 0; i < n; i++)
    {
        if (L[i] + 1 <= R[i] - 1 && R[i] + 1 <= maxr)
        {
            int rk = get_rank(R[i] + 1);
            lines.push_back({L[i] + 1, rk, len, 1, i});
            lines.push_back({R[i] - 1, rk, len, -1, i});
        }
        if (0 <= L[i] - 1 && L[i] + 1 <= R[i] - 1)
        {
            int rk1 = get_rank(L[i] + 1);
            int rk2 = get_rank(R[i] - 1);
            lines.push_back({0, rk1, rk2, 1, i});
            lines.push_back({L[i] - 1, rk1, rk2, -1, i});
        }
    }
    if (lines.empty())
    {
        cout << "0 1" << endl;
        return 0;
    }
    sort(lines.begin(), lines.end());
    SegTree t(len);
    int M = 0, x = 0, y = 1;
    for (auto line : lines)
    {
        t.update(1, 1, len, line.y1, line.y2, line.k);
        auto [tM, ty] = t.query();
        if (tM > M || (tM == M && line.x == x && ty < y))
        {
            M = tM;
            x = line.x;
            y = ty;
        }
    }
    y = ys[y - 1];
    cout << x << ' ' << y << endl;
    return 0;
}
最后更新: 2024-07-24
创建日期: 2024-07-21