Atcoder Begginer Contest 327 讲解（A~E题）-Toy模板网

这篇具有很好参考价值的文章主要介绍了Atcoder Begginer Contest 327 讲解（A~E题）。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

A - ab

Description

Problem Statement

You are given a string $S$ of length $N$ consisting of lowercase English letters.
If there are any adjacent occurrences of a and b in $S$ , print Yes; otherwise, print No. (The order of a and b does not matter.)

问题陈述

给你一个长度为 $N$ 的字符串 $S$ ，由小写英文字母组成。
如果在 $S$ 中出现相邻的a和b，打印是；否则，打印否。(a "和 "b "的顺序并不重要）。

Constraints

$\leq N \leq 100$
$S$ is a string of length $N$ consisting of lowercase English letters.

Input

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

$N$
$S$

Output

If there are any adjacent occurrences of a and b in $S$ , print Yes; otherwise, print No.

Sample Input 1

3
abc

Sample Output 1

Yes

The string abc has a as the first character and b as the second character, which are adjacent. Thus, print Yes.

Sample Input 2

2
ba

Sample Output 2

Yes

The string ba has a as the second character and b as the first character, which are adjacent. (Note that the order of a and b does not matter.)

Sample Input 3

7
atcoder

Sample Output 3

No

Solution

ABC327 A题

Code

#include <iostream>
#define int long long

using namespace std;

typedef pair<int, int> PII;

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

	int N;
	string S;

	cin >> N >> S;

	for (int i = 1; i < S.size(); i ++)
		if (S[i] == 'a' && S[i - 1] == 'b' || S[i - 1] == 'a' && S[i] == 'b')
		{
			cout << "Yes" << endl;
			return 0;
		}

	cout << "No" << endl;

	return 0;
}

B - A^A

Description

Problem Statement

You are given an integer $B$ .

If there exists a positive integer $A$ such that $A^A = B$ , print its value; otherwise, output -1.

问题陈述

给你一个整数 $B$ 。
如果存在一个正整数 $A$ ，使得 $A^A = B$ ，打印它的值，否则，输出-1。

Constraints

$\leq B \leq 10^{18}$
$B$ is an integer.

Input

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

$B$

Output

If there exists a positive integer $A$ such that $A^A = B$ , print its value; otherwise, print -1.

If there are multiple positive integers $A$ such that $A^A = B$ , any of them will be accepted.

Sample Input 1

Sample Output 1

$3^3 = 27$ , so print $3$ .

Sample Input 2

Sample Output 2

-1

There is no $A$ such that $A^A = B$ .

Sample Input 3

10000000000

Sample Output 3

Solution

ABC327 B题

Code

#include <iostream>
#define int long long

using namespace std;

typedef pair<int, int> PII;

__int128 qmi(int a, int b)
{
	__int128 Result = 1;
	while (b)
	{
		if (b & 1) Result = Result * a;
		a = a * a;
		b >>= 1;
	}

	return Result;
}

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

	int B;

	cin >> B;

	int A = 1;
	for (; qmi(A, A) <= B; A ++)
		if (qmi(A, A) == B)
		{
			cout << A << endl;
			return 0;
		}

	cout << -1 << endl;

	return 0;
}

C - Number Place

Description

Problem Statement

There is a $9\times 9$ grid $A$ , where each cell contains an integer between $1$ and $9$ , inclusive.

Specifically, the cell at the $i$ -th row from the top and $j$ -th column from the left contains $A_{i,j}$ .
If $A$ satisfies all of the following conditions, print Yes. Otherwise, print No.
For each row of $A$ , the nine cells in that row contain each integer from $1$ to $9$ exactly once.
For each column of $A$ , the nine cells in that column contain each integer from $1$ to $9$ exactly once.
Divide the rows of $A$ into three groups, each of three rows, from top to bottom, and similarly divide the columns into three groups, each of three columns, from left to right.
Each $3\times 3$ grid obtained from $A$ in this way contains each integer from $1$ to $9$ exactly once.

问题陈述

有一个 $9\times 9$ 网格 $A$ ，其中每个单元格都包含一个介于 $1$ 和 $9$ （含）之间的整数。
具体来说，从顶部起第 $i$ 行和从左侧起第 $j$ 列的单元格中包含 $A_{i,j}$ 。

如果 $A$ 满足以下所有条件，则打印 “是”。否则，打印 “否”。

对于 $A$ 的每一行，该行中的九个单元格包含了从 $1$ 到 $9$ 的每一个整数。
对于 $A$ 的每一列，该列中的九个单元格包含了从 $1$ 到 $9$ 的每一个整数。
将 $A$ 的行从上到下分成三组，每组三行，同样将列从左到右分成三组，每组三列。这样从 $A$ 得到的每个 $3\times 3$ 网格正好包含一次从 $1$ 到 $9$ 的每个整数。

Constraints

$1\leq A_{i,j}\leq 9$
All input values are integers.

Input

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

$A_{1,1}$ $A_{1,2}$ $\ldots$ $A_{1,9}$
$A_{2,1}$ $A_{2,2}$ $\ldots$ $A_{2,9}$
$\vdots$
$A_{9,1}$ $A_{9,2}$ $\ldots$ $A_{9,9}$

Output

If the grid $A$ satisfies all the conditions in the problem statement, print Yes; otherwise, print No.

Sample Input 1

1 2 3 4 5 6 7 8 9
4 5 6 7 8 9 1 2 3
7 8 9 1 2 3 4 5 6
2 3 4 5 6 7 8 9 1
5 6 7 8 9 1 2 3 4
8 9 1 2 3 4 5 6 7
3 4 5 6 7 8 9 1 2
6 7 8 9 1 2 3 4 5
9 1 2 3 4 5 6 7 8

Sample Output 1

Yes

The grid $A$ is shown below.
Atcoder Begginer Contest 327 讲解（A~E题）,Atcoder,Atcoder,c++,ABC
The grid $A$ satisfies all three conditions, so print Yes.

Sample Input 2

1 2 3 4 5 6 7 8 9
2 3 4 5 6 7 8 9 1
3 4 5 6 7 8 9 1 2
4 5 6 7 8 9 1 2 3
5 6 7 8 9 1 2 3 4
6 7 8 9 1 2 3 4 5
7 8 9 1 2 3 4 5 6
8 9 1 2 3 4 5 6 7
9 1 2 3 4 5 6 7 8

Sample Output 2

No

The grid $A$ is shown below.
Atcoder Begginer Contest 327 讲解（A~E题）,Atcoder,Atcoder,c++,ABC
For example, if you look at the top left $3\times 3$ grid, you can see that the third condition is unsatisfied, so print No.

Sample Input 3

1 2 3 4 5 6 7 8 9
4 5 6 7 8 9 1 2 3
7 8 9 1 2 3 4 5 6
1 2 3 4 5 6 7 8 9
4 5 6 7 8 9 1 2 3
7 8 9 1 2 3 4 5 6
1 2 3 4 5 6 7 8 9
4 5 6 7 8 9 1 2 3
7 8 9 1 2 3 4 5 6

Sample Output 3

No

The grid $A$ is shown below.
Atcoder Begginer Contest 327 讲解（A~E题）,Atcoder,Atcoder,c++,ABC
For example, if you look at the leftmost column, you can see that the second condition is unsatisfied, so print No.

Solution

ABC327 C题

Code

#include <iostream>
#define int long long

using namespace std;

typedef pair<int, int> PII;

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

	int A[10][10];

	for (int i = 1; i <= 9; i ++)
		for (int j = 1; j <= 9; j ++)
			cin >> A[i][j];

	for (int i = 1; i <= 9; i ++)
	{
		int Tmp = 0;
		for (int j = 1; j <= 9; j ++)
			Tmp |= (1 << A[i][j] - 1);
		if (Tmp != 511)
		{
			cout << "No" << endl;
			return 0;
		}
	}

	for (int i = 1; i <= 9; i ++)
	{
		int Tmp = 0;
		for (int j = 1; j <= 9; j ++)
			Tmp |= (1 << A[j][i] - 1);
		if (Tmp != 511)
		{
			cout << "No" << endl;
			return 0;
		}
	}

	for (int i = 1; i <= 9; i += 3)
		for (int j = 1; j <= 9; j += 3)
		{
			int Tmp = 0;
			for (int x = i; x <= i + 2; x ++)
				for (int y = j; y <= j + 2; y ++)
					Tmp |= (1 << A[x][y] - 1);
			if (Tmp != 511)
			{
				cout << "No" << endl;
				return 0;
			}
		}

	cout << "Yes" << endl;

	return 0;
}

D - Good Tuple Problem

Description

Problem Statement

A pair of sequences of length $M$ consisting of positive integers at most $N$ , $((S_1, S_2, \dots, S_M), (T_1, T_2, \dots, T_M))$ , is said to be a good pair of sequences when $(S, T)$ satisfies the following condition.
There exists a sequence $(X_1, X_2, \dots, X_N)$ of length $N$ consisting of $0$ and $1$ that satisfies the following condition:
$X_{S_i} \neq X_{T_i}$ for each $\dots, M$ .
You are given a pair of sequences of length $M$ consisting of positive integers at most $N$ : $((A_1, A_2, \dots, A_M), (B_1, B_2, \dots, B_M))$ . If $(A, B)$ is a good pair of sequences, print Yes; otherwise, print No.

Constraints

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

Input

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

$N$ $M$
$A_1$ $A_2$ $\dots$ $A_M$
$B_1$ $B_2$ $\dots$ $B_M$

Output

If $(A, B)$ is a good pair of sequences, print Yes; otherwise, print No.

Sample Input 1

3 2
1 2
2 3

Sample Output 1

Yes

If we set $X = (0, 1, 0)$ , then $X$ is a sequence of length $N$ consisting of $0$ and $1$ that satisfies $X_{A_1} \neq X_{B_1}$ and $X_{A_2} \neq X_{B_2}$ .

Thus, $(A, B)$ satisfies the condition of being a good pair of sequences.

Sample Input 2

3 3
1 2 3
2 3 1

Sample Output 2

No

No sequence $X$ satisfies the condition, so $(A, B)$ is not a good pair of sequences.

Sample Input 3

10 1
1
1

Sample Output 3

No

Sample Input 4

7 8
1 6 2 7 5 4 2 2
3 2 7 2 1 2 3 3

Sample Output 4

Yes

Solution

ABC327 D题

Code

#include <iostream>
#include <vector>
#include <map>
#define int long long

using namespace std;

typedef pair<int, int> PII;

const int SIZE = 2e5 + 10;

int N, M;
int A[SIZE], B[SIZE];
vector<int> G[SIZE];
int Color[SIZE];

bool DFS(int u, int color)
{
    Color[u] = color;
    
    for (auto c : G[u])
    {
        if (!Color[c])
            if (!DFS(c, 3 - color))
                return false;
        if (Color[c] == color)
            return false;
    }
    
    return true;
}

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

	cin >> N >> M;

	for (int i = 1; i <= M; i ++)
		cin >> A[i];
	for (int i = 1; i <= M; i ++)
		cin >> B[i];

	for (int i = 1; i <= M; i ++)
		if (A[i] == B[i])
		{
			cout << "No" << endl;
			return 0;
		}
		else
			G[A[i]].push_back(B[i]), G[B[i]].push_back(A[i]);

	// for (auto c : Edge)
	// 	cout << c.first << " " << c.second << endl;

	bool Flag = 1;
    for (int i = 1; i <= N; i ++)
        if (!Color[i])
            if (!DFS(i, 1))
            {
                cout << "No" << endl;
                return 0;
            }

    cout << "Yes" << endl;

	return 0;
}

E - Maximize Rating

Description

Problem Statement

Takahashi participated in $N$ contests and earned a performance $P_i$ in the $i$ -th contest.

He wants to choose some (at least one) contests from these and maximize his rating calculated from the results of those contests.
Find the maximum possible rating he can achieve by optimally choosing the contests.
Here, Takahashi’s rating $R$ is calculated as the following, where $k$ is the number of chosen contests and $(Q_1, Q_2, \ldots, Q_k)$ are the performances in the chosen contests in the order he participated:

$\displaystyle R=\frac{\sum_{i=1}^k (0.9)^{k-i}Q_i}{\sum_{i=1}^k (0.9)^{k-i}}-\frac{1200}{\sqrt{k}}.$

问题陈述

高桥参加了 $N$ 次比赛，并在 $i$ 次比赛中获得了 $P_i$ 的成绩。
他想从中选择一些（至少一个）比赛，并最大限度地提高根据这些比赛结果计算出的评分。

求通过优化选择比赛他能获得的最高评分。

这里，高桥的评分 $R$ 计算如下，其中 $k$ 是所选比赛的数量， $(Q_1, Q_2, \ldots, Q_k)$ 是所选比赛的成绩，按他参加比赛的顺序：

$\displaystyle R=\frac{\sum_{i=1}^k (0.9)^{k-i}Q_i}{\sum_{i=1}^k (0.9)^{k-i}}-\frac{1200}{\sqrt{k}}.$

Constraints

$1\leq N\leq 5000$
$1\leq P_i\leq 5000$
All input values are integers.

Input

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

$N$
$P_1$ $P_2$ $\ldots$ $P_N$

Output

Print the maximum possible rating that Takahashi can achieve.

Your output will be considered correct if the absolute or relative error from the true value is at most $10^{-6}$ .

Sample Input 1

3
1000 600 1200

Sample Output 1

256.735020470879931

If Takahashi chooses the first and third contests, his rating will be:
$\displaystyle R=\frac{0.9\times 1000+ 1.0\times 1200}{0.9+1.0}-\frac{1200}{\sqrt{2}}=256.73502...$ .
This is the maximum possible rating.

Sample Input 2

3
600 1000 1200

Sample Output 2

261.423219407873376

The rating is maximized when all the first, second, and third contests are selected.

Sample Input 3

1
100

Sample Output 3

-1100.000000000000000

The rating can also be negative.

Solution

ABC327 E题

Code

#include <iostream>
#include <cmath>
#include <cstring>
#include <ctime>

using namespace std;

typedef pair<int, int> PII;

const int SIZE = 1e4 + 10;

int N;
int P[SIZE];
double F[SIZE][SIZE], Max[SIZE][SIZE], Pow[SIZE];

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

	cin >> N;

	Pow[0] = 1.0;
	for (int i = 1; i <= N; i ++)
		Pow[i] = Pow[i - 1] * 0.9;

	for (int i = 1; i <= N; i ++)
		cin >> P[i];

	for (int i = 1; i <= N; i ++)
		for (int j = 1; j <= N; j ++)
			F[i][j] = Max[i][j] = 0.0;
	for (int i = 1; i <= N; i ++)
		for (int j = 1; j <= i; j ++)
		{
			F[i][j] = max(F[i][j], F[i - 1][j]);
			F[i][j] = max(F[i][j], Max[i - 1][j - 1] * 0.9 + P[i]);
			Max[i][j] = max(Max[i - 1][j], F[i][j]);
		}

	double Answer = -1e18;
	for (int k = 1; k <= N; k ++)
	{
		double Result = -1e18;
		for (int i = 1; i <= N; i ++)
			Result = max(Result, F[i][k]);
		double Tmp = 0;
		for (int i = 1; i <= k; i ++)
			Tmp += Pow[k - i];
		Result /= Tmp;
		Result -= (1200.0 / sqrt(k * 1.0));
		Answer = max(Answer, Result);
	}

	printf("%.6lf\n", Answer);

	return 0;
}

F - Apples

Description

Problem Statement

There are apple trees lined up on a number line, and $N$ apples fall from the trees.

Specifically, for each $1\leq i\leq N$ , an apple falls at coordinate $X_i$ at time $T_i$ .
Takahashi has a basket with durability $D$ and length $W$ , and he can take the following action exactly once.

Choose positive integers $S$ and $L$ . He sets up the basket to cover the range $L-0.5\leq x\leq L+W-0.5$ at time $S - 0.5$ , and retrieves it at time $S + D - 0.5$ .
He gets all the apples that fell into the range covered by the basket between the time it was set up and the time it was retrieved.

He cannot move the basket once it has been set up, nor can he set it up again once it has been retrieved.

Find the maximum number of apples that he can get.

Constraints

$\leq N\leq 2\times 10^5$
$\leq D\leq 2\times 10^5$
$\leq W\leq 2\times 10^5$
$\leq T_i\leq 2\times 10^5$
$\leq X_i\leq 2\times 10^5$
All pairs $T_i,X_i)$ are different.
All input values are integers.

Input

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

$N$ $D$ $W$
$T_1$ $X_1$
$T_2$ $X_2$
$\vdots$
$T_N$ $X_N$

Output

Print the maximum number of apples that Takahashi can get.

Sample Input 1

Sample Output 1

If Takahashi chooses $S = 3$ and $L = 2$ , he will set up the basket to cover the range $1.5\leq x\leq 4.5$ from time $2.5$ to $6.5$ . Then, he gets the following five apples:
The apple that falls at coordinate $X_2=4$ at time $T_2=3$
The apple that falls at coordinate $X_3=4$ at time $T_3=6$
The apple that falls at coordinate $X_4=2$ at time $T_4=5$
The apple that falls at coordinate $X_5=2$ at time $T_5=4$
The apple that falls at coordinate $X_6=3$ at time $T_6=4$
There is no way to get six or more apples, so print $5$ .

问题陈述

有几棵苹果树排在一条数线上， $N$ 个苹果从树上掉下来。
具体地说，每一个 $1\leq i\leq N$ 都有一个苹果在时间 $T_i$ 落在坐标 $X_i$ 处。

高桥有一个耐久度为 $D$ 、长度为 $W$ 的篮子，他可以做以下动作次。

选择正整数 $S$ 和 $L$ 。他在 $S - 0.5$ 时将篮子放置在 $L-0.5\leq x\leq L+W-0.5$ 范围内，在 $S + D - 0.5$ 时将其取回。他可以得到从放置篮子到取回篮子这段时间内掉落在篮子覆盖范围内的所有苹果。

篮子放好后，他不能移动篮子，篮子取回后，他也不能再放篮子。
求他能得到的苹果的最大数量。

Solution

ABC327 F题

Code

#include <iostream>
#include <algorithm>
#define int long long

using namespace std;

typedef pair<int, int> PII;

const int SIZE = 2e5 + 10;

int N, D, W;
PII P[SIZE];
struct Segment
{
	int l, r;
	int Max, Lazy;
}Tree[SIZE * 4];

void Pushup(int u)
{
	Tree[u].Max = max(Tree[u << 1].Max, Tree[u << 1 | 1].Max);
}

void Pushdown(int u)
{
	if (Tree[u].Lazy)
	{
		Tree[u << 1].Max += Tree[u].Lazy;
		Tree[u << 1 | 1].Max += Tree[u].Lazy;
		Tree[u << 1].Lazy += Tree[u].Lazy;
		Tree[u << 1 | 1].Lazy += Tree[u].Lazy;
		Tree[u].Lazy = 0;
	}
}

void Build(int u, int l, int r)
{
	Tree[u] = {l, r};
	if (l == r) return;

	int mid = l + r >> 1;
	Build(u << 1, l, mid), Build(u << 1 | 1, mid + 1, r);
}

void Modify(int u, int l, int r, int d)
{
	if (Tree[u].l >= l && Tree[u].r <= r)
	{
		Tree[u].Max += d;
		Tree[u].Lazy += d;
		return;
	}

	Pushdown(u);
	int mid = Tree[u].l + Tree[u].r >> 1;
	if (mid >= l) Modify(u << 1, l, r, d);
	if (mid < r) Modify(u << 1 | 1, l, r, d);
	Pushup(u);
}

int Query(int u, int l, int r)
{
	if (Tree[u].l >= l && Tree[u].r <= r)
		return Tree[u].Max;

	Pushdown(u);
	int mid = Tree[u].l + Tree[u].r >> 1, Result = 0;
	if (mid >= l) Result = Query(u << 1, l, r);
	if (mid < r) Result = max(Result, Query(u << 1 | 1, l, r));

	return Result;
}

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

	cin >> N >> D >> W;

	int Time = 0, Pos = 0;
	for (int i = 1; i <= N; i ++)
		cin >> P[i].first >> P[i].second, Time = max(Time, P[i].first), Pos = max(Pos, P[i].second);

	sort(P + 1, P + 1 + N);

	Build(1, 1, Time);

	int j = 1;
	for (int i = 1; i <= D; i ++)
		while (P[j].first == i && j <= N)
		{
			Modify(1, max(1ll, P[j].second - W + 1), P[j].second, 1);
			j ++;
		}

	int j2 = 1, Result = Query(1, 1, Pos);
	for (int i = D + 1; i <= Time; i ++)
	{
		while (P[j2].first == i - D && j2 <= N)
		{
			Modify(1, max(1ll, P[j2].second - W + 1), P[j2].second, -1);
			j2 ++;
		}
		while (P[j].first == i && j <= N)
		{
			Modify(1, max(1ll, P[j].second - W + 1), P[j].second, 1);
			j ++;
		}
		Result = max(Result, Query(1, 1, Pos));
	}

	cout << Result << endl;

	return 0;
}