Atcoder Beginner Contest 311 C - E题讲解

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

C - Find it!

1. Description

Problem Statement

There is a directed graph with N N N vertices and N N N edges.

The i i i-th edge goes from vertex i i i to vertex A i A_i Ai. (The constraints guarantee that i ≠ A i i \neq A_i i=Ai.)

Find a directed cycle without the same vertex appearing multiple times.

It can be shown that a solution exists under the constraints of this problem.

Notes

The sequence of vertices B = ( B 1 , B 2 , … , B M B_1, B_2, \dots, B_M B1,B2,,BM) is called a directed cycle when all of the following conditions are satisfied:
∙ \bullet M ≥ 2 M \geq 2 M2
∙ \bullet The edge from vertex B i B_i Bi to vertex B i + 1 B_{i+1} Bi+1 exists. ( 1 ≤ i ≤ M − 1 1 \leq i \leq M-1 1iM1)
∙ \bullet The edge from vertex B M B_M BM to vertex B 1 B_1 B1 exists.
∙ \bullet If i ≠ j i \neq j i=j , then B i ≠ B j B_i \neq B_j Bi=Bj .

Constraints

All input values are integers.
2 ≤ N ≤ 2 × 1 0 5 2 \le N \le 2 \times 10^5 2N2×105
1 ≤ A i ≤ N 1 \le A_i \le N 1AiN
A i ≠ i A_i \neq i Ai=i

Input

The input is given from Standard Input in the following format:
N N N
A 1 A_1 A1 A 2 A_2 A2 … \dots A N A_N AN

Output

Print a solution in the following format:
M M M
B 1 B_1 B1 B 2 B_2 B2 … \dots B M B_M BM

M M M is the number of vertices, and B i B_i Bi is the i i i-th vertex in the directed cycle.
The following conditions must be satisfied:
2 ≤ M 2 \le M 2M
B i + 1 = A B i B_{i+1} = A_{B_i} Bi+1=ABi ( 1 ≤ i ≤ M − 1 1 \le i \le M-1 1iM1 )
B 1 = A B M B_{1} = A_{B_M} B1=ABM
B i ≠ B j B_i \neq B_j Bi=Bj ( i ≠ j i \neq j i=j )

If multiple solutions exist, any of them will be accepted.

Sample Input 1

7
6 7 2 1 3 4 5

Sample Output 1

4
7 5 3 2

7 → 5 → 3 → 2 → 7 7 \rightarrow 5 \rightarrow 3 \rightarrow 2 \rightarrow 7 75327 is indeed a directed cycle.
Here is the graph corresponding to this input:

Here are other acceptable outputs:
4
2 7 5 3

3
4 1 6

Note that the graph may not be connected.

Sample Input 2

2
2 1

Sample Output 2

2
1 2
This case contains both of the edges 1 → 2 1 \rightarrow 2 12 and 2 → 1 2 \rightarrow 1 21.
In this case, 1 → 2 → 1 1 \rightarrow 2 \rightarrow 1 121 is indeed a directed cycle.
Here is the graph corresponding to this input, where 1 ↔ 2 1 \leftrightarrow 2 12 represents the existence of both 1 → 2 1 \rightarrow 2 12 and 2 → 1 2 \rightarrow 1 21:

Sample Input 3

8
3 7 4 7 3 3 8 2

Sample Output 3

3
2 7 8
Here is the graph corresponding to this input:

2. Solution

Atcoder Begginer Contest 311(C题)

3. Code

#include <iostream>
#include <vector>
#include <cstring>
#include <unordered_map>

using namespace std;

const int N = 2e5 + 10;

int n;
int a[N];
int h[N], e[N], idx, ne[N], st[N];
vector<int> pass;
int res;
unordered_map<int, int> pos;
int b[N];
bool flg;

void add(int a, int b)
{
	e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}
void dfs(int u)
{
	if (st[u] || flg) return;
	st[u] = 1;
	
	for (int i = h[u]; ~i; i = ne[i])
	{
		if (st[e[i]] == 1)
		{
			res = e[i];
			flg = 1;
			return;
		}
		else if (st[e[i]] != 2)
		{
			pass.push_back(e[i]);
			dfs(e[i]);
			if (flg) return;
			pass.pop_back();
		}
	}
	
	st[u] = 2;
}

int main()
{
	cin >> n;
	
	for (int i = 1; i <= n; i ++)
		cin >> a[i], add(i, a[i]), pos[a[i]] = i;
		
	for (int i = 1; i <= n; i ++)
		if (!flg)
			dfs(i);
		
	b[1] = res;
	int k = n;
	for (int i = 1; i <= n; i ++)
	{
		b[i + 1] = a[b[i]];
		if (b[i + 1] == b[1])
		{
			k = i;
			break;
		}
	}	
	
	cout << k << endl;
	for (int i = 1; i <= k; i ++)
		cout << b[i] << " ";

	return 0;
}


D - Grid Ice Floor

1. Description

Problem Statement

There is an N × M N \times M N×M grid and a player standing on it.

Let ( i , j ) (i,j) (i,j) denote the square at the i i i-th row from the top and j j j-th column from the left of this grid.

Each square of this grid is ice or rock, which is represented by N N N strings S 1 , S 2 , … , S N S_1,S_2,\dots,S_N S1,S2,,SN of length M M M as follows:
if the j j j-th character of S i S_i Si is ., square ( i , j ) (i,j) (i,j) is ice;
if the j j j-th character of S i S_i Si is #, square ( i , j ) (i,j) (i,j) is rock.
The outer periphery of this grid (all squares in the 1 1 1-st row, N N N-th row, 1 1 1-st column, M M M-th column) is rock.
Initially, the player rests on the square ( 2 , 2 ) (2,2) (2,2), which is ice.

The player can make the following move zero or more times.
First, specify the direction of movement: up, down, left, or right.
Then, keep moving in that direction until the player bumps against a rock. Formally, keep doing the following:
if the next square in the direction of movement is ice, go to that square and keep moving;
if the next square in the direction of movement is rock, stay in the current square and stop moving.
Find the number of ice squares the player can touch (pass or rest on).

Constraints

3 ≤ N , M ≤ 200 3 \le N,M \le 200 3N,M200
S i S_i Si is a string of length M M M consisting of # and ..
Square ( i , j ) (i, j) (i,j) is rock if i = 1 i=1 i=1, i = N i=N i=N, j = 1 j=1 j=1, or j = M j=M j=M.
Square ( 2 , 2 ) (2,2) (2,2) is ice.

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 the answer as an integer.

Sample Input 1

6 6
######
#....#
#.#..#
#..#.#
#....#
######

Sample Output 1

12

For instance, the player can rest on ( 5 , 5 ) (5,5) (5,5) by moving as follows:
( 2 , 2 ) → ( 5 , 2 ) → ( 5 , 5 ) (2,2) \rightarrow (5,2) \rightarrow (5,5) (2,2)(5,2)(5,5).
The player can pass ( 2 , 4 ) (2,4) (2,4) by moving as follows:
( 2 , 2 ) → ( 2 , 5 ) (2,2) \rightarrow (2,5) (2,2)(2,5), passing ( 2 , 4 ) (2,4) (2,4) in the process.
The player cannot pass or rest on ( 3 , 4 ) (3,4) (3,4).

Sample Input 2

21 25
#########################
#..............###...####
#..............#..#...###
#........###...#...#...##
#........#..#..#........#
#...##...#..#..#...#....#
#..#..#..###...#..#.....#
#..#..#..#..#..###......#
#..####..#..#...........#
#..#..#..###............#
#..#..#.................#
#........##.............#
#.......#..#............#
#..........#....#.......#
#........###...##....#..#
#..........#..#.#...##..#
#.......#..#....#..#.#..#
##.......##.....#....#..#
###.............#....#..#
####.................#..#
#########################

Sample Output 2

215

2. Solution

Atcoder Begginer Contest 311(D题)

3. Code

#include <bits/stdc++.h>
#define x first
#define y second
#define int long long

using namespace std;

const int N = 2e2 + 10;
typedef pair<int, int> PII;

int h, w;
char s[N][N];
bool st[N][N], vis[N][N];
int dx[4] = {0, 1, 0, -1}, dy[4] = {1, 0, -1, 0};

void bfs(int sx, int sy)
{
	queue<PII> q;
	
	q.push({sx, sy});
	
	while (q.size())
	{
		auto t = q.front();
		q.pop();
		
		for (int i = 0; i < 4 ;i ++)
		{
			int xx = t.x, yy = t.y;
			while (s[xx][yy] == '.')
				st[xx][yy] = 1, xx += dx[i], yy += dy[i];
			xx -= dx[i], yy -= dy[i];
			
			if (!vis[xx][yy])
				vis[xx][yy] = 1, q.push({xx, yy});
		}
	}
}

signed main()
{
	cin >> h >> w;
	
	for (int i = 1; i <= h; i ++)
		for (int j = 1; j <= w; j ++)
			cin >> s[i][j];
			
	bfs(2, 2);
	
	int res = 0;
	for (int i = 1; i <= h; i ++)
		for (int j = 1; j <= w; j ++)
			res += st[i][j];
			
	cout << res << endl;
			
	return 0;
}

E - Defect-free Squares

1. Description

Problem Statement

There is a grid with H H H rows and W W W columns. Let ( i , j ) (i, j) (i,j) denote the square at the i i i-th row from the top and j j j-th column from the left of the grid.

Each square of the grid is holed or not. There are exactly N N N holed squares: ( a 1 , b 1 ) , ( a 2 , b 2 ) , … , ( a N , b N ) (a_1, b_1), (a_2, b_2), \dots, (a_N, b_N) (a1,b1),(a2,b2),,(aN,bN).
When the triple of positive integers ( i , j , n ) (i, j, n) (i,j,n) satisfies the following condition, the square region whose top-left corner is ( i , j ) (i, j) (i,j) and whose bottom-right corner is ( i + n − 1 , j + n − 1 ) (i + n - 1, j + n - 1) (i+n1,j+n1) is called a holeless square.
i + n − 1 ≤ H i + n - 1 \leq H i+n1H.
j + n − 1 ≤ W j + n - 1 \leq W j+n1W.
For every pair of non-negative integers ( k , l ) (k, l) (k,l) such that 0 ≤ k ≤ n − 1 , 0 ≤ l ≤ n − 1 0 \leq k \leq n - 1, 0 \leq l \leq n - 1 0kn1,0ln1, square ( i + k , j + l ) (i + k, j + l) (i+k,j+l) is not holed.
How many holeless squares are in the grid?

Constraints

1 ≤ H , W ≤ 3000 1 \leq H, W \leq 3000 1H,W3000
0 ≤ N ≤ min ⁡ ( H × W , 1 0 5 ) 0 \leq N \leq \min(H \times W, 10^5) 0Nmin(H×W,105)
1 ≤ a i ≤ H 1 \leq a_i \leq H 1aiH
1 ≤ b i ≤ W 1 \leq b_i \leq W 1biW
All ( a i , b i ) (a_i, b_i) (ai,bi) are pairwise different.
All input values are integers.

Input

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

H H H W W W N N N
a 1 a_1 a1 b 1 b_1 b1
a 2 a_2 a2 b 2 b_2 b2
⋮ \vdots
a N a_N aN b N b_N bN

Output

Print the number of holeless squares.

Sample Input 1

2 3 1
2 3

Sample Output 1

6

There are six holeless squares, listed below. For the first five, n = 1 n = 1 n=1, and the top-left and bottom-right corners are the same square.
The square region whose top-left and bottom-right corners are ( 1 , 1 ) (1, 1) (1,1).
The square region whose top-left and bottom-right corners are ( 1 , 2 ) (1, 2) (1,2).
The square region whose top-left and bottom-right corners are ( 1 , 3 ) (1, 3) (1,3).
The square region whose top-left and bottom-right corners are ( 2 , 1 ) (2, 1) (2,1).
The square region whose top-left and bottom-right corners are ( 2 , 2 ) (2, 2) (2,2).
The square region whose top-left corner is ( 1 , 1 ) (1, 1) (1,1) and whose bottom-right corner is ( 2 , 2 ) (2, 2) (2,2).

Sample Input 2

3 2 6
1 1
1 2
2 1
2 2
3 1
3 2

Sample Output 2

0

There may be no holeless square.

Sample Input 3

1 1 0

Sample Output 3

1

The whole grid may be a holeless square.

Sample Input 4

3000 3000 0

Sample Output 4

9004500500

2. Solution

此题可以用两个思路来做,一是二分+前缀和,二是dp,具体见视频。

Atcoder Begginer Contest 311(E题)

3. Code

思路1:(二分+前缀和)

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

using namespace std;

const int N = 3e3 + 10;

int h, w, k;
int a, b;
bool mp[N][N];
int sum[N][N];

bool check(int a, int b, int c)
{
	int tmp = sum[a + c - 1][b + c - 1] - sum[a + c - 1][b - 1] - sum[a - 1][b + c - 1] + sum[a - 1][b - 1];
	return (tmp == 0);
}

signed main()
{
	cin >> h >> w >> k;
	
	for (int i = 1; i <= k; i ++)
		cin >> a >> b, mp[a][b] = 1;
		
	for (int i = 1; i <= h; i ++)
		for (int j = 1; j <= w; j ++)
			sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + mp[i][j];
			
	int res = 0;
	for (int i = 1; i <= h; i ++)
		for (int j = 1; j <= w; j ++)
		{
			int l = 0, r = min(h - i + 1, w - j + 1);
			while (l < r)
			{
				int mid = l + r + 1 >> 1;
				if (check(i, j, mid)) l = mid;
				else r = mid - 1;
			}
			
			res += l;
		}
		
	cout << res << endl;
	
	return 0;
}

思路2:(Dp)

#include <iostream>
#define int long long

using namespace std;

const int N = 3e3 + 10;

int n, m, k;
int a, b;
int mp[N][N], dp[N][N];

signed main()
{
	cin >> n >> m >> k;
	
	for (int i = 1; i <= k; i ++)
			cin >> a >> b, mp[a][b] = 1;
			
	int res =0 ;
	for (int i = 1; i <= n; i ++)
		for (int j = 1; j <= m; j ++)
		{
			dp[i][j] = min(dp[i - 1][j], min(dp[i][j - 1], dp[i - 1][j - 1])) + 1;
			if (mp[i][j])
				dp[i][j] = 0;
			res += dp[i][j];
		}
		
	cout << res << endl;
	
	return 0;
}

最后祝大家早日Atcoder Beginner Contest 311 C - E题讲解,Atcoder,算法-DP,c++,算法文章来源地址https://www.toymoban.com/news/detail-607321.html

到了这里,关于Atcoder Beginner Contest 311 C - E题讲解的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • Atcoder Beginner Contest 321 G - Electric Circuit 题解 - 状压dp | 指定最低位

    为了更好的阅读体验,请点击这里 题目链接:G - Electric Circuit 看到了 (N) 的数据范围,因此是显然的状压 dp。 不妨设 (f_S) 为仅使用 (S) 集合中的所有点,能够连成恰好 (1) 个连通块的方案数。 (g_S) 为仅使用 (S) 集合中的所有点的方案数,其中 (cntr(S)) 在 (S) 中为

    2024年02月05日
    浏览(54)
  • AtCoder Beginner Contest 350 (ABCDEF题)视频讲解

    You are given a string S S S of length 6 6 6 . It is guaranteed that the first three characters of S S S are ABC and the last three characters are digits. Determine if S S S is the abbreviation of a contest held and concluded on AtCoder before the start of this contest. Here, a string T T T is “the abbreviation of a contest held and concluded on AtCoder be

    2024年04月25日
    浏览(31)
  • AtCoder Beginner Contest 297——A-E题讲解

    蒟蒻来讲题,还望大家喜。若哪有问题,大家尽可提! Hello, 大家好哇!本 初中生蒟蒻 讲解一下 AtCoder Beginner Contest 297 这场比赛的 A-E题 ! 今晚比前面几场要简单点,但我在B题翻了下车,第一次提交竟然WA了,做题要仔细啊。 开心的是,今晚终于进到绿名了! ===============

    2024年02月03日
    浏览(39)
  • Atcoder Beginner Contest 304——A-D题讲解

    蒟蒻来讲题,还望大家喜。若哪有问题,大家尽可提! Hello, 大家好哇!本 初中生蒟蒻 讲解一下 AtCoder Beginner Contest 304 这场比赛的 A-D题 ! =========================================================================================== 题目描述 Problem Statement There are N N N people numbered 1 , 2 , … , N 1, 2,

    2024年02月08日
    浏览(41)
  • AtCoder Beginner Contest 317(A~E题)讲解

    Problem Statement Naohiro has a monster. The monster’s current health is H H H . He also has N N N kinds of potions, numbered from 1 1 1 to N N N in ascending order of effectiveness. If you give the monster potion n n n , its health will increase by P n P_n P n ​ . Here, P 1 P 2 ⋯ P N P_1 lt P_2 lt dots lt P_N P 1 ​ P 2 ​ ⋯ P N ​ . He wants

    2024年02月11日
    浏览(28)
  • AtCoder Beginner Contest 314(A~D题 + G题)讲解

    Problem Statement The number pi to the 100 100 100 -th decimal place is 3.1415926535897932384626433832795028841971693993751058209749445923078164062862089986280348253421170679 . You are given an integer N N N between 1 1 1 and 100 100 100 , inclusive. Print the value of pi to the N N N -th decimal place. More precisely, truncate the value of pi to N N N decim

    2024年02月13日
    浏览(30)
  • AtCoder Beginner Contest 310

    感觉F又双叒叕写复杂了 点杯咖啡,要 (p) 元,但可以用一个优惠券,使得咖啡只要 (q) 元,但你需要额外购买 (n) 个商品中(价格为 (a_i) )的一个。 问点杯咖啡的最小价格。 考虑直接买还是使用优惠券,使用优惠券的话就选 (n) 个商品中价格最小的。 两种情况取最小

    2024年02月16日
    浏览(28)
  • AtCoder Beginner Contest 320

    给定 (a,b) ,输出 (a^b + b^a) 。 因为数不超过 (10) ,可以直接用 pow 计算然后转成 (int) 。不会有精度损失。 神奇的代码 给定一个字符串 (s) ,求长度最长的回文串。 因为长度只有 (100) ,可以直接枚举子串,然后暴力判断是不是回文串(翻转后是否和自身相同),复杂

    2024年02月08日
    浏览(38)
  • AtCoder Beginner Contest 348

    给定 (n) ,输出 (ooxooxoox...) ,长度为 (n) 。 按题意模拟即可。 神奇的代码 给定 (n) 个点,对每个点,求出与其距离最远的点的下标。 (n) 只有 (100) ,对于每个点,花 (O(n)) 遍历每个点最大化距离,时间复杂度为 (O(n^2)) 。 神奇的代码 (n) 个豌豆,每个豌豆有美味值

    2024年04月08日
    浏览(42)
  • AtCoder Beginner Contest 302

    给定怪物的血量 (a) 和你每次攻击扣除的血量 (b) ,问打多少次怪物才会死。 答案即为 (lceil frac{a}{b} rceil = lfloor frac{a + b - 1}{b} rfloor) 神奇的代码 给定一个二维网格,格子上有字母,找到一连串位置,使得其字符串为 (snuke) ,要求这一连串位置俩俩相邻,即有共边或

    2024年02月05日
    浏览(78)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包