您现在的位置是:首页 > 正文

AtCoder Beginner Contest 302——A-E题讲解

2024-04-01 00:10:27阅读 1

蒟蒻来讲题,还望大家喜。若哪有问题,大家尽可提!

Hello, 大家好哇!本初中生蒟蒻讲解一下AtCoder Beginner Contest 302这场比赛的A-Ex题

===========================================================================================

A - Attack

原题

Problem Statement

There is an enemy with stamina A A A. Every time you attack the enemy, its stamina reduces by B B B.
At least how many times do you need to attack the enemy to make its stamina 0 0 0 or less?

Constraints

1 ≤ A , B ≤ 1 0 18 1 \le A,B \le 10^{18} 1A,B1018
A A A and B B B are integers.

Input

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

A A A B B B

Output

Print the answer.

Sample Input 1
7 3
Sample Output 1
3

Attacking three times make the enemy’s stamina − 2 -2 2.
Attacking only twice makes the stamina 1 1 1, so you need to attack it three times.

Sample Input 2
123456789123456789 987654321
Sample Output 2
124999999
Sample Input 3
999999999999999998 2
Sample Output 3
499999999999999999

题目大意

攻击一次,A减少B,问多少次可以让A减为0或者更小


思路

太简单,不写了,直接见代码

代码

#include <iostream>

using namespace std;

int main()
{
	cin.tie(0);
	cout.tie(0);
	ios::sync_with_stdio(0);
	
	long long a, b;
	
	cin >> a >> b;
	
	cout << a / b + (a % b != 0) << endl;
	
	return 0;
}

B - Find snuke

原题

Problem Statement

There is a grid with H H H horizontal rows and W W W vertical columns. Each cell has a lowercase English letter written on it.
We denote by ( i , j ) (i, j) (i,j) the cell at the i i i-th row from the top and j j j-th column from the left.
The letters written on the grid are represented by H H H strings S 1 , S 2 , … , S H S_1,S_2,\ldots, S_H S1,S2,,SH, each of length W W W.
The j j j-th letter of S i S_i Si represents the letter written on ( i , j ) (i, j) (i,j).
There is a unique set of
contiguous cells (going vertically, horizontally, or diagonally) in the grid
with s, n, u, k, and e written on them in this order.

Find the positions of such cells and print them in the format specified in the Output section.
A tuple of five cells ( A 1 , A 2 , A 3 , A 4 , A 5 ) (A_1,A_2,A_3,A_4,A_5) (A1,A2,A3,A4,A5) is said to form
a set of contiguous cells (going vertically, horizontally, or diagonally) with s, n, u, k, and e written on them in this order
if and only if all of the following conditions are satisfied.
A 1 , A 2 , A 3 , A 4 A_1,A_2,A_3,A_4 A1,A2,A3,A4 and A 5 A_5 A5 have letters s, n, u, k, and e written on them, respectively.
For all 1 ≤ i ≤ 4 1\leq i\leq 4 1i4, cells A i A_i Ai and A i + 1 A_{i+1} Ai+1 share a corner or a side.
The centers of A 1 , A 2 , A 3 , A 4 A_1,A_2,A_3,A_4 A1,A2,A3,A4, and A 5 A_5 A5 are on a common line at regular intervals.

Constraints

5 ≤ H ≤ 100 5\leq H\leq 100 5H100
5 ≤ W ≤ 100 5\leq W\leq 100 5W100
H H H and W W W are integers.
S i S_i Si is a string of length W W W consisting of lowercase English letters.
The given grid has a unique conforming set of cells.

Input

H H H W W W
S 1 S_1 S1
S 2 S_2 S2
⋮ \vdots
S H S_H SH

Output

Print five lines in the following format.
Let ( R 1 , C 1 ) , ( R 2 , C 2 ) … , ( R 5 , C 5 ) (R_1,C_1), (R_2,C_2)\ldots,(R_5,C_5) (R1,C1),(R2,C2),(R5,C5) be the cells in the sought set with s, n, u, k, and e written on them, respectively.
The i i i-th line should contain R i R_i Ri and C i C_i Ci in this order, separated by a space.
In other words, print them in the following format:
R 1 R_1 R1 C 1 C_1 C1
R 2 R_2 R2 C 2 C_2 C2
⋮ \vdots
R 5 R_5 R5 C 5 C_5 C5

See also Sample Inputs and Outputs below.

Sample Input 1
6 6
vgxgpu
amkxks
zhkbpp
hykink
esnuke
zplvfj
Sample Output 1
5 2
5 3
5 4
5 5
5 6

Tuple ( A 1 , A 2 , A 3 , A 4 , A 5 ) = ( ( 5 , 2 ) , ( 5 , 3 ) , ( 5 , 4 ) , ( 5 , 5 ) , ( 5 , 6 ) ) (A_1,A_2,A_3,A_4,A_5)=((5,2),(5,3),(5,4),(5,5),(5,6)) (A1,A2,A3,A4,A5)=((5,2),(5,3),(5,4),(5,5),(5,6)) satisfies the conditions.

Indeed, the letters written on them are s, n, u, k, and e;

for all 1 ≤ i ≤ 4 1\leq i\leq 4 1i4, cells A i A_i Ai and A i + 1 A_{i+1} Ai+1 share a side;

and the centers of the cells are on a common line.
<img src=“https://img.atcoder.jp/abc302/f0a6b1007df7fb00caa27a5f82a3afb1.png”, width=400>

Sample Input 2
5 5
ezzzz
zkzzz
ezuzs
zzznz
zzzzs
Sample Output 2
5 5
4 4
3 3
2 2
1 1

Tuple ( A 1 , A 2 , A 3 , A 4 , A 5 ) = ( ( 5 , 5 ) , ( 4 , 4 ) , ( 3 , 3 ) , ( 2 , 2 ) , ( 1 , 1 ) ) (A_1,A_2,A_3,A_4,A_5)=((5,5),(4,4),(3,3),(2,2),(1,1)) (A1,A2,A3,A4,A5)=((5,5),(4,4),(3,3),(2,2),(1,1)) satisfies the conditions.

However, for example, ( A 1 , A 2 , A 3 , A 4 , A 5 ) = ( ( 3 , 5 ) , ( 4 , 4 ) , ( 3 , 3 ) , ( 2 , 2 ) , ( 3 , 1 ) ) (A_1,A_2,A_3,A_4,A_5)=((3,5),(4,4),(3,3),(2,2),(3,1)) (A1,A2,A3,A4,A5)=((3,5),(4,4),(3,3),(2,2),(3,1)) violates the third condition because the centers of the cells are not on a common line, although it satisfies the first and second conditions.

Sample Input 3
10 10
kseeusenuk
usesenesnn
kskekeeses
nesnusnkkn
snenuuenke
kukknkeuss
neunnennue
sknuessuku
nksneekknk
neeeuknenk
Sample Output 3
9 3
8 3
7 3
6 3
5 3

题目大意

上、下、左、右、左上、右下、左下、右上八个方向找snuke,找到后输出位置。


思路

找到’s’的位置后,八个方向遍历。

代码

#include <iostream>
#include <vector>
 
using namespace std;
 
const int N = 1e2 + 10;
 
int n, m;
char a[N][N];
string s = " snuke";
 
int main()
{
	cin.tie(0);
	cout.tie(0);
	ios::sync_with_stdio(0);
	
	cin >> n >> m;
	
	for (int i = 1; i <= n; i ++)
		for (int j = 1; j <= m; j ++)
			cin >> a[i][j];
			
	for (int i = 1; i <= n; i ++)
		for (int j = 1; j <= m; j ++)
			if (a[i][j] == 's')
				for (int dx = -1; dx <= 1; dx ++)
					for (int dy = -1; dy <= 1; dy ++)
						if (dx != 0 || dy != 0)
						{
							int flg = 1;
							vector<pair<int, int>> res;
							res.push_back({i, j});
							for (int len = 2; len <= 5; len ++)
							{
								int xx = i + dx * (len - 1), yy = j + dy * (len - 1);
								if (a[xx][yy] != s[len])
								{
									flg = 0;
									break;
								}
								res.push_back({xx, yy});
							}
							if (flg)
							{
								for (auto c : res)
									cout << c.first << " " << c.second << endl;
								return 0;
							}
						}
	
	return 0;
}

C - Almost Equal

原题

Problem Statement

You are given N N N strings S 1 , S 2 , … , S N S_1,S_2,\dots,S_N S1,S2,,SN, each of length M M M, consisting of lowercase English letter. Here, S i S_i Si are pairwise distinct.
Determine if one can rearrange these strings to obtain a new sequence of strings T 1 , T 2 , … , T N T_1,T_2,\dots,T_N T1,T2,,TN such that:
for all integers i i i such that 1 ≤ i ≤ N − 1 1 \le i \le N-1 1iN1, one can alter exactly one character of T i T_i Ti to another lowercase English letter to make it equal to T i + 1 T_{i+1} Ti+1.

Constraints

2 ≤ N ≤ 8 2 \le N \le 8 2N8
1 ≤ M ≤ 5 1 \le M \le 5 1M5
S i S_i Si is a string of length M M M consisting of lowercase English letters. ( 1 ≤ i ≤ N ) (1 \le i \le N) (1iN)
S i S_i Si are pairwise distinct.

Input

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

N N N M M M
S 1 S_1 S1
S 2 S_2 S2
⋮ \vdots
S N S_N SN

Output

Print Yes if one can obtain a conforming sequence; print No otherwise.

Sample Input 1
4 4
bbed
abcd
abed
fbed
Sample Output 1
Yes

One can rearrange them in this order: abcd, abed, bbed, fbed. This sequence satisfies the condition.

Sample Input 2
2 5
abcde
abced
Sample Output 2
No

No matter how the strings are rearranged, the condition is never satisfied.

Sample Input 3
8 4
fast
face
cast
race
fact
rice
nice
case
Sample Output 3
Yes

题目大意

给定N个字符串,通过重新排序让相邻两个字符串只有一个字母不同。


思路

题目比较简单,但一定要注意全排序函数的使用,昨晚被这个题目折腾完了。
这道题可以对所有字符串的排列就行全排序,遍历哪一个排序能够符合题目的要求,即每两个相邻字符串只有一个字母不同。
这里要特别注意,在使用next_permutation()函数前,要先进行一次sort,不然结果就会有5个测试点WA,因为next_permutation()函数是接着上次的顺序向下排的。

代码

#include <iostream>
#include <algorithm>
 
using namespace std;
 
int n, m;
string s[10];
 
int main()
{
	cin.tie(0);
	cout.tie(0);
	ios::sync_with_stdio(0);
	
	cin >> n >> m;
	
	if (m == 1)
	{
		cout << "Yes" << endl;
		return 0;
	}
	
	for (int i = 1; i <= n; i ++)
		cin >> s[i];
		
	sort(s + 1, s + n + 1));
		
	do
	{
		/*
		for(int i = 1; i <= n; i ++)
			cout << s[i] << endl;
		*/
		int flg = 1;
		for (int i = 1; i < n; i ++)
		{
			int cnt = 0;
			for (int j = 0; j < m; j ++)
				if (s[i][j] != s[i + 1][j])
					cnt ++;
					
			if (cnt != 1)
			{
				flg = 0;
				break;
			}
		}
		
		if (flg)
		{
			cout << "Yes" << endl;
			return 0;
		}
		
	}while(next_permutation(s + 1, s + n + 1));
	
	cout << "No" << endl;
	
	return 0;
}

D - Impartial Gift

原题

Problem Statement

Takahashi has decided to give one gift to Aoki and one gift to Snuke.

There are N N N candidates of gifts for Aoki,
and their values are A 1 , A 2 , … , A N A_1, A_2, \ldots,A_N A1,A2,,AN.

There are M M M candidates of gifts for Snuke,
and their values are B 1 , B 2 , … , B M B_1, B_2, \ldots,B_M B1,B2,,BM.
Takahashi wants to choose gifts so that the difference in values of the two gifts is at most D D D.
Determine if he can choose such a pair of gifts. If he can, print the maximum sum of values of the chosen gifts.

Constraints

1 ≤ N , M ≤ 2 × 1 0 5 1\leq N,M\leq 2\times 10^5 1N,M2×105
1 ≤ A i , B i ≤ 1 0 18 1\leq A_i,B_i\leq 10^{18} 1Ai,Bi1018
0 ≤ D ≤ 1 0 18 0\leq D \leq 10^{18} 0D1018
All values in the input are integers.

Input

The input is given from Standard Input in the following format:
N N N M M M D D D
A 1 A_1 A1 A 2 A_2 A2 … \ldots A N A_N AN
B 1 B_1 B1 B 2 B_2 B2 … \ldots B M B_M BM

Output

If he can choose gifts to satisfy the condition,
print the maximum sum of values of the chosen gifts.
If he cannot satisfy the condition, print − 1 -1 1.

Sample Input 1
2 3 2
3 10
2 5 15
Sample Output 1
8

The difference of values of the two gifts should be at most 2 2 2.

If he gives a gift with value 3 3 3 to Aoki and another with value 5 5 5 to Snuke, the condition is satisfied, achieving the maximum possible sum of values.

Thus, 3 + 5 = 8 3+5=8 3+5=8 should be printed.

Sample Input 2
3 3 0
1 3 3
6 2 7
Sample Output 2
-1

He cannot choose gifts to satisfy the condition.
Note that the candidates of gifts for a person may contain multiple gifts with the same value.

Sample Input 3
1 1 1000000000000000000
1000000000000000000
1000000000000000000
Sample Output 3
2000000000000000000

Note that the answer may not fit into a 32 32 32-bit integer type.

Sample Input 4
8 6 1
2 5 6 5 2 1 7 9
7 2 5 5 2 4
Sample Output 4
14

思路

这道题我们可以用二分来做,在做之前首先我们要排序两个序列!

  • 对于序列一,我们枚举每一个点,然后通过二分在序列B中找到最大的不超过当前枚举的点的权值,最后更新两个数的差。
  • 对于序列二,我们枚举每一个点,然后通过二分在序列A中找到最大的不超过当前枚举的点的权值,最后给更新两个数的差。

注意:这里只用找到不超过枚举到的点(设为x)的权值是因为,如果有比当前点权值大的点(设为y),且他们两个的差更小,那么我们在枚举序列B的时候一定会枚举到y,此时x就在y的前面,自然会更新到这个更小的值

代码

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

using namespace std;

const int N = 2e5 + 10;

int n, m, d;
int a[N], b[N];

signed main()
{
	cin.tie(0);
	cout.tie(0);
	ios::sync_with_stdio(0);
	
	cin >> n >> m >> d;
	
	for (int i = 1; i <= n; i ++)
		cin >> a[i];
	for (int i = 1; i <= m; i ++)
		cin >> b[i];
		
	sort(a + 1, a + 1 + n);
	sort(b + 1, b + 1 + m);
	
	int res = -1;
	for (int i = 1; i <= n; i ++)
	{
		int l = 0, r = m;
		while (l < r)
		{
			int mid = l + r + 1 >> 1;
			if (b[mid] <= a[i]) l = mid;
			else r = mid - 1;
		}
		
		if (b[l] == 0) continue;
		else
			if (a[i] - b[l] <= d)
				res = max(res, a[i] + b[l]);
	}
	
	for (int i = 1; i <= m; i ++)
	{
		int l = 0, r = n;
		while (l < r)
		{
			int mid = l + r + 1 >> 1;
			if (a[mid] <= b[i]) l = mid;
			else r = mid - 1;
		}
		
		if (a[l] == 0) continue;
		else
			if (b[i] - a[l] <= d)
				res = max(res, b[i] + a[l]);
	}
	
	cout << res << endl;
	
	return 0;
}

E - Isolation

原题

Problem Statement

There is an undirected graph with N N N vertices numbered 1 1 1 through N N N, and initially with 0 0 0 edges.

Given Q Q Q queries, process them in order. After processing each query,
print the number of vertices that are not connected to any other vertices by an edge.
The i i i-th query, q u e r y i \mathrm{query}_i queryi, is of one of the following two kinds.
1 u v: connect vertex u u u and vertex v v v with an edge. It is guaranteed that, when this query is given, vertex u u u and vertex v v v are not connected by an edge.
2 v: remove all edges that connect vertex v v v and the other vertices. (Vertex v v v itself is not removed.)

Constraints

2 ≤ N ≤ 3 × 1 0 5 2 \leq N\leq 3\times 10^5 2N3×105
1 ≤ Q ≤ 3 × 1 0 5 1 \leq Q\leq 3\times 10^5 1Q3×105
For each query of the first kind, 1 ≤ u , v ≤ N 1\leq u,v\leq N 1u,vN and u ≠ v u\neq v u=v.
For each query of the second kind, 1 ≤ v ≤ N 1\leq v\leq N 1vN.
Right before a query of the first kind is given, there is no edge between vertices u u u and v v v.
All values in the input are integers.

Input

The input is given from Standard Input in the following format:
N N N Q Q Q
q u e r y 1 \mathrm{query}_1 query1
q u e r y 2 \mathrm{query}_2 query2
⋮ \vdots
q u e r y Q \mathrm{query}_Q queryQ

Output

Print Q Q Q lines.

The i i i-th line ( 1 ≤ i ≤ Q ) (1\leq i\leq Q) (1iQ) should contain the number of vertices that are not connected to any other vertices by an edge.

Sample Input 1
3 7
1 1 2
1 1 3
1 2 3
2 1
1 1 2
2 2
1 1 2
Sample Output 1
1
0
0
1
0
3
1

After the first query, vertex 1 1 1 and vertex 2 2 2 are connected to each other by an edge, but vertex 3 3 3 is not connected to any other vertices.

Thus, 1 1 1 should be printed in the first line.
After the third query, all pairs of different vertices are connected by an edge.

However, the fourth query asks to remove all edges that connect vertex 1 1 1 and the other vertices, specifically to remove the edge between vertex 1 1 1 and vertex 2 2 2, and another between vertex 1 1 1 and vertex 3 3 3.
As a result, vertex 2 2 2 and vertex 3 3 3 are connected to each other, while vertex 1 1 1 is not connected to any other vertices by an edge.

Thus, 0 0 0 and 1 1 1 should be printed in the third and fourth lines, respectively.

Sample Input 2
2 1
2 1
Sample Output 2
2

When the query of the second kind is given, there may be no edge that connects that vertex and the other vertices.


思路

  • 对于操作一,我们就直接减无向边,同时如果加之前一个点或两个点都没有连边,那么就从总答案的点数减去没有连边的点数。
  • 对于操作二,我们把哪个点的所有点删掉,因为建的是无向边,我们还要把他删掉的边所对应的另一个的点与这个点相连的边也删掉,如果删掉后没有其余边了,再加1

代码

#include <iostream>
#include <set>

using namespace std;

const int N = 3e5 + 10;

int n, q;
int op, a, b;
set<int> g[N];

int main()
{
	cin.tie(0);
	cout.tie(0);
	ios::sync_with_stdio(0);
	
	cin >> n >> q;
	
	int res = n;
	while (q --)
	{
		cin >> op >> a;
		
		if (op == 1)
		{
			cin >> b;
			if (g[a].size() == 0) res --;
			if (g[b].size() == 0) res --;
			g[a].insert(b);
			g[b].insert(a);
		}
		else
		{
			for (auto c : g[a])
			{
				g[c].erase(a);
				if (g[c].size() == 0) res ++;
			}
			if (g[a].size() > 0) res ++;
			g[a].clear();
		}
		cout << res << endl;
	}
	
	return 0;
}

今天就到这里了!

大家有什么问题尽管提,我都会尽力回答的!

吾欲您伸手,点的小赞赞。吾欲您喜欢,点得小关注!

网站文章

  • C/C++语言:判断是否是素数

    判断任一个正整数n是否是素数

    2024-04-01 00:10:22
  • 使用JavaScript创建和设置HTML表格

    使用JavaScript创建和设置HTML表格

    要在JavaScript中创建和设置HTML表格,您可以使用DOM(文档对象模型)来操作HTML元素。下面是一个示例代码,演示如何使用JavaScript创建一个简单的表格并设置一些样式。您可以根据需...

    2024-04-01 00:10:16
  • 6.工厂模式_2:实现改良版本

    跟汤老师学Java笔记:工厂模式实现改良版本 完成:第一遍 1.工厂模式改良版本如何实现? package designPattern; import java.io.BufferedReader; ...

    2024-04-01 00:09:52
  • linux中通过dbca创建oracle数据库

    linux中通过dbca创建oracle数据库

    本文承接上篇博客,linux中安装oracle数据库1.首先还是一样的,本地的xstar连接上服务器,2.#非常重要,必须在oracle用户下执行这行命令,否则会导致你弹出的安装oracle界面全是框框export LANG=en_US.UTF-8#这边的ip要填你自己安装xstart自己电脑上面的ipexport DISPLAY=192.168.5.108:0.03...

    2024-04-01 00:09:40
  • L1-054 福到了 (15 分)

    “福”字倒着贴,寓意“福到”。不论到底算不算民俗,本题且请你编写程序,把各种汉字倒过来输出。这里要处理的每个汉字是由一个 N×N 的网格组成的,网格中的元素或者为字符@或者为空格。而倒过来的汉字所用的...

    2024-04-01 00:09:34
  • C#基础(三十八)详细介绍委托、回调:一个类调用另一个类的方法

    一、简介 在基于Prism的MVVM架构中,用到了Socket通信作为Server。SocketClass类定义了单例模式,然后在软件启动的时候,就加载SocketClass并一直监听Client的消息。该消息包行了不同的标志,根据标志值加载不同类的方法。也就是加载View.xaml对应的ViewModel.cs。 那么问题来了,如何加载其他类(ViewModel...

    2024-04-01 00:09:07
  • (Python)文件读取时出现编码报错(一)——已解决

    (Python)文件读取时出现编码报错(一)——已解决

    (Python)文件读取时出现编码报错——已解决

    2024-04-01 00:09:01
  • 初学者之路——————随机粗糙面建模

    蒙特卡罗法又称线性滤波法,基本思想是在频域用功率谱进行滤波,再做逆快速傅立叶变换得到粗糙面的高低起伏。 粗糙面被认为由大量谐波叠加而成,谐波的振幅是独立的高斯随机变量,方差正比于特定波数的功率谱,所以可以用函数来表示一维粗糙面。 由于合成过程的表面长度有限,表面自相关函数不会衰减到0,所以会有振荡现象。因此,在反变换过程中需要进行加窗用来避免边缘效应和谱重叠问题。 如果文章存在问题,欢迎大家指出。

    2024-04-01 00:08:56
  • Zabbix异常-页面加载不出

    Zabbix异常-页面加载不出

    Zabbix异常-页面加载不出 由于机房搬迁,重启服务器之后,想要进入原来的zabbix监控页面,发现老是加载不出来。提示: 检查端口开启状态 正常 尝试获取zabbix页面信息 获取正常 估计还是端口未开放的问题 登录服务器,查看iptables规则 问题来了,所定义的防火墙规则不应该只有这么点,而且貌似也并没有开放80端口 开放80端口 问题很明显,防火...

    2024-04-01 00:08:48
  • scrapy可视化管理工具gerapy学习笔记

    安装和使用的方法见链接https://cuiqingcai.com/4959.html 值得注意的是需要的request版本比较高,如果本机有需要用到低版本的request,最好在虚拟机中安装 总结 一个管理爬虫项目的可视化工具,把项目部署到管理的操作全部变为交互式,相当的直观和方便。但是比起spiderkeeper相比缺少了定时爬虫功能,同时对于爬虫情况的可视化也不够完善。...

    2024-04-01 00:08:23