AtCoder Beginner Contest 417

A A Substring

You are given an N-character string S consisting of lowercase English letters.
Output the string of N−A−B characters obtained by removing the first A characters and the last B characters from S.

翻译：

给定一个由 N 个小写英文字母组成的字符串 S。
输出 S 字符串移除前 A个字符，后 B 个字符后的字符串。

分析：使用string中的 s.erase(pos, k) 删除 s中的从 pos 下标开始的连续 k个元素。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e6 + 10, inf = 0x3f3f3f3f;

void solve() {
    int n, a, b;
    string s;
    cin >> n >> a >> b >> s;
    s.erase(0, a);
    s.erase(s.size()-b, b); 
    cout << s;
}

int main() {
    int T = 1; while (T--) solve();
    return 0;
}

B Search and Delete

Takahashi has an integer sequence $A=(A_1,A_2,\dots ,A_N)$ of length N.
It is guaranteed that A is non-decreasing.

Takahashi performs M operations on this integer sequence.
In the i-th operation $(1\le i\le M)$, he performs the following operation:

If the sequence A contains $B_i$ as an element, select one such element and delete it. If no such element exists, do nothing.
Note that since A is non-decreasing, the sequence after the operation is uniquely determined regardless of the choice of element, and remains non-decreasing.

Find A after performing M operations.

翻译：

高桥有一个长度为 N 的整数序列 $A=(A_1,A_2,\dots ,A_N)$。
保证 A 是非递减的。

高桥对这个整数序列执行 M 次操作。在第 i $(1\le i\le M)$ 次操作中，他执行以下操作：

如果序列 A 包含 $B_i$ 作为元素，选择其中一个这样的元素并删除它。如果不存在这样的元素，则不执行任何操作。
注意，由于 A 是非递减的，操作后的序列无论选择哪个元素都是唯一确定的，并且仍然保持非递减。

执行 M 次操作后找到 A 。

分析：数据范围很小，直接暴力模拟即可。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e6 + 10, inf = 0x3f3f3f3f;

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

    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (b[i] == a[j]) {
                a[j] = -1;
                break;
            }
        }
    }

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

int main() {
    int T = 1; while (T--) solve();
    return 0;
}

C Distance Indicators

You are given an integer sequence $A=(A_1,A_2,...A_N)$ of length N.

Find how many pairs of integers (i,j) ($1\le i<j\le N$) satisfy $j-i=A_i-A_j$.

Constraints：$1\le N\le 2\times 10^5,1\le A_i\le 2\times 10^5(1\le i\le N)$。

翻译：

你被给定一个长度为 N 的整数序列 $A=(A_1,A_2,...A_N)$。

找出有多少对整数 (i,j) ($1\le i<j\le N$) 满足 $j-i=A_i-A_j$。

约束：$1\le N\le 2\times 10^5,1\le A_i\le 2\times 10^5(1\le i\le N)$。

分析：数据范围较大，枚举复杂度为 $O(n^2)$，考虑将原式变形：移项得 $j-a_j=i+a_i\ge 2$，可以发现左右两边均是与当前位置有关的信息。

用 $st[x]++$ 表示 $x$ 出现的次数加一。

由于答案的更新在 $st$ 更新前，所以保证了 $i<j$。

其实，无论答案更新在前还是在后，本题都不影响答案。证明如下：

• 由于后续本就需要计算，所以只需要考虑当前是否影响答案即可。
• 会影响答案的一定是 $i+a_i=i-a_i$，但是这是不可能的，所以不会影响答案。

答案需要开 long long。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e5 + 5, inf = 0x3f3f3f3f;
void solve() {
    ll n, ans = 0;
    cin >> n;
    vector<int> a(n + 1);
    map<int, int> st;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        ans += st[i - a[i]];
        st[i + a[i]]++;
    }
    cout << ans << "\n";
}
int main() {
    int T = 1;
    while (T--)
        solve();
    return 0;
}

D Takahashi’s Expectation

Takahashi will receive $N$ presents.

He has a parameter called mood, which is a non-negative integer, and his mood changes every time he receives a present. Each present has three parameters: value $P$, mood increase $A$, and mood decrease $B$, and his mood changes as follows based on these parameters:

• When the value $P$ of the received present is greater than or equal to his mood, he is happy with the present, and his mood increases by $A$.
• When the value $P$ of the received present is less than his mood, he is disappointed with the present, and his mood decreases by $B$. However, if his mood is originally less than $B$, it becomes $0$.

The $i$-th $(1\le i\le N)$ present he receives has value $P_i$, mood increase $A_i$, and mood decrease $B_i$.

You are given $Q$ questions, so answer all of them. In the $i$-th $(1\le i\le Q)$ question, you are given a non-negative integer $X_i$, so answer the following question:

Find Takahashi’s mood after receiving all $N$ presents when his mood is initially $X_i$.

翻译：

高桥将收到 $N$ 份礼物。

他有一个名为心情的参数，是一个非负整数，每次收到礼物时，他的心情都会发生变化。每件礼物都有三个参数：价值 $P$ 、心情上升 $A$ 、心情下降 $B$ ，根据这些参数，他的心情会发生如下变化：

• 当收到的礼物的值 $P$ 大于或等于他的心情时，他对礼物感到高兴，心情增加 $A$ 。
• 当收到的礼物的价值 $P$ 小于他的心情时，他对礼物感到失望，心情会降低 $B$ 。但是，如果他的心情原本小于 $B$ ，则会变成 $0$ 。

他收到的 $i$ /- $(1\le i\le N)$ 份礼物的价值为 $P_i$ ，心情增加 $A_i$ ，心情减少 $B_i$ 。

你有 $Q$ 个问题，请回答所有问题。在 $i$ - $(1\le i\le Q)$ 题中，你得到了一个非负整数 $X_i$ ，请回答下面的问题：

求高桥收到所有 $N$ 礼物后的心情，当他的心情最初为 $X_i$ 时。

分析：
题目中数据如果采用暴力，复杂度为 $O(nq)$，约 $5e9$——这里其实可以通过一些瞎搞的做法降低常数，大概降低 10 倍就可以通过了。自然，这在复杂度上是比较危险的。

正确的解法是这样的：可以看题目发现，$P_i,A_i,B_i\in [1,500]$，$X_i\in [0,10^9]$。
可以想到 $X_i$ 的范围如此之大，实际上只需要和 $500$ 进行比较，这是否可以考虑预处理一些较小的解，然后通过将 $X$ 快速转为该区间的解，貌似可行。

预处理 $d{p}_{i,j}$ 表示开始情绪值为 $j$，从第 $i$ 个礼物开始收取完所有礼物后的情绪值。

初始化：$d{p}_{n+1,j}=j$
状态转移：
$$d{p}_{i,j}=\{\begin{array}{ll}d{p}_{i+1,j+a_i}& \text{ if }j\le p_i\\ d{p}_{i+1,j-a_i}& \text{ if }j>p_i\end{array}$$
目标：$d{p}_{1,x}$

• 当 $x\le 1000$，可以直接得到答案 $d{p}_{1,x}$；
• 当 $x>1000$，可以通过 $x-{\sum }_{i=1}^k{B}_i$，使得 $x\le 1000$。

由于 $B_i>0$，所以构造的 $B$ 前缀和 $S_i$ 是单调递增的，可以二分得到答案。
$x-S_i\le 1000\to S_i\ge x-1000$。
如果不存在 $i$ 满足该不等式，则证明 $S_n<x-1000$，答案为 $x-S_n$；
如果存在 $i$ 满足该不等式，则证明可以通过 $x-S_i$ 使得 $x\le 1000$，所以答案为 $d{p}_{i+1,x-S_i}$。

 #include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e4 + 5, inf = 0x3f3f3f3f;
int n, q, x, p[N], a[N], b[N], s[N], dp[N][1505];
signed main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> p[i] >> a[i] >> b[i];
        s[i] = s[i - 1] + b[i];
    }
    for (int i = 0; i <= 1500; i++)
        dp[n + 1][i] = i;
    for (int i = n; i >= 0; i--)
        for (int j = 0; j <= 1000; j++)
            if (p[i] >= j)
                dp[i][j] = dp[i + 1][j + a[i]];
            else
                dp[i][j] = dp[i + 1][max(0, j - b[i])];
    cin >> q;
    while (q--) {
        cin >> x;
        if (x <= 1000) {
            cout << dp[1][x] << "\n";
            continue;
        }
        int i = lower_bound(s + 1, s + 1 + n, x - 1000) - s;
        if (i == n + 1)
            cout << x - s[n] << "\n";
        else
            cout << dp[i + 1][x - s[i]] << "\n";
    }
    return 0;
}

E A Path in A Dictionary

You are given a simple connected undirected graph G with N vertices and M edges.
The vertices of G are numbered vertex 1, vertex 2, …, vertex N, and the i-th $(1\le i\le M)$ edge connects vertices $U_i$ and $V_i$.

Find the lexicographically smallest simple path from vertex X to vertex Y in G.
That is, find the lexicographically smallest among the integer sequences $P=(P1,P2,\dots ,P_{\mid P\mid })$ that satisfy the following conditions:

• $1\le P_i\le N$
• If $i\ne j$, then $P_i\ne P_j$.
• $P_1=X$ and $P_{\mid P\mid }=Y$.
• For $1\le i\le \mid P\mid -1$, there exists an edge connecting vertices $P_i$ and $P_{i+1}$.

One can prove that such a path always exists under the constraints of this problem.

You are given T test cases, so find the answer for each.

翻译：
给定一个简单的连通无向图 G ，它有 N 个顶点和 M 条边。
G 的顶点编号为顶点 1、2 、… 、N ，第 i 条 $(1\le i\le M)$ 边连接顶点 $U_i$ 和 $V_i$。
​在 G 中，找到从顶点 X 到顶点 Y 的字典序最小的简单路径。
也就是说，找到满足以下条件的整数序列 $P=(P1,P2,\dots ,P_{\mid P\mid })$ 中字典序最小的序列：

• $1\le P_i\le N$
• 如果 $i\ne j$, 那么 $P_i\ne P_j$.
• $P_1=X$ 且 $P_{\mid P\mid }=Y$.
• 对于 $1\le i\le \mid P\mid -1$, 存在一条边连接顶点 $P_i$ 和 $P_{i+1}$.

可以证明，在问题的约束条件下，这样的路径总是存在。
给出了 T 个测试用例，所以找出每个的答案。

分析：建图后按节点升序排序，dfs 遍历即可。

#include <bits/stdc++.h>
#define int long long
using namespace std;
typedef long long ll;
const int N = 1e6 + 10, inf = 0x3f3f3f3f, inf2 = 1e18;
vector<int> G[N];
int a[N], n, m, x, y, p;
bool st[N], flag;

void dfs(int u) {
    if (flag) return;
    st[u] = 1, a[++p] = u;
    if (u == y) {
        for (int i = 1; i <= p; i++)
            cout << a[i] << " \n"[i == p];
        flag = 1; return;
    }
    for (auto& v : G[u]) {
        if (st[v]) continue;
        dfs(v);
    }
    --p;
}
void solve() {
    cin >> n >> m >> x >> y;
    p = 0, flag = 0;
    memset(st, 0x00, sizeof st);
    for (int i = 1; i <= n; i++) G[i].clear();
    for (int i = 1, u, v; i <= m; i++) {
        cin >> u >> v;
        G[u].push_back(v), G[v].push_back(u);
    }
    for (int i = 1; i <= n; i++) sort(G[i].begin(), G[i].end());
    dfs(x);
}
signed main() {
    int T = 1;
    cin >> T;
    while (T--) solve();
    return 0;
}

F Random Gathering

There are $N$ plates arranged from left to right as plate $1,$ plate $2,\dots ,$ plate $N$. Initially, plate $i(1\le i\le N)$ contains $A_i$ stones.

You will perform $M$ operations on these plates. In the $i$-th operation $(1\le i\le M)$, two integers $L_i$ and $R_i$ are given, and the following operations are performed in order:

• Remove all stones from the $R_i-L_i+1$ plates: plate $L_i,$ plate $L_i+1,\dots ,$ plate $R_i$.
• Uniformly randomly choose an integer between $L_i$ and $R_i$, inclusive, and let it be $x$.
• Place all the removed stones on plate $x$.

For $i=1,2,\dots ,N$, find the expected number, modulo $998244353$, of stones placed on plate $i$ when all $M$ operations are completed.

Finding expected value modulo $998244353$

It can be proved that the expected value you seek is always a rational number. Also, under the constraints of this problem, when that value is expressed as an irreducible fraction $\frac{P}{Q}$, it can be proved that $Q\not\equiv 0(\mathrm{mod}998244353)$. Therefore, there is a unique integer $R$ such that $R\times Q\equiv P(\mathrm{mod}998244353),0\le R<998244353$. Finding the expected value modulo $998244353$ means finding this $R$.

翻译：

有 $N$ 个盘子，从左到右排列为盘子 $1,$ 盘子 $2,\dots ,$ 盘子 $N$ 。最初，板块 $i(1\le i\le N)$ 包含 $A_i$ 块石头。

您将在这些板块上进行 $M$ 次操作。在 $i$ -th 运算 $(1\le i\le M)$ 中，给出了两个整数 $L_i$ 和 $R_i$ ，并依次进行了以下运算：

• 移除 $R_i-L_i+1$ 盘中的所有棋子：盘子 $L_i,$ 盘子 $L_i+1,\dots ,$ 盘子 $R_i$ 。
• 在 $L_i$ 和 $R_i$ （含）之间统一随机选择一个整数，让它成为 $x$ 。
• 将所有取出的棋子放入棋盘 $x$ 中。

就 $i=1,2,\dots ,N$ 而言，求当所有 $M$ 运算完成后，放置在 $i$ 盘中的石子的预期数目（模为 $998244353$ ）。

求模数 $998244353$ 的期望值。

可以证明，所求的期望值总是一个有理数。另外，在本题的限制条件下，当该值表示为不可约分数 $\frac{P}{Q}$ 时，可以证明 $Q\not\equiv 0(\mathrm{mod}998244353)$ 。因此，存在一个唯一的整数 $R$ ，即 $R\times Q\equiv P(\mathrm{mod}998244353),0\le R<998244353$ 。求模为 $998244353$ 的期望值就是求这个 $R$ 。

分析：

根据期望值的线性关系，可知每个盘子操作后放的石子的期望数量 $E=\frac{{\sum }_{i=l}^r{a}_i}{r-l+1}$
区间求和 $[l,r]={\sum }_{i=l}^r{a}_i$，区间修改 $[l,r]$ 为 $E$，故而维护一个懒标记的线段树即可。
给定的模数为质数，使用费马小定理做逆元处理除法取模。

#include <bits/stdc++.h>
#define int long long
#define lowbit(x) (x & (-x))
typedef long long ll;
using namespace std;
const int N = 2e5 + 5, inf = 0x3f3f3f3f;
const int P = 998244353;
int n, m, a[N];
struct Node {
    int l, r, sum, tag;
} tr[N << 2];

void pushup(Node& u, Node& l, Node& r) {
    u.sum = l.sum + r.sum;
    u.sum %= P;
    u.tag = 0;
}
void pushup(int u) {
    pushup(tr[u], tr[u << 1], tr[u << 1 | 1]);
}
void pushdown(Node& u, int tag) {
    u.tag = tag;
    u.sum = tag * (u.r - u.l + 1) % P;
    u.sum %= P;
}
void pushdown(int u) {
    if (tr[u].tag) {
        pushdown(tr[u << 1], tr[u].tag);
        pushdown(tr[u << 1 | 1], tr[u].tag);
        tr[u].tag = 0;
    }
}
void build(int u, int l, int r) {
    if (l == r) {
        tr[u] = {l, r, a[l], 0};
        return;
    }
    int mid = l + r >> 1;
    tr[u] = {l, r, 0, 0};
    build(u << 1, l, mid);
    build(u << 1 | 1, mid + 1, r);
    pushup(u);
}

void modify(int u, int l, int r, int tag) {
    if (l > tr[u].r || r < tr[u].l)
        return;
    if (tr[u].l >= l && tr[u].r <= r) {
        pushdown(tr[u], tag);
        return;
    }
    pushdown(u);
    int mid = tr[u].l + tr[u].r >> 1;
    if (l <= mid)
        modify(u << 1, l, r, tag);
    if (r > mid)
        modify(u << 1 | 1, l, r, tag);
    pushup(u);
}
int query(int u, int l, int r) {
    if (tr[u].l >= l && tr[u].r <= r)
        return tr[u].sum;
    pushdown(u);

    int mid = tr[u].l + tr[u].r >> 1, ans = 0;
    if (l <= mid)
        ans += query(u << 1, l, r), ans %= P;
    if (r > mid)
        ans += query(u << 1 | 1, l, r), ans %= P;
    return ans;
}
int fpow(int a, int b) {
    int res = 1;
    while (b) {
        if (b & 1)
            res = res * a % P;
        a = a * a % P, b >>= 1;
    }
    return res % P;
}
signed main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    build(1, 1, n);
    int l, r;
    while (m--) {
        cin >> l >> r;
        int x = query(1, l, r) * fpow(r - l + 1, P - 2) % P;
        modify(1, l, r, x);
    }
    for (int i = 1; i <= n; i++) {
        int x = query(1, i, i);
        cout << x << " \n"[i == n];
    }
    return 0;
}

G Binary Cat

Define strings $S_0$ and $S_1$ as $S_0=$ 0 and $S_1=$ 1.
You are given $Q$ queries, so process them in order.
In the $i$-th query $(1\le i\le Q)$, you are given a triple of integers $(L_i,R_i,X_i)$.

Let $S_{i+1}$ be the string obtained by concatenating $S_{L_i}$ and $S_{R_i}$ in this order. Then, find the $X_i$-th character of $S_{i+1}$.

It is guaranteed that $X_i$ is at most the length of $S_{i+1}$.

翻译：
将字符串 $S_0$ 和 $S_1$ 定义为 $S_0=0$ 和 $S_1=1$ 。
我们会得到 $Q$ 个查询，请按顺序处理它们。
在 $i$ -查询 $(1\le i\le Q)$ 中，你会得到一个整数三元组 $(L_i,R_i,X_i)$ 。

假设 $S_{i+1}$ 是按照这个顺序连接 $S_{L_i}$ 和 $S_{R_i}$ 得到的字符串。然后，找出 $S_{i+1}$ 的 $X_i$ -th 字符。

可以保证 $X_i$ 最多是 $S_{i+1}$ 的长度。