AtCoder Regular Contest 170 (ABC题)

发布时间:2024年01月24日

A - Yet Another AB Problem

Problem Statement

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

Constraints

2 ≤ N ≤ 2 × 1 0 5 2 \leq N \leq 2 \times 10^5 2N2×105
Each of S S S and T T T is a string of length N N N consisting of A and B.
All input numbers are integers.

Input

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

N N N
S S S
T T T

Output

If it is impossible to make S S S equal T T 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 i=1 i=1 and j = 3 j=3 j=3 changes S S S to AABBA.
Performing the operation with i = 4 i=4 i=4 and j = 5 j=5 j=5 changes S S S to AABAB.
Thus, you can make S S S equal T T T with two operations. It can be proved that this is the minimum number of operations required, so the answer is 2 2 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 S S equal T T 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 A A of length N N N consisting of integers between 1 1 1 and 10 \textbf{10} 10, inclusive.
A pair of integers ( l , r ) (l,r) (l,r) satisfying 1 ≤ l ≤ r ≤ N 1\leq l \leq r\leq N 1lrN is called a good pair if it satisfies the following condition:
The sequence ( A l , A l + 1 , … , A r ) (A_l,A_{l+1},\ldots,A_r) (Al?,Al+1?,,Ar?) contains a (possibly non-contiguous) arithmetic subsequence of length 3 3 3. More precisely, there is a triple of integers ( i , j , k ) (i,j,k) (i,j,k) with KaTeX parse error: Expected 'EOF', got '&' at position 10: l \leq i &?lt; j &lt; k\le… such that A j ? A i = A k ? A j A_j - A_i = A_k - A_j Aj??Ai?=Ak??Aj?.
Find the number of good pairs.

Constraints

3 ≤ N ≤ 1 0 5 3 \leq N \leq 10^5 3N105
1 ≤ A i ≤ 10 1\leq A_i \leq 10 1Ai?10
All input numbers are integers.

Input

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

N N N
A 1 A_1 A1? … \ldots A N A_N AN?

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 ) (l,r)=(1,4),(1,5),(2,5) (l,r)=(1,4),(1,5),(2,5).
For example, the sequence ( A 1 , A 2 , A 3 , A 4 ) (A_1,A_2,A_3,A_4) (A1?,A2?,A3?,A4?) contains an arithmetic subsequence of length 3 3 3, which is ( 5 , 3 , 1 ) (5,3,1) (5,3,1), so ( 1 , 4 ) (1,4) (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 X X composed of a finite number of non-negative integers, we define m e x ( X ) \mathrm{mex}(X) mex(X) as the smallest non-negative integer not in X X X. For example, m e x ( ( 0 , 0 , 1 , 3 ) ) = 2 , m e x ( ( 1 ) ) = 0 , m e x ( ( ) ) = 0 \mathrm{mex}((0,0, 1,3)) = 2, \mathrm{mex}((1)) = 0, \mathrm{mex}(()) = 0 mex((0,0,1,3))=2,mex((1))=0,mex(())=0.
You are given a sequence S = ( S 1 , … , S N ) S=(S_1,\ldots,S_N) S=(S1?,,SN?) of length N N N where each element is 0 0 0 or 1 1 1.
Find the number, modulo 998244353 998244353 998244353, of sequences A = ( A 1 , A 2 , … , A N ) A=(A_1,A_2,\ldots,A_N) A=(A1?,A2?,,AN?) of length N N N consisting of integers between 0 0 0 and M M M, inclusive, that satisfy the following condition:
For each i ( 1 ≤ i ≤ N ) i (1\leq i\leq N) i(1iN), A i = m e x ( ( A 1 , A 2 , … , A i ? 1 ) ) A_i = \mathrm{mex}((A_1,A_2,\ldots,A_{i-1})) Ai?=mex((A1?,A2?,,Ai?1?)) if S i = 1 S_i=1 Si?=1, and A i ≠ m e x ( ( A 1 , A 2 , … , A i ? 1 ) ) A_i \neq \mathrm{mex}((A_1,A_2,\ldots,A_{i-1})) Ai?=mex((A1?,A2?,,Ai?1?)) if S i = 0 S_i=0 Si?=0.

Constraints

1 ≤ N ≤ 5000 1 \leq N \leq 5000 1N5000
0 ≤ M ≤ 1 0 9 0 \leq M \leq 10^9 0M109
S i S_i Si? is 0 0 0 or 1 1 1.
All input numbers are integers.

Input

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

N N N M M M
S 1 S_1 S1? … \ldots S N S_N SN?

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,0,1) (0,0,0,1)
( 0 , 0 , 2 , 1 ) (0,0,2,1) (0,0,2,1)
( 0 , 2 , 0 , 1 ) (0,2,0,1) (0,2,0,1)
( 0 , 2 , 2 , 1 ) (0,2,2,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 998244353 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;
}

视频题解

Atcoder Regular Contest 170(A - C 题讲解)


最后祝大家早日在这里插入图片描述

文章来源:https://blog.csdn.net/weixin_66946161/article/details/135830436
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。