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
M≥2
∙
\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
1≤i≤M−1)
∙
\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
2≤N≤2×105
1
≤
A
i
≤
N
1 \le A_i \le N
1≤Ai≤N
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
2≤M
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
1≤i≤M−1 )
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
7→5→3→2→7 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
1→2 and
2
→
1
2 \rightarrow 1
2→1.
In this case,
1
→
2
→
1
1 \rightarrow 2 \rightarrow 1
1→2→1 is indeed a directed cycle.
Here is the graph corresponding to this input, where
1
↔
2
1 \leftrightarrow 2
1↔2 represents the existence of both
1
→
2
1 \rightarrow 2
1→2 and
2
→
1
2 \rightarrow 1
2→1:
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
3≤N,M≤200
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+n−1,j+n−1) is called a holeless square.
i
+
n
−
1
≤
H
i + n - 1 \leq H
i+n−1≤H.
j
+
n
−
1
≤
W
j + n - 1 \leq W
j+n−1≤W.
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
0≤k≤n−1,0≤l≤n−1, 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
1≤H,W≤3000
0
≤
N
≤
min
(
H
×
W
,
1
0
5
)
0 \leq N \leq \min(H \times W, 10^5)
0≤N≤min(H×W,105)
1
≤
a
i
≤
H
1 \leq a_i \leq H
1≤ai≤H
1
≤
b
i
≤
W
1 \leq b_i \leq W
1≤bi≤W
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题)文章来源:https://www.toymoban.com/news/detail-607321.html
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;
}
最后祝大家早日文章来源地址https://www.toymoban.com/news/detail-607321.html
到了这里,关于Atcoder Beginner Contest 311 C - E题讲解的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!