第一届ACC(AcWing Cup)全国高校联赛
摘要
Title: 第一届ACC(AcWing Cup)全国高校联赛
Tag: 差分、dp、k个不相交子段的最大值
Powered by:NEFU AB-IN
第一届ACC(AcWing Cup)全国高校联赛
-
A AcWing 4376. 数圈圈
-
思路
模拟
-
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20'''
Author: NEFU AB-IN
Date: 2022-03-20 18:55:28
FilePath: \ACM\Acwing\ACC\A.PY
LastEditTime: 2022-03-20 19:17:40
'''
n = int(input())
n = hex(n)[2:]
ans1 = ['0', '4', '6', '9', 'A', 'D']
ans2 = ['8', 'B']
ans = 0
for i in str(n):
if i.upper() in ans1:
ans += 1
if i.upper() in ans2:
ans += 2
print(ans)
-
B AcWing 4377. 农田灌溉
-
思路
暴力bfs也可以，这里采用的差分，每次再求个前缀和，同时判断是否有点为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'''
Author: NEFU AB-IN
Date: 2022-03-20 18:55:41
FilePath: \ACM\Acwing\ACC\b.py
LastEditTime: 2022-03-20 20:17:56
'''
for _ in range(int(input())):
n, k = map(int, input().split())
a = list(map(int, input().split()))
t = 0
while True:
t += 1
flag = 0
b = [0] * 250
for i in range(k):
b[max(a[i] - (t - 1), 0)] += 1
b[min(a[i] + t, n + 9)] -= 1
for i in range(1, n + 1):
b[i] += b[i - 1]
if b[i] == 0:
flag = 1
if flag == 0:
break
print(t)
C AcWing 4378. 选取数对
-
题意
一个长度为 n 的整数数列 a1,a2,…,an。从中挑出k个长度为m的不相交区间，使其和最大
-
思路
-
代码
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: 2022-03-21 09:34:00
FilePath: \ACM\Acwing\ACC\c.py
LastEditTime: 2022-03-21 09:59:17
'''
N = 5010
INF = int(4e9)
s = [0] * N
dp = [[0] * N for _ in range(N)]
n, m, k = map(int, input().split())
a = list(map(int, input().split()))
a = [0, *a]
for i in range(1, n + 1):
s[i] = s[i - 1] + a[i]
for i in range(m, n + 1):
for j in range(1, k + 1):
dp[i][j] = max(dp[i - 1][j], dp[i - m][j - 1] + s[i] - s[i - m])
print(dp[n][k])
