Acwing 第 88 场周赛
摘要
Title: Acwing 第 88 场周赛
Tag: dp
Powered by:NEFU AB-IN
Acwing 第 88 场周赛
-
A AcWing 4800. 下一个
-
题意
略
-
思路
枚举即可
-
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23'''
Author: NEFU AB-IN
Date: 2023-01-28 19:01:44
FilePath: \Acwing\88cp\a.py
LastEditTime: 2023-01-28 19:03:16
'''
from collections import Counter
def check(x):
d = Counter(str(x))
for key in d.keys():
if d[key] > 1:
return 0
return 1
x = int(input())
for i in range(x + 1, 100000):
if check(i):
print(i)
exit(0)
-
-
B AcWing 4801. 强连通图
-
题意
给定一个平面。平面中有 n条与 x轴平行的有向边，从上到下依次编号为 1∼n，每条边都无限长，且两两不重合。
平面中有 m条与 y轴平行的有向边，从左到右依次编号为 1∼m，每条边都无限长，且两两不重合。
这些边一共有 n×m个交点。
给定每条边的具体方向，请你判断这 n×m个交点是否满足：从任意交点出发可以到达任意其它交点。 -
思路
当时的思路是，看到数据范围比较小，就想着暴力，将这一横或竖的点都连起来，然后每个进行DFS，看是否每个都能到达所有顶点
但其实是个结论题：- 容易发现，只要角上的四个点可以互相到达，那么这个图一定满足“从任意交点出发可以到达任意其它交点”
- 因为如果四个顶点可以互相到达，那么就代表边缘上的点同样可以。而图上的任意中间点可以先顺着所处的边的方向走到边缘，然后通过边缘的四条边的直接抵达某个点，满足要求
-
代码
DFS
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/*
* @Author: NEFU AB-IN
* @Date: 2023-01-28 18:53:44
* @FilePath: \Acwing\88cp\b.cpp
* @LastEditTime: 2023-01-28 19:39:06
*/
using namespace std;
typedef pair<int, int> PII;
const int N = 1e4 + 10, INF = 0x3f3f3f3f;
vector<int> g[N];
int st[N];
int n, m, cnt;
void dfs(int u)
{
cnt++;
st[u] = 1;
for (auto v : g[u])
{
if (!st[v])
dfs(v);
}
}
signed main()
{
IOS;
cin >> n >> m;
string x, y;
cin >> x >> y;
auto f = [&](int x, int y) { return y * m + x; };
for (int j = 0; j < n; ++j)
{
if (x[j] == '>')
for (int i1 = 0, j1 = j; i1 < m - 1; ++i1)
g[f(i1, j1)].push_back(f(i1 + 1, j1));
else
for (int i1 = m - 1, j1 = j; i1 > 0; --i1)
g[f(i1, j1)].push_back(f(i1 - 1, j1));
}
for (int i = 0; i < m; ++i)
{
if (y[i] == 'v')
for (int i1 = i, j1 = 0; j1 < n - 1; ++j1)
g[f(i1, j1)].push_back(f(i1, j1 + 1));
else
for (int i1 = i, j1 = n - 1; j1 > 0; --j1)
g[f(i1, j1)].push_back(f(i1, j1 - 1));
}
for (int i = 0; i < n * m; ++i)
{
cnt = 0;
memset(st, 0, sizeof st);
dfs(i);
if (cnt != n * m)
{
cout << "NO\n";
return 0;
}
}
cout << "YES\n";
return 0;
}结论
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
using namespace std;
int n, m;
string a, b;
int main()
{
cin >> n >> m >> a >> b;
if (a[0] == '<' && a[n - 1] == '>' && b[0] == 'v' && b[m - 1] == '^')
puts("YES");
else if (a[0] == '>' && a[n - 1] == '<' && b[0] == '^' && b[m - 1] == 'v')
puts("YES");
else
puts("NO");
return 0;
}
-
-
C AcWing 4802. 金明的假期
-
题意
金明有 n天假期，编号 1∼n
整个假期期间，他每天只可能有三种选择：
去健身房健身一整天。（前提是当天健身房开放）
去图书馆看书一整天。（前提是当天图书馆开放）
在家休息一整天。
用一个长度为 n的整数数组 a1,a2,…,an来表示这 n天健身房与图书馆的开放情况，其中：
ai等于 0表示第 i天健身房关闭且图书馆关闭。
ai等于 1表示第 i天健身房关闭但图书馆开放。
ai等于 2表示第 i天健身房开放但图书馆关闭。
ai等于 3表示第 i天健身房开放且图书馆开放。
金明希望自己用来休息的天数尽可能少，但是，他一定不会连续两天（或更多天）去健身房健身，也一定不会连续两天（或更多天）去图书馆看书。
请你计算，金明用来休息的最少可能天数。 -
思路
一个简单的DP题，
dp[i][j]代表第i天干第j件事情的休息时间，一共三个事情，0、1、2分别代表休息，图书馆，健身
一共是三个转移方程其余情况，比如当这天图书馆开门了，那么当天的
dp[i][1]设为无穷大，也就是不允许这种情况出现
最后三者取最小值即可 -
代码
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/*
* @Author: NEFU AB-IN
* @Date: 2023-01-28 18:53:47
* @FilePath: \Acwing\88cp\c.cpp
* @LastEditTime: 2023-01-28 19:52:12
*/
using namespace std;
typedef pair<int, int> PII;
const int N = 1e4 + 10, INF = 0x3f3f3f3f;
int dp[N][5]; // 代表第i天干第j件事情的休息时间
int n;
signed main()
{
IOS;
cin >> n;
for (int i = 1; i <= n; ++i)
{
int x;
cin >> x;
dp[i][0] = min(dp[i - 1][2], min(dp[i - 1][0], dp[i - 1][1])) + 1;
if (x == 0)
{
dp[i][1] = dp[i][2] = INF;
}
if (x == 1 || x == 3)
dp[i][2] = min(dp[i - 1][1], dp[i - 1][0]);
else
dp[i][2] = INF;
if (x == 2 || x == 3)
dp[i][1] = min(dp[i - 1][2], dp[i - 1][0]);
else
dp[i][1] = INF;
}
cout << min(min(dp[n][0], dp[n][1]), dp[n][2]);
return 0;
}
-