AtCoder Regular Contest 170 （ABC题）

A - Yet Another AB Problem

Problem Statement

You are given two strings $S$ and $T$ of length $N$ consisting of A and B. Let $S_i$ denote the $i$-th character from the left of $S$.
You can repeat the following operation any number of times, possibly zero:
Choose integers $i$ and $j$ such that KaTeX parse error: Expected 'EOF', got '&' at position 9: 1\leq i &?lt; j \leq N. Replace $S_i$ with A and $S_j$ with B.
Determine if it is possible to make $S$ equal $T$. If it is possible, find the minimum number of operations required.

Constraints

$2\le N\le 2\times 10^5$
Each of $S$ and $T$ is a string of length $N$ consisting of A and B.
All input numbers are integers.

Input

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

$N$
$S$
$T$

Output

If it is impossible to make $S$ equal $T$, print -1.
Otherwise, print the minimum number of operations required to do so.

Sample Input 1

5
BAABA
AABAB

Sample Output 1

2

Performing the operation with $i=1$ and $j=3$ changes $S$ to AABBA.
Performing the operation with $i=4$ and $j=5$ changes $S$ to AABAB.
Thus, you can make $S$ equal $T$ with two operations. It can be proved that this is the minimum number of operations required, so the answer is $2$.

Sample Input 2

2
AB
BA

Sample Output 2

-1

It can be proved that no matter how many operations you perform, you cannot make $S$ equal $T$.

Solution

具体见文后视频。

---

Code

#include <bits/stdc++.h>
#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;
	string S1, S2;

	cin >> N >> S1 >> S2;

	S1 = ' ' + S1, S2 = ' ' + S2;
	std::vector<int> A, B;
	for (int i = 1; i <= N; i ++)
		if (S1[i] == 'A' && S2[i] == 'B')
			B.push_back(i);
	for (int i = 1; i <= N; i ++)
		if (S1[i] == 'B' && S2[i] == 'A')
			A.push_back(i);

	int Pair = 0;
	for (int i = 0, j = 0; i < A.size(); i ++)
	{
		while (j < B.size() && B[j] < A[i]) j ++;
		if (j < B.size() && B[j] >= A[i]) Pair ++, j ++;
	}

	bool F1 = 0, F2 = 0;
	if (A.size())
		for (int i = A.back() + 1; i <= N; i ++)
			if (S2[i] == 'B')
				F1 = 1;
	if (B.size())
		for (int i = 1; i < *(B.begin()); i ++)
			if (S2[i] == 'A')
				F2 = 1;

	if ((!F1 && A.size()) || (!F2 && B.size())) cout << -1 << endl;
	else cout << A.size() + B.size() - Pair << endl;

	return 0;
}

B - Arithmetic Progression Subsequence

Problem Statement

You are given a sequence $A$ of length $N$ consisting of integers between $1$ and $\text{10}$, inclusive.
A pair of integers $(l,r)$ satisfying $1\le l\le r\le N$ is called a good pair if it satisfies the following condition:
The sequence $(A_l,A_{l+1},\dots ,A_r)$ contains a (possibly non-contiguous) arithmetic subsequence of length $3$. More precisely, there is a triple of integers $(i,j,k)$ with KaTeX parse error: Expected 'EOF', got '&' at position 10: l \leq i &?lt; j < k\le… such that $A_j?A_i=A_k?A_j$.
Find the number of good pairs.

Constraints

$3\le N\le 10^5$
$1\le A_i\le 10$
All input numbers are integers.

Input

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

$N$
$A_1$ $\dots$ $A_N$

Output

Print the answer.

Sample Input 1

5
5 3 4 1 5

Sample Output 1

3

There are three good pairs: $(l,r)=(1,4),(1,5),(2,5)$.
For example, the sequence $(A_1,A_2,A_3,A_4)$ contains an arithmetic subsequence of length $3$, which is $(5,3,1)$, so $(1,4)$ is a good pair.

Sample Input 2

3
1 2 1

Sample Output 2

0

There may be cases where no good pairs exist.

Sample Input 3

9
10 10 1 3 3 7 2 2 5

Sample Output 3

3

Solution

具体见文后视频。

Code

#include <bits/stdc++.h>
#define lowbit(x) x & -x
#define int long long

using namespace std;

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

const int SIZE = 1e5 + 10;

int N;
int A[SIZE];
std::vector<int> P[20];
struct Fenwick
{
	int Tree[SIZE];
	Fenwick() { memset(Tree, 0, sizeof Tree); }
	void Add(int x, int d) { for (int i = x; i <= N; i += lowbit(i)) Tree[i] = max(Tree[i], d); }
	int Max(int x)
	{
		int Result = 0;
		for (int i = x; i; i -= lowbit(i))
			Result = max(Result, Tree[i]);
		return Result;
	}
}Cnt;

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], P[A[i]].push_back(i);

	int L = 0, R = N + 1, Result = 0;
	vector<PII> Seg;
	for (int i = 2; i < N; i ++)
		for (int j = -A[i] + 1; j < A[i]; j ++)
		{
			if (!P[A[i] + j].size() || !P[A[i] - j].size()) continue;
			auto it = lower_bound(P[A[i] + j].begin(), P[A[i] + j].end(), i);
			if (it == P[A[i] + j].begin()) continue;
			int Left = *( -- it);
			it = upper_bound(P[A[i] - j].begin(), P[A[i] - j].end(), i);
			if (it == P[A[i] - j].end()) continue;
			int Right = *it;
			Seg.push_back({Left, Right});
			Cnt.Add(Right, Left);
		}
	
	for (int r = 1; r <= N; r ++)
	{
		int L = Cnt.Max(r);
		Result += L;
	}

	cout << Result << endl;

	return 0;
}

C - Prefix Mex Sequence

Problem Statement

For a sequence $X$ composed of a finite number of non-negative integers, we define $\mathrm{mex}(X)$ as the smallest non-negative integer not in $X$. For example, $\mathrm{mex}((0,0,1,3))=2,\mathrm{mex}((1))=0,\mathrm{mex}(())=0$.
You are given a sequence $S=(S_1,\dots ,S_N)$ of length $N$ where each element is $0$ or $1$.
Find the number, modulo $998244353$, of sequences $A=(A_1,A_2,\dots ,A_N)$ of length $N$ consisting of integers between $0$ and $M$, inclusive, that satisfy the following condition:
For each $i(1\le i\le N)$, $A_i=\mathrm{mex}((A_1,A_2,\dots ,A_{i?1}))$ if $S_i=1$, and $A_i\ne \mathrm{mex}((A_1,A_2,\dots ,A_{i?1}))$ if $S_i=0$.

Constraints

$1\le N\le 5000$
$0\le M\le 10^9$
$S_i$ is $0$ or $1$.
All input numbers are integers.

Input

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

$N$ $M$
$S_1$ $\dots$ $S_N$

Output

Print the answer.

Sample Input 1

4 2
1 0 0 1

Sample Output 1

4

The following four sequences satisfy the conditions:
$(0,0,0,1)$
$(0,0,2,1)$
$(0,2,0,1)$
$(0,2,2,1)$

Sample Input 2

10 1000000000
0 0 1 0 0 0 1 0 1 0

Sample Output 2

587954969

Be sure to find the count modulo $998244353$.

Solution

具体见文后视频。

---

Code

#include <bits/stdc++.h>
#define int long long

using namespace std;

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

const int SIZE = 3e5 + 10;

int N;
int A[SIZE], Next[SIZE];

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

	memset(Next, -1, sizeof Next);

	cin >> N;

	for (int i = 1; i <= N; i ++)
	{
		cin >> A[i];
		if (A[i] == -1) Next[0] = i;
		else Next[A[i]] = i;
	}
	
	for (int i = 0; Next[i] != -1; i = Next[i])
		cout << Next[i] << " ";

	return 0;
}

视频题解

---

最后祝大家早日