Acwing 第 89 场周赛
摘要
Title: Acwing 第 89 场周赛
Tag: dp
Powered by:NEFU AB-IN
Acwing 第 89 场周赛
-
A AcWing 4803. 满足的数
-
题意
略
-
思路
模拟即可
-
代码
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/*
* @Author: NEFU AB-IN
* @Date: 2023-02-04 18:58:52
* @FilePath: \Acwing\89cp\a\a.cpp
* @LastEditTime: 2023-02-04 19:02:10
*/
using namespace std;
typedef pair<int, int> PII;
const int N = 1e5 + 10, INF = 0x3f3f3f3f;
signed main()
{
IOS;
int n;
cin >> n;
vector<int> a(n);
int sum = 0;
for (int i = 0; i < n; ++i)
cin >> a[i], sum += a[i];
int cnt = 0;
for (int i = 1; i <= 5; ++i)
{
if ((sum + i) % (n + 1) != 1)
cnt++;
}
cout << cnt;
return 0;
}
-
-
B AcWing 4804. 构造矩阵
-
题意
略
-
思路
首先遍历所有的0，在0的行和列打上标记，也就是这些点必须是0了
然后再遍历1，如果这一行或列，有一个未遍历过的或者等于1的点，那么这个点就可以覆盖为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
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/*
* @Author: NEFU AB-IN
* @Date: 2023-02-04 18:58:52
* @FilePath: \Acwing\89cp\b\b.cpp
* @LastEditTime: 2023-02-04 19:16:48
*/
using namespace std;
typedef pair<int, int> PII;
const int N = 110, INF = 0x3f3f3f3f;
int b[N][N], a[N][N];
signed main()
{
IOS;
int m, n;
cin >> m >> n;
for (int i = 1; i <= m; ++i)
{
for (int j = 1; j <= n; ++j)
{
cin >> b[i][j];
a[i][j] = -1;
}
}
for (int i = 1; i <= m; ++i)
{
for (int j = 1; j <= n; ++j)
{
if (b[i][j] == 0)
{
for (int x = 1; x <= m; ++x)
{
a[x][j] = 0;
}
for (int y = 1; y <= n; ++y)
{
a[i][y] = 0;
}
}
}
}
for (int i = 1; i <= m; ++i)
{
for (int j = 1; j <= n; ++j)
{
if (b[i][j] == 1)
{
int cnt = 0;
for (int x = 1; x <= m; ++x)
{
if (a[x][j] == -1 || a[x][j] == 1)
cnt++;
if (a[x][j] == -1)
a[x][j] = 1;
}
for (int y = 1; y <= n; ++y)
{
if (a[i][y] == -1 || a[i][y] == 1)
cnt++;
if (a[i][y] == -1)
a[i][y] = 1;
}
if (cnt == 0)
{
cout << "NO\n";
return 0;
}
}
}
}
cout << "YES\n";
for (int i = 1; i <= m; ++i)
{
for (int j = 1; j <= n; ++j)
{
cout << a[i][j] << " ";
}
cout << '\n';
}
return 0;
}
-
-
C AcWing 4805. 加减乘
-
题意
规定两种数字操作：
加减操作，将数字加 1或减 1，代价为 x。
乘法操作，将数字乘 2，代价为 y。
每种操作的使用次数不限。
请你计算，通过上述操作，将 0 变为 n，所需花费的最小代价。 -
思路
题目稍微变一下（意义不变），即将n变为0的最小代价
若是最优解，则满足下面两个性质：
- 加减操作不能相连
- 加减抵消没有必要
- 不能出现连续加操作
附图如下
所以情况就可以全部列出了，
dp[i]表示将i变成0的最小代价：- 若i为奇数：
意义为：如果i后面跟加法操作，即加1，那么再后面跟的，就只能是除操作，因为两个性质的同时约束
意义为：如果i后面跟减法操作，那么就变成了偶数，由于减这个操作不受性质的约束，所以后面的操作可以归为偶数的情况- i后面不能跟除操作，因为i为奇数
- 若i为偶数
- i后面不能跟加法操作，因为i会变奇数，而若变为奇数，且前一个操作为加法，根据性质和奇数的情况，没有符合的路，故不行
四种情况取最小值即可
- 加减操作不能相连
-
代码
比赛时写的，思路不够清晰
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/*
* @Author: NEFU AB-IN
* @Date: 2023-02-04 18:58:52
* @FilePath: \Acwing\89cp\c\c.cpp
* @LastEditTime: 2023-02-04 19:32:40
*/
using namespace std;
typedef pair<int, int> PII;
const int N = 1e7 + 10, INF = 0x3f3f3f3f;
int dp[N];
signed main()
{
IOS;
int n, x, y;
cin >> n >> x >> y;
for (int i = 1; i <= n; ++i)
{
// dp[i] = min(dp[i - 1] + x, dp[i + 1] + x, dp[i / 2] + y);
dp[i] = dp[i - 1] + x;
if (i % 2 == 0)
dp[i] = min(dp[i], dp[i / 2] + y);
dp[i + 1] = dp[i] + x;
if ((i + 1) % 2 == 0)
dp[i + 1] = min(dp[i + 1], dp[(i + 1) / 2] + y);
dp[i] = min(dp[i], dp[i + 1] + x);
}
cout << dp[n];
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
using namespace std;
typedef pair<int, int> PII;
const int N = 2e7 + 10, INF = 0x3f3f3f3f;
int dp[N];
signed main()
{
IOS;
int n, x, y;
cin >> n >> x >> y;
memset(dp, 0x3f, sizeof dp);
dp[0] = 0;
for (int i = 1; i <= n; ++i)
{
if (i & 1)
dp[i] = min(dp[(i + 1) / 2] + x + y, dp[i - 1] + x);
else
dp[i] = min(dp[i / 2] + y, dp[i - 1] + x);
}
cout << dp[n];
return 0;
}
-
