链接：https://atcoder.jp/contests/abc417

A – A Substring

算法：

    模拟。

思路：

    无。

关键代码：

void solve()
{
    int n, a, b;
    string s;
    cin >> n >> a >> b >> s;

    for (int i = a; i < n - b; ++i)
        cout << s[i];
    cout << endl;
}

B – Search and Delete

算法：

    模拟。

思路：

    无。

关键代码：

void solve()
{
    int n, m;
    cin >> n >> m;
    vector<int> a(n + 10), b(m + 10);
    cin >> a >> b;

    vector<int> st(n + 10, 0);
    for (int i = 0; i < m; ++i)
    {
        int op = b[i];

        for (int i = 0; i < n; ++i)
        {
            if (a[i] == op && !st[i])
            {
                st[i] = 1;
                break;
            }
        }
    }

    for (int i = 0; i < n; ++i)
    {
        if (!st[i])
            cout << a[i] << ' ';
    }

    cout << endl;
}

C – Distance Indicators

算法：

    哈希表。

思路：

    无。

关键代码：

void solve()
{
    int n;
    cin >> n;
    vi a(n + 10);
    for (int i = 1; i <= n; ++i)
        cin >> a[i];

    ll ans = 0;
    map<int, int> st;
    for (int i = 1; i <= n; ++i)
    {
        if (st.count(i - a[i]))
            ans += st[i - a[i]];

        ++st[a[i] + i];
    }

    cout << ans << endl;
}

D – Takahashi’s Expectation

算法：

    模拟。

思路：

    由于题目中初始心情值 x 的范围非常大，最大可达 \(10^9\)，而每个礼物的参数 \(P_i, A_i, B_i\) 都限制在较小的范围内（1 到 500），这使得心情减少值 \(B_i\) 的总和 \(\sum B_i\) 和心情增加最大值 \(a_{max}\) 相对较小。

    因此，当初始心情 x 超过了阈值 \(b_{sum}+a_{max}\) 时，可以直接判定 Takahashi 在接受所有礼物之后，心情将只会因为礼物的负面影响而递减，且最终心情不会低于 \(x – b_{sum}\)。

    基于此，我们可以在处理每个询问时加入如下剪枝：

• 如果 \(x > b_{sum} + a_{max}\)，则直接输出结果为 \(x – b_{sum}\)，无需模拟所有礼物。

    此剪枝有效地减少了大量不必要的模拟运算，提升了程序的运行效率。

关键代码：

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

    vector<int> a(n), b(n), p(n);
    for (int i = 0; i < n; ++i)
        cin >> p[i] >> a[i] >> b[i];

    ll sum = accumulate(all(b), 0ll);
    ll maxx = sum + ranges::max(a);

    int Q;
    cin >> Q;
    while (Q--)
    {
        int x;
        cin >> x;

        if (x > maxx)
        {
            cout << x - sum << endl;
            continue;
        }

        for (int i = 0; i < n; ++i)
        {
            if (x <= p[i])
                x += a[i];
            else
                x -= b[i];

            x = max(x, 0);
        }

        cout << x << endl;
    }
}

E – A Path in A Dictionary

算法：

    dfs，图论。

思路：

    使用邻接表存储图，对于每条点多能到达的点进行升序排序。

    定义一个数组 f，其中 f[u] 表示在当前搜索中，点 u 的前驱节点，也就是说，从起点 x 出发，到达 u 的字典序最小路径中，u 是由 f[u] 这个点访问到的。

    具体做法是：从起点 x 开始进行 dfs ，在遍历相邻节点时，优先访问字典序更小的点。对于每个未被访问过的邻居点 v，将 f[v] 赋值为当前节点 u，表示路径上 v 是通过 u 到达的，然后递归继续 dfs。

    完成 dfs 后，从终点 y 开始，按照 f[y]、f[f[y]] 等前驱节点依次回溯，直到回到起点 x，这条回溯得到的路径就是从 x 到 y 的字典序最小简单路径。

关键代码：

void solve()
{
    int n, m, x, y;
    cin >> n >> m >> x >> y;

    vector<vector<int>> g(n + 10);
    for (int i = 0; i < m; ++i)
    {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }

    for (int i = 1; i <= n; ++i)
        ranges::sort(g[i]);

    vector<int> f(n + 10, -1);
    function<void(int)> dfs = [&](int u) -> void
    {
        for (auto v : g[u])
        {
            if (f[v] == -1)
            {
                f[v] = u;
                dfs(v);
            }
        }
    };

    f[x] = x;
    dfs(x);

    vector<int> ans;
    while (y != x)
    {
        ans.push_back(y);
        y = f[y];
    }

    ans.push_back(x);
    ranges::reverse(ans);

    for (auto x : ans)
        cout << x << ' ';
    cout << endl;
}

F – Random Gathering

算法：

    线段树，数论，期望。

思路：

    设 \(p_i\) 表示当前第 \(i\) 个盘子的期望石子数。对于一次操作 \([l,r]\)，区间期望和为：

\(S=\sum_{i=l}^{r} p_i\)

    由于区间内每个位置被选中的概率相同，操作后区间中任一位置的期望都变为：

\(\frac{S}{r-l+1}\)

    因此只需维护一个带赋值懒标记的线段树，并在模意义下用逆元处理分母即可实现该更新。

关键代码：

const int MOD = 998244353;

template <typename T>
struct SegmentTreeLazySumAssign
{
    struct Node
    {
        int l, r;
        T sum;
        T assign; // 懒标记，-1 表示没有赋值操作
    };

    int N;
    vector<Node> tr;
    vector<T> v;

    SegmentTreeLazySumAssign(int _N, const vector<T> &_v)
    {
        N = _N;
        v.resize(N + 10);
        for (int i = 1; i <= N; ++i)
            v[i] = _v[i];
        tr.resize(4 * N);
        build(1, 1, N);
    }

#define LC (u << 1)
#define RC ((u << 1) | 1)

    inline void pushup(int u)
    {
        tr[u].sum = (tr[LC].sum + tr[RC].sum) % MOD;
    }

    inline void apply_assign(int u, T val)
    {
        tr[u].sum = (tr[u].r - tr[u].l + 1) * val % MOD;
        tr[u].assign = val;
    }

    inline void pushdown(int u)
    {
        if (tr[u].assign != -1)
        {
            apply_assign(LC, tr[u].assign);
            apply_assign(RC, tr[u].assign);
            tr[u].assign = -1;
        }
    }

    inline void build(int u, int l, int r)
    {
        tr[u] = {l, r, 0, -1};
        if (l == r)
        {
            tr[u].sum = v[l];
            return;
        }
        int mid = (l + r) >> 1;
        build(LC, l, mid);
        build(RC, mid + 1, r);
        pushup(u);
    }

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

        pushdown(u);

        T sum = 0;
        int mid = (tr[u].l + tr[u].r) >> 1;
        if (l <= mid)
            sum = (sum + query(LC, l, r)) % MOD;
        if (r > mid)
            sum = (sum + query(RC, l, r)) % MOD;
        return sum % MOD;
    }

    inline void update(int u, int l, int r, T val)
    {
        if (tr[u].l >= l && tr[u].r <= r)
        {
            apply_assign(u, val);
            return;
        }

        pushdown(u);
        int mid = (tr[u].l + tr[u].r) >> 1;
        if (l <= mid)
            update(LC, l, r, val);
        if (r > mid)
            update(RC, l, r, val);
        pushup(u);
    }

    inline T query(int l, int r) { return query(1, l, r); }

    inline void update(int l, int r, T val) { update(1, l, r, val); }
};

ll qmi(ll a, ll b, ll p)
{
    ll ans = 1 % p;
    while (b)
    {
        if (b & 1)
            ans = ans * a % p;
        b >>= 1;
        a = a * a % p;
    }

    return ans;
}

ll inv(ll q, ll mod)
{
    return qmi(q, mod - 2, mod);
}

void solve()
{
    int n, m;
    cin >> n >> m;
    vector<ll> a(n + 10);
    for (int i = 1; i <= n; ++i)
        cin >> a[i];

    SegmentTreeLazySumAssign<ll> seg(n, a);

    for (int i = 0; i < m; ++i)
    {
        int l, r;
        cin >> l >> r;

        ll sum = seg.query(l, r) % MOD;
        ll val = sum * inv(r - l + 1, MOD) % MOD;
        seg.update(l, r, val);
    }

    for (int i = 1; i <= n; ++i)
        cout << seg.query(i, i) << ' ';
    cout << endl;
}

G – Binary Cat

    还没补。