AtCoder Beginner Contest 351 （ABCDEG题）视频讲解

A - Buildings

Problem Statement

There are $N$ buildings aligned in a row. The $i$ -th building from the left has a height of $H_i$ .
Determine if there is a building taller than the first one from the left. If such a building exists, find the position of the leftmost such building from the left.

Constraints

$\leq N \leq 100$
$\leq H_i \leq 100$
All input values are integers.

Input

The input is given from Standard Input in the following format:

$N$
$H_1$ $H_2$ $\ldots$ $H_N$

Output

If no building is taller than the first one from the left, print -1.
If such a building exists, print the position (index) of the leftmost such building from the left.

Sample Input 1

4
3 2 5 2

Sample Output 1

The building taller than the first one from the left is the third one from the left.

Sample Input 2

3
4 3 2

Sample Output 2

-1

No building is taller than the first one from the left.

Sample Input 3

7
10 5 10 2 10 13 15

Sample Output 3

The buildings taller than the first one from the left are the sixth and seventh ones. Among them, the leftmost is the sixth one.

Solution

具体见文末视频。

Code

#include <bits/stdc++.h>
#define fi first
#define se second
#define int long long

using namespace std;

typedef pair<int, int> PII;
typedef long long LL;

signed main() {
	cin.tie(0);
	cout.tie(0);
	ios::sync_with_stdio(0);

	int n, a, x;
	cin >> n >> a;

	for (int i = 2; i <= n; i ++) {
		cin >> x;
		if (x > a) {
			cout << i << endl;
			return 0;
		}
	}
	cout << -1 << endl;

	return 0;
}

B - AtCoder Amusement Park

Problem Statement

The AtCoder amusement park has an attraction that can accommodate $K$ people. Now, there are $N$ groups lined up in the queue for this attraction.
The $i$ -th group from the front $(1\leq i\leq N)$ consists of $A_i$ people. For all $i$ $(1\leq i\leq N)$ , it holds that $A_i \leq K$ .
Takahashi, as a staff member of this attraction, will guide the groups in the queue according to the following procedure.
Initially, no one has been guided to the attraction, and there are $K$ empty seats.

If there are no groups in the queue, start the attraction and end the guidance. Compare the number of empty seats in the attraction with the number of people in the group at the front of the queue, and do one of the following: If the number of empty seats is less than the number of people in the group at the front, start the attraction. Then, the number of empty seats becomes $K$ again. Otherwise, guide the entire group at the front of the queue to the attraction. The front group is removed from the queue, and the number of empty seats decreases by the number of people in the group. Go back to step 1.

Here, no additional groups will line up after the guidance has started. Under these conditions, it can be shown that this procedure will end in a finite number of steps. Determine how many times the attraction will be started throughout the guidance. ## Constraints

$1\leq N\leq 100$
$1\leq K\leq 100$
$1\leq A_i\leq K\ (1\leq i\leq N)$
All input values are integers.

Input

The input is given from Standard Input in the following format:

$N$ $K$
$A_1$ $A_2$ $\ldots$ $A_N$

Output

Print the answer.

Sample Input 1

7 6
2 5 1 4 1 2 3

Sample Output 1

Initially, the seven groups are lined up as follows:

Part of Takahashi’s guidance is shown in the following figure:

Initially, the group at the front has $2$ people, and there are $6$ empty seats. Thus, he guides the front group to the attraction, leaving $4$ empty seats.
Next, the group at the front has $5$ people, which is more than the $4$ empty seats, so the attraction is started.
After the attraction is started, there are $6$ empty seats again, so the front group is guided to the attraction, leaving $1$ empty seat.
Next, the group at the front has $1$ person, so they are guided to the attraction, leaving $0$ empty seats.
In total, he starts the attraction four times before the guidance is completed.
Therefore, print 4.

Sample Input 2

7 10
1 10 1 10 1 10 1

Sample Output 2

Sample Input 3

15 100
73 8 55 26 97 48 37 47 35 55 5 17 62 2 60

Sample Output 3

Solution

具体见文末视频。

Code

#include <bits/stdc++.h>
#define fi first
#define se second
#define int long long

using namespace std;

typedef pair<int, int> PII;
typedef long long LL;

signed main() {
	cin.tie(0);
	cout.tie(0);
	ios::sync_with_stdio(0);

	int n, m;
	cin >> n >> m;

	int res = 0, tot = 0, x;
	for (int i = 1; i <= n; i ++) {
		cin >> x;
		if (tot + x > m) {
			res ++, tot = 0;
		}
		tot += x;
	}
	if (tot) res ++;

	cout << res << endl;

	return 0;
}

C - Sigma Problem

Problem Statement

For positive integers $x$ and $y$ , define $f (x, y)$ as the remainder of $(x + y)$ divided by $10^8$ .
You are given a sequence of positive integers $(A_1, \ldots, A_N)$ of length $N$ . Find the value of the following expression:

$\displaystyle \sum_{i=1}^{N-1}\sum_{j=i+1}^N f(A_i,A_j)$.
## Constraints

$\leq N \leq 3\times 10^5$
$KaTeX parse error: Expected 'EOF', got '&' at position 12: 1 \leq A_i &̲lt; 10^8$
All input values are integers.

Input

The input is given from Standard Input in the following format:

$N$
$A_1$ $\ldots$ $A_N$

Output

Print the answer.

Sample Input 1

3
3 50000001 50000002

Sample Output 1

100000012

$f(A_1,A_2)=50000004$
$f(A_1,A_3)=50000005$
$f(A_2,A_3)=3$
Thus, the answer is $f(A_1,A_2) + f(A_1,A_3) + f(A_2,A_3) = 100000012$ .
Note that you are not asked to compute the remainder of the sum divided by $10^8$ .

Sample Input 2

5
1 3 99999999 99999994 1000000

Sample Output 2

303999988

Solution

具体见文末视频。

Code

#include <bits/stdc++.h>
#define fi first
#define se second
#define int long long

using namespace std;

typedef pair<int, int> PII;
typedef long long LL;

signed main() {
	cin.tie(0);
	cout.tie(0);
	ios::sync_with_stdio(0);

	int n;
	cin >> n;

	std::vector<int> a(n + 1);
	int tot = 0, res = 0;
	for (int i = 1; i <= n; i ++) {
		cin >> a[i];
		res += tot + a[i] * (i - 1), tot += a[i];
	}
	sort(a.begin() + 1, a.end());

	int tmp = 1e8;
	for (int i = 1; i < n; i ++) {
		auto it = lower_bound(a.begin() + i + 1, a.end(), tmp - a[i]);
		if (it == a.end()) continue;
		int id = it - a.begin();
		res -= tmp * (n - id + 1);
	}

	cout << res << endl;

	return 0;
}

D - Another Sigma Problem

Problem Statement

For positive integers $x$ and $y$ , define $f (x, y)$ as follows:
Interpret the decimal representations of $x$ and $y$ as strings and concatenate them in this order to obtain a string $z$ . The value of $f (x, y)$ is the value of $z$ when interpreted as a decimal integer.
For example, $f (3, 14) = 314$ and $f (100, 1) = 1001$ .
You are given a sequence of positive integers $(A_1, \ldots, A_N)$ of length $N$ . Find the value of the following expression modulo $998244353$ :

$\displaystyle \sum_{i=1}^{N-1}\sum_{j=i+1}^N f(A_i,A_j)$.
## Constraints

$\leq N \leq 2 \times 10^5$
$\leq A_i \leq 10^9$
All input values are integers.

Input

The input is given from Standard Input in the following format:

$N$
$A_1$ $\ldots$ $A_N$

Output

Print the answer.

Sample Input 1

3
3 14 15

Sample Output 1

$f(A_1, A_2) = 314$
$f(A_1, A_3) = 315$
$f(A_2, A_3) = 1415$
Thus, the answer is $f(A_1, A_2) + f(A_1, A_3) + f(A_2, A_3) = 2044$ .

Sample Input 2

5
1001 5 1000000 1000000000 100000

Sample Output 2

625549048

Be sure to calculate the value modulo $998244353$ .

Solution

具体见文末视频。

Code

#include <bits/stdc++.h>
#define fi first
#define se second
#define int long long

using namespace std;

typedef pair<int, int> PII;
typedef long long LL;

const int N = 2e5 + 10, mod = 998244353;

int n;
int a[N], s[N];

int dec(int x) {
	int res = 0;
	while (x) res ++, x /= 10;
	return res;
}
int ksm(int a, int b) {
	int res = 1;
	while (b) {
		if (b & 1) res = res * a % mod;
		a = a * a % mod;
		b >>= 1;
	}
	return res;
}

signed main() {
	cin.tie(0);
	cout.tie(0);
	ios::sync_with_stdio(0);

	cin >> n;

	for (int i = 1; i <= n; i ++)
		cin >> a[i];
	reverse(a + 1, a + 1 + n);
	for (int i = 1; i <= n; i ++)
		s[i] = (s[i - 1] + ksm(10, dec(a[i]))) % mod;

	int res = 0;
	for (int i = 1; i <= n; i ++) {
		res = (res + s[i - 1] * a[i]) % mod;
		res = (res + a[i] * (n - i) % mod) % mod;
	}

	cout << res << endl;

	return 0;
}

E - Yet Another Sigma Problem

Problem Statement

For strings $x$ and $y$ , define $f (x, y)$ as follows:
$f (x, y)$ is the length of the longest common prefix of $x$ and $y$ .
You are given $N$ strings $(S_1, \ldots, S_N)$ consisting of lowercase English letters. Find the value of the following expression:

$\displaystyle \sum_{i=1}^{N-1}\sum_{j=i+1}^N f(S_i,S_j)$.
## Constraints

$\leq N \leq 3\times 10^5$
$S_i$ is a string consisting of lowercase English letters.
$\leq |S_i|$
$|S_1|+|S_2|+\ldots+|S_N|\leq 3\times 10^5$
All input numbers are integers.

Input

The input is given from Standard Input in the following format:

$N$
$S_1$ $\ldots$ $S_N$

Output

Print the answer.

Sample Input 1

3
ab abc arc

Sample Output 1

$f(S_1,S_2)=2$
$f(S_1,S_3)=1$
$f(S_2,S_3)=1$
Thus, the answer is $f(S_1,S_2) + f(S_1,S_3) + f(S_2,S_3) = 4$ .

Sample Input 2

11
ab bb aaa bba baba babb aaaba aabbb a a b

Sample Output 2

Solution

具体见文末视频。

Code

#include <bits/stdc++.h>
#define fi first
#define se second
#define int long long

using namespace std;

typedef pair<int, int> PII;
typedef long long LL;

const int N = 3e5 + 10;

int n;
string s[N];
int tr[N][26], idx, cnt[N * 26];
int res;

void insert(string s) {
	int p = 0;
	for (int i = 0; i < s.size(); i ++) {
		int u = s[i] - 'a';
		if (!tr[p][u]) tr[p][u] = ++ idx;
		p = tr[p][u], cnt[p] ++;
	}
}
void dfs(int u) {
	res += cnt[u] * (cnt[u] - 1) / 2;
	for (int i = 0; i < 26; i ++)
		if (tr[u][i]) {
			dfs(tr[u][i]);
		}
}

signed main() {
	cin.tie(0);
	cout.tie(0);
	ios::sync_with_stdio(0);

	cin >> n;

	for (int i = 1; i <= n; i ++)
		cin >> s[i], insert(s[i]);

	dfs(0);

	cout << res << endl;

	return 0;
}

G - Merchant Takahashi

Problem Statement

The Kingdom of AtCoder has $N$ towns: towns $1$ , $2$ , $\ldots$ , $N$ .
To move from town $i$ to town $j$ , you must pay a toll of $\times |i-j|$ yen.
Takahashi, a merchant, is considering participating in zero or more of $M$ upcoming markets.
The $i$ -th market $\leq i \leq M)$ is described by the pair of integers $T_i, P_i)$ , where the market is held in town $T_i$ and he will earn $P_i$ yen if he participates.
For all $KaTeX parse error: Expected 'EOF', got '&' at position 10: 1 \leq i &̲lt; M$ , the $i$ -th market ends before the $(i + 1)$ -th market begins.
The time it takes for him to move is negligible.
He starts with $10^{10^{100}}$ yen and is initially in town $1$ .
Determine the maximum profit he can make by optimally choosing which markets to participate in and how to move.
Formally, let $10^{10^{100}} + X$ be his final amount of money if he maximizes the amount of money he has after the $M$ markets. Find $X$ .

Constraints

$\leq N \leq 2 \times 10^5$
$\leq C \leq 10^9$
$\leq M \leq 2 \times 10^5$
$\leq T_i \leq N$ $\leq i \leq M)$
$\leq P_i \leq 10^{13}$ $\leq i \leq M)$
All input values are integers.

Input

The input is given from Standard Input in the following format:

$N$ $C$
$M$
$T_1$ $P_1$
$T_2$ $P_2$
$\vdots$
$T_M$ $P_M$

Output

Print the answer.

Sample Input 1

Sample Output 1

For example, Takahashi can increase his money by $49$ yen by acting as follows:
Move to town $5$ . His money becomes $10^{10^{100}} - 12$ yen.
Participate in the first market. His money becomes $10^{10^{100}} + 18$ yen.
Move to town $4$ . His money becomes $10^{10^{100}} + 15$ yen.
Participate in the third market. His money becomes $10^{10^{100}} + 40$ yen.
Move to town $2$ . His money becomes $10^{10^{100}} + 34$ yen.
Participate in the fourth market. His money becomes $10^{10^{100}} + 49$ yen.
It is impossible to increase his money to $10^{10^{100}} + 50$ yen or more, so print 49.

Sample Input 2

6 1000000000
4
5 30
2 10
4 25
2 15

Sample Output 2

The toll fee is so high that it is optimal for him not to move from town $1$ .

Sample Input 3

Sample Output 3

Sample Input 4

50 1000000000
15
30 60541209756
48 49238708511
1 73787345006
24 47221018887
9 20218773368
34 40025202486
14 28286410866
24 82115648680
37 62913240066
14 92020110916
24 20965327730
32 67598565422
39 79828753874
40 52778306283
40 67894622518

Sample Output 4

606214471001

Note that the output value may exceed the range of a $32$ -bit integer.

Solution

后期补一下这题目的视频

Code

#include <bits/stdc++.h>
#define fi first
#define se second
#define int long long

using namespace std;

typedef pair<int, int> PII;
typedef long long LL;

template<class Info>
struct SGT {
    #define l(p) (p << 1)
    #define r(p) (p << 1 | 1)
    int n;
    std::vector<Info> info;
    SGT() {}
    SGT(int _n, Info _v = Info()) {
        init(_n, _v);
    }
    template<class T>
    SGT(std::vector<T> _init) {
        init(_init);
    }
    void init(int _n, Info _v = Info()) {
        init(std::vector<Info>(_n, _v));
    }
    template<class T>
    void init(std::vector<T> _init) {
        n = _init.size();
        info.assign(4 << std::__lg(n), Info());
        auto build = [&](auto self, int p, int l, int r) {
            if (r - l == 1) {
                info[p] = _init[l];
                return;
            }
            int m = l + r >> 1;
            self(self, l(p), l, m);
            self(self, r(p), m, r);
            pull(p);
        };
        build(build, 1, 0, n);
    }
    void pull(int p) { // 这个就是 y 总的 pushup
        info[p] = info[l(p)] + info[r(p)];
    }
    void modify(int p, int l, int r, int x, const Info &v) {
        if (r - l == 1) {
            info[p] = v;
            return;
        }
        int m = l + r >> 1;
        if (x < m) {
            modify(l(p), l, m, x, v);
        } else {
            modify(r(p), m, r, x, v);
        }
        pull(p);
    }
    void modify(int p, const Info &v) {
        modify(1, 0, n, p, v);
    }
    Info query(int p, int l, int r, int x, int y) {
        if (l >= y or r <= x) {
            return Info();
        }
        if (l >= x and r <= y) {
            return info[p];
        }
        int m = l + r >> 1;
        return query(l(p), l, m, x, y) + query(r(p), m, r, x, y);
    }
    Info query(int l, int r) {
        return query(1, 0, n, l, r + 1);
    }
};

struct Info {
    // 定义要存的变量，比如区间和 sum 或者最大公约数 d 等等，至于下标就不用存了
    int mx;
    Info(int s = -1e18): mx(s) {}
};
Info operator+(Info a, Info b) {
    Info c;
    // 对 a（左儿子） 和 b（右儿子） 一通操作合成 c（父结点）
    c.mx = max(a.mx, b.mx);
    return c;
}

const int N = 2e5 + 10;

int n, c, m;
int a[N], b[N], f[N];

signed main() {
	cin.tie(0);
	cout.tie(0);
	ios::sync_with_stdio(0);

	cin >> n >> c >> m;
	for (int i = 1; i <= m; i ++) 
        cin >> a[i] >> b[i];

	SGT<Info> plus, sub;
	plus.init(n + 1), sub.init(n + 1);
	plus.modify(1, Info(c)), sub.modify(1, Info(-c));
	for (int i = 1; i <= m; i ++) {
		int tmp = plus.query(1, a[i]).mx - c * a[i] + b[i];
		tmp = max(tmp, sub.query(a[i] + 1, n + 1).mx + c * a[i] + b[i]);
		plus.modify(a[i], max(tmp + c * a[i], plus.query(a[i], a[i]).mx));
		sub.modify(a[i], max(tmp - c * a[i], sub.query(a[i], a[i]).mx));
		f[i] = tmp;
	}

	int res = 0;
	for (int i = 0; i <= m; i ++)
		res = max(res, f[i]);

    cout << res << endl;

	return 0;
}