AtCoder Beginner Contest 322 (A~F题)

A - First ABC 2

Description

Problem Statement

You are given a string $S$ of length $N$ consisting of A, B, and C.

Find the position where ABC first appears as a (contiguous) substring in $S$ . In other words, find the smallest integer $n$ that satisfies all of the following conditions.
$\leq n \leq N - 2$ .
The string obtained by extracting the $n$ -th through $(n + 2)$ -th characters of $S$ is ABC.
If ABC does not appear in $S$ , print -1.

Constraints

$\leq N \leq 100$
$S$ is a string of length $N$ consisting of A, B, and C.

Input

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

$N$
$S$

Output

Print the position where ABC first appears as a substring in $S$ , or -1 if it does not appear in $S$ .

Sample Input 1

8
ABABCABC
1
2

Sample Output 1

3
1

ABC first appears in $S$ at the $3$ -rd through $5$ -th characters of $S$ . Therefore, the answer is $3$ .

Sample Input 2

3
ACB
1
2

Sample Output 2

-1
1

If ABC does not appear in $S$ , print $- 1$ .

Sample Input 3

20
BBAAABBACAACABCBABAB
1
2

Sample Output 3

13
1

Solution

对于每一个起始位置，进行判断是否能构成 ABC 即可。

Code

#include 
#define int long long

using namespace std;

signed main()
{
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(0);
    
    int N;
    string s;
    
    cin >> N >> s;
    
    for (int i = 0; i < s.size(); i ++)
    	if (s[i] == 'A' && s[i + 1] == 'B' && s[i + 2] == 'C')
    	{
    		cout << i + 1 << endl;
    		return 0;
		}
		
	cout << -1 << endl;

	return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

B - Prefix and Suffix

Description

Problem Statement

You are given two strings $S$ and $T$ consisting of lowercase English letters. The lengths of $S$ and $T$ are $N$ and $M$ , respectively. (The constraints guarantee that $\leq M$ .)
$S$ is said to be a prefix of $T$ when the first $N$ characters of $T$ coincide $S$ .

$S$ is said to be a suffix of $T$ when the last $N$ characters of $T$ coincide $S$ .
If $S$ is both a prefix and a suffix of $T$ , print $0$ ;

If $S$ is a prefix of $T$ but not a suffix, print $1$ ;

If $S$ is a suffix of $T$ but not a prefix, print $2$ ;

If $S$ is neither a prefix nor a suffix of $T$ , print $3$ .

Constraints

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

Input

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

$N$ $M$
$S$
$T$

Output

Print the answer according to the instructions in the problem statement.

Sample Input 1

3 7
abc
abcdefg
1
2
3

Sample Output 1

1
1

$S$ is a prefix of $T$ but not a suffix, so you should print $1$ .

Sample Input 2

3 4
abc
aabc
1
2
3

Sample Output 2

2
1

$S$ is a suffix of $T$ but not a prefix.

Sample Input 3

3 3
abc
xyz
1
2
3

Sample Output 3

3
1

$S$ is neither a prefix nor a suffix of $T$ .

Sample Input 4

3 3
aaa
aaa
1
2
3

Sample Output 4

0
1

$S$ and $T$ may coincide, in which case $S$ is both a prefix and a suffix of $T$ .

Solution

通过枚举判断是否是前缀或后缀即可，最后按照要求输出。

Code

#include 
#define int long long

using namespace std;

signed main()
{
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(0);
    
    int N, M; 
    string s, t;
    
    cin >> N >> M;
    cin >> s >> t;
    
    bool flg1 = 1;
    for (int i = 0; i < N; i ++)
    	if (s[i] != t[i])
    	{
    		flg1 = 0;
    		break;
		}
	bool flg2 = 1;
	for (int i = N - 1; i >= 0; i --)
    	if (s[i] != t[M - N + i])
    	{
    		flg2 = 0;
    		break;
		}
		
	if (flg1 && flg2) cout << 0 << endl;
	else if (flg1) cout << 1 << endl;
	else if (flg2) cout << 2 << endl;
	else cout << 3 << endl;

	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

C - Festival

Description

Problem Statement

The AtCoder Kingdom holds a festival for $N$ days. On $M$ of these days, namely on the $A_1$ -th, $A_2$ -th, $\dots$ , $A_M$ -th days, fireworks will be launched. It is guaranteed that fireworks will be launched on the last day of the festival. (In other words, $A_M=N$ is guaranteed.)
For each $i=1,2,\dots,N$ , solve the following problem.
How many days later from the $i$ -th day will fireworks be launched for the first time on or after the $i$ -th day? If fireworks are launched on the $i$ -th day, it is considered to be $0$ days later.

Constraints

$\le M \le N \le 2 \times 10^5$
$\le A_1 \le A_2 \le \dots \le A_M = 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$

Output

Print $N$ lines.
The $i$ -th line $\le i \le N)$ should contain an integer representing the number of days from the $i$ -th day until fireworks are launched for the first time on or after the $i$ -th day.

Sample Input 1

Sample Output 1

The kingdom holds a festival for $3$ days, and fireworks are launched on the $2$ -nd and $3$ -rd days.
From the $1$ -st day, the first time fireworks are launched is the $2$ -nd day of the festival, which is $1$ day later.
From the $2$ -nd day, the first time fireworks are launched is the $2$ -nd day of the festival, which is $0$ days later.
From the $3$ -rd day, the first time fireworks are launched is the $3$ -rd day of the festival, which is $0$ days later.

Sample Input 2

Sample Output 2

Solution

本蒟蒻直接 无脑双指针，貌似可能不需要。
对于每一个 $i$ ，找出比他大的最小的数，然后输出差值即可。（lowerbound也是可以的）

Code

#include 
#define int long long

using namespace std;

const int SIZE = 2e5 + 10;

int N, M;
int A[SIZE]; 

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];
		
	int j = 1;
	for (int i = 1; i <= N; i ++)
	{
		while (j < M && A[j] < i) j ++;
		cout << A[j] - i << endl;
	}

	return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

D - Polyomino

纯模拟，跑路了……

E - Product Development

Description

Problem Statement

AtCoder Inc. is planning to develop a product. The product has $K$ parameters, whose values are currently all zero. The company aims to raise all parameter values to at least $P$ .
There are $N$ development plans. Executing the $i$ -th development plan ( $\le i \le N$ ) increases the value of the $j$ -th parameter by $A_{i,j}$ for every integer $j$ such that $\le j \le K$ , at the cost of $C_i$ .
A development plan cannot be executed more than once. Determine whether the company can achieve its goal, and if it can, find the minimum total cost required to achieve the goal.

Constraints

$\le N \le 100$
$\le K,P \le 5$
$\le A_{i,j} \le P(1 \le i \le N,1 \le j \le K)$
$\le C_i \le 10^9(1 \le i \le N)$
All input values are integers.

Input

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

$N$ $K$ $P$
$C_1$ $A_{1,1}$ $A_{1,2}$ $\dots$ $A_{1,K}$
$C_2$ $A_{2,1}$ $A_{2,2}$ $\dots$ $A_{2,K}$
$\dots$
$C_N$ $A_{N,1}$ $A_{N,2}$ $\dots$ $A_{N,K}$

Output

If AtCoder Inc. can achieve its goal, print the minimum total cost required to achieve the goal; otherwise, print -1.

Sample Input 1

Sample Output 1

9
1

If you execute the first, third, and fourth development plans, each parameter will be $3 + 2 + 0 = 5, 0 + 4 + 1 = 5, 2 + 0 + 4 = 6$ , all of which are at least $5$ , so the goal is achieved. The total cost in this case is $5 + 3 + 1 = 9$ .
It is impossible to achieve the goal at a total cost of $8$ or less. Thus, the answer is $9$ .

Sample Input 2

Sample Output 2

-1
1

You cannot achieve the goal no matter what you do. Thus, print -1.

Solution

一道动态规划 Dynamic Programming题目。
这里讲一下考场上的奇葩作法：

眺望到 $A_{i,j}\le P\le5$ ，突发奇想，设 $F_{i,a,b,c,d,e}$ 分别代表第 $i$ 个产品的参数值
想到可以如下转移： $F_{i,\min(P,a+A_{i,1}),\min(P,b+A_{i,2}),\min(P,c+A_{i,3}),\min(P,d+A_{i,4}),\min(P,e+A_{i,5})}=\min(本身,F_{j,a,b,c,d,e})$ ，就是说选了第 $i$ 个产品，那么对于每一个参数就会增长这些值，而状态 $i$ ，可以由状态 $j$ 转移而来（ $j < i$ ），注意不是 $i - 1$ ，如果写为 $i - 1$ 会漏掉许多状态。
最后是输出，这里诞生了奇葩的想法，由于 $K = 1$ 的时候有一个参数， $K = 2$ 的时候有两个参数， $\dots$ 那么，我们可以分别处理： $K = 1$ 时，是 $max_{i=1}^N(F_{i,P,0,0,0,0})$ ，因为后面不需考虑所以用 $0$ 就行； $K = 2$ 时，是 $max_{i=1}^N(F_{i,P,P,0,0,0})$ ，以此类推 $\dots$
注意：一定要取 $\max$ ，要不会吃好几发 $\colorbox{orange}{\color{white}{WA}}$ ！直接掉大分（哭

Code

#include 
#define int long long

using namespace std;

int N, K, P;
int A[101][6], C[101];
int F[101][6][6][6][6][6];

signed main()
{
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(0);
    
    cin >> N >> K >> P;
    
	for (int i = 1; i <= N; i ++)
	{
		cin >> C[i];
		for (int j = 1; j <= K; j ++)
			cin >> A[i][j];
	}
	
	memset(F, 0x3f, sizeof F);
	for (int i = 0; i <= N; i ++)
		F[i][0][0][0][0][0] = 0;
	for (int i = 1; i <= N; i ++)
		for (int j = 0; j < i; j ++)
			for (int a = 0; a <= P; a ++)
				for (int b = 0; b <= P; b ++)
					for (int c = 0; c <= P; c ++)
						for (int d = 0; d <= P; d ++)
							for (int e = 0; e <= P; e ++)
							{
								int &Tmp = F[i][min(P, a + A[i][1])][min(P, b + A[i][2])][min(P, c + A[i][3])][min(P, d + A[i][4])][min(P, e + A[i][5])];
								Tmp = min(Tmp, F[j][a][b][c][d][e] + C[i]);
							}
						
	if (K == 1)
	{
		int T = F[N][P][0][0][0][0];
		for (int i = 1; i <= N; i ++)
			T = min(T, F[i][P][0][0][0][0]);
		if (T > 1e16) cout << -1 << endl;
		else cout << T << endl;
	}
	if (K == 2)
	{
		int T = F[N][P][P][0][0][0];
		for (int i = 1; i <= N; i ++)
			T = min(T, F[i][P][P][0][0][0]);
		if (T > 1e16) cout << -1 << endl;
		else cout << T << endl;
	}
	if (K == 3)
	{
		int T = F[N][P][P][P][0][0];
		for (int i = 1; i <= N; i ++)
			T = min(T, F[i][P][P][P][0][0]);
		if (T > 1e16) cout << -1 << endl;
		else cout << T << endl;
	}
	if (K == 4)
	{
		int T = F[N][P][P][P][P][0];
		for (int i = 1; i <= N; i ++)
			T = min(T, F[i][P][P][P][P][0]);
		if (T > 1e16) cout << -1 << endl;
		else cout << T << endl;
	}
	if (K == 5)
	{
		int T = F[N][P][P][P][P][P];
		for (int i = 1; i <= N; i ++)
			T = min(T, F[i][P][P][P][P][P]);
		if (T > 1e16) cout << -1 << endl;
		else cout << T << endl;
	}

	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82

F - Vacation Query

Description

Problem Statement

You are given a string $S$ of length $N$ consisting of 0 and 1. Let $S_i$ denote the $i$ -th character of $S$ .
Process $Q$ queries in the order they are given.

Each query is represented by a tuple of three integers $(c, L, R)$ , where $c$ represents the type of the query.
When $c = 1$ : For each integer $i$ such that $\leq i \leq R$ , if $S_i$ is 1, change it to 0; if it is 0, change it to 1.
When $c = 2$ : Let $T$ be the string obtained by extracting the $L$ -th through $R$ -th characters of $S$ . Print the maximum number of consecutive 1s in $T$ .

Constraints

$\leq N \leq 5 \times 10^5$
$\leq Q \leq 10^5$
$S$ is a string of length $N$ consisting of 0 and 1.
$\in \lbrace 1, 2 \rbrace$
$\leq L \leq R \leq N$
$N$ , $Q$ , $c$ , $L$ , and $R$ are all integers.

Input

The input is given from Standard Input in the following format, where $\mathrm{query}_i$ represents the $i$ -th query:

$N$ $Q$
$S$
$\mathrm{query}_1$
$\mathrm{query}_2$
$\vdots$
$\mathrm{query}_Q$

Each query is given in the following format:

$c$ $L$ $R$

Output

Let $k$ be the number of queries with $c = 2$ . Print $k$ lines.

The $i$ -th line should contain the answer to the $i$ -th query with $c = 2$ .

Sample Input 1

Sample Output 1

The queries are processed as follows.
Initially, $S =$ 1101110.
For the first query, $T =$ 1101110. The longest sequence of consecutive 1s in $T$ is 111 from the $4$ -th character to $6$ -th character, so the answer is $3$ .
For the second query, $T =$ 101. The longest sequence of consecutive 1s in $T$ is 1 at the $1$ -st or $3$ -rd character, so the answer is $1$ .
For the third query, the operation changes $S$ to 1110000.
For the fourth query, $T =$ 00. $T$ does not contain 1, so the answer is $0$ .
For the fifth query, the operation changes $S$ to 1111111.
For the sixth query, $T =$ 1111111. The longest sequence of consecutive 1s in $T$ is 1111111 from the $1$ -st to $7$ -th characters, so the answer is $7$ .

Solution

貌似是 线段树 经典题，场上没搞出来，（后悔

这题无疑两个操作：

区间翻转
最长连续 $1$ 的个数

考虑线段树内存储哪些信息，建议先做一下：P4513 小白逛公园和 P6492 [COCI2010-2011#6] STEP

做完这两道题，相信大家就知道答案了：

左右端点( $l, r$ )
从左边开始连续 $1$ 的个数( $L_1$ )，右边开始连续 $1$ 的个数( $R_1$ )
这段区间的最长连续 $1$ 的个数( $Len_1$ )。

$\mathrm{Pushup}$ 操作：

处理左边连续 $1$ 的个数：如果左子树全是 $1$ ，那么就是 $左子树大小+右子树L_1$ ，反之就是 $左子树L_1$
处理右边连续 $1$ 的个数：与上面类似
处理最长连续 $1$ 的个数： $max(\max(左子树Len_1,右子树Len_1),左子树R_1+右子树L_1)$ ，第二种情况是左右拼接到一起。

这样，只是求出了最长连续 $1$ 的个数，还不支持翻转：
考虑如何处理翻转，我们会发现其实就是最长连续的 $1$ ，变成了最长连续的 $0$ 。所以我们线段数还要处理最长连续的 $0$ ，这样我们再仿照上面的操作进行一遍就可以切掉这道题了。

时间有限，写的可能简略，如有不懂一定要问我呦！

Code(细节较多，写起来要注意)

#include 
#define int long long

using namespace std;

const int SIZE = 5e5 + 10;

int N, Q;
int A[SIZE];
struct Segment
{
	int l, r;
	int L0, L1, R0, R1;
	int Len0, Len1;
	int Swap;
}Tree[SIZE * 4];

void Pushup(int u)
{
	if (Tree[u << 1].r - Tree[u << 1].l + 1 == Tree[u << 1].Len0)
		Tree[u].L0 = Tree[u << 1].Len0 + Tree[u << 1 | 1].L0;
	else
		Tree[u].L0 = Tree[u << 1].L0;
	if (Tree[u << 1 | 1].r - Tree[u << 1 | 1].l + 1 == Tree[u << 1 | 1].Len0)
		Tree[u].R0 = Tree[u << 1 | 1].Len0 + Tree[u << 1].R0;
	else
		Tree[u].R0 = Tree[u << 1 | 1].R0;
	
	if (Tree[u << 1].r - Tree[u << 1].l + 1 == Tree[u << 1].Len1)
		Tree[u].L1 = Tree[u << 1].Len1 + Tree[u << 1 | 1].L1;
	else
		Tree[u].L1 = Tree[u << 1].L1;
	if (Tree[u << 1 | 1].r - Tree[u << 1 | 1].l + 1 == Tree[u << 1 | 1].Len1)
		Tree[u].R1 = Tree[u << 1 | 1].Len1 + Tree[u << 1].R1;
	else
		Tree[u].R1 = Tree[u << 1 | 1].R1;
	
	Tree[u].Len0 = max(max(Tree[u << 1].Len0, Tree[u << 1 | 1].Len0), Tree[u << 1].R0 + Tree[u << 1 | 1].L0);
	Tree[u].Len1 = max(max(Tree[u << 1].Len1, Tree[u << 1 | 1].Len1), Tree[u << 1].R1 + Tree[u << 1 | 1].L1);
}

void Pushdown(int u)
{
	if (Tree[u].Swap != 0)
	{
		swap(Tree[u << 1].L0, Tree[u << 1].L1), swap(Tree[u << 1].R0, Tree[u << 1].R1);
		swap(Tree[u << 1].Len0, Tree[u << 1].Len1);
		Tree[u << 1].Swap ^= 1;//这里要注意如果本来要翻转，就不要再进行翻转了。
		swap(Tree[u << 1 | 1].L0, Tree[u << 1 | 1].L1), swap(Tree[u << 1 | 1].R0, Tree[u << 1 | 1].R1);
		swap(Tree[u << 1 | 1].Len0, Tree[u << 1 | 1].Len1);
		Tree[u << 1 | 1].Swap ^= 1;//这里要注意如果本来要翻转，就不要再进行翻转了。
		Tree[u].Swap = 0;
	}
}

void Build(int u, int l, int r)
{
	if (l == r)
	{
		Tree[u] = {l, l, !A[l], A[l], !A[l], A[l], !A[l], A[l]};
		return;
	}
	
	Tree[u] = {l, r};
	int mid = l + r >> 1;
	Build(u << 1, l, mid), Build(u << 1 | 1, mid + 1, r);
	Pushup(u);
}

void Modify(int u, int l, int r)
{
	if (Tree[u].l >= l && Tree[u].r <= r)
	{
		swap(Tree[u].L0, Tree[u].L1), swap(Tree[u].R0, Tree[u].R1);
		swap(Tree[u].Len0, Tree[u].Len1);
		Tree[u].Swap ^= 1; //这里要注意如果本来要翻转，就不要再进行翻转了。
		return;
	}
	
	Pushdown(u);
	int mid = Tree[u].l + Tree[u].r >> 1;
	if (mid >= l) Modify(u << 1, l, r);
	if (mid < r) Modify(u << 1 | 1, l, r);
	Pushup(u);
}

Segment Query(int u, int l, int r)
{
	if (Tree[u].l >= l && Tree[u].r <= r)
		return Tree[u];
	
	Pushdown(u);
	int mid = Tree[u].l + Tree[u].r >> 1;
	if (mid >= l && mid < r)
	{
		Segment Left = Query(u << 1, l, r), Right = Query(u << 1 | 1, l, r);
		Pushup(u);
		Segment Tmp;
		Tmp.l = Left.l, Tmp.r = Right.r;
		if (Left.L1 == Left.r - Left.l + 1)
			Tmp.L1 = Left.L1 + Right.L1;
		Tmp.L1 = max(Tmp.L1, Left.L1);
		
		if (Right.r - Right.l + 1 == Right.Len1)
			Tmp.R1 = Right.Len1 + Left.R1;
		Tmp.R1 = max(Tmp.R1, Right.R1);
		
		Tmp.Len1 = max(max(Left.Len1, Right.Len1), Left.R1 + Right.L1);
		
		return Tmp;
	}
	else if (mid >= l)
		return Query(u << 1, l, r);
	else
		return Query(u << 1 | 1, l, r);
}

signed main()
{
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(0);
    
    cin >> N >> Q;
    
    char x;
    for (int i = 1; i <= N; i ++)
    	cin >> x, A[i] = x & 1;
    	
    Build(1, 1, N);
    	
    while (Q --)
    {
    	int op, l, r;
    	cin >> op >> l >> r;
    	
    	if (op == 1)
    		Modify(1, l, r);
    	else
    		cout << Query(1, l, r).Len1 << endl;
	}

	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144

未简化代码，大家见谅~~~

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

相关阅读:
mac中安装Homebrew
菜狗杯Misc一层一层一层地剥开我的♥wp
黑白二维码不好看，那么快学习改色的方法吧
前端知识以及组件学习总结
线程五大状态，以及线程方法
Jupyter运行显存爆炸，明明上一个单元格已经运行完毕为什么还是会炸？
c++11 智能指针（std::shared_ptr）（六）
在访问一个网页时弹出的浏览器窗口,如何用selenium 网页自动化解决？
系列文章｜云原生时代下微服务架构进阶之路 - Spring Boot
网络聊天室(三)

原文地址：https://blog.csdn.net/weixin_66946161/article/details/133457896