Acwing 第 96 场周赛
摘要
Title: Acwing 第 96 场周赛
Tag: 完全背包、多重背包、线段树
Powered by:NEFU AB-IN
Acwing 第 96 场周赛
-
A AcWing 4876. 完美数
-
题意
如果一个正整数能够被 2520整除，则称该数为完美数。
给定一个正整数 n，请你计算 [1,n]
范围内有多少个完美数。 -
思路
整除即可
-
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18# import
import sys, math
from collections import Counter, deque
from heapq import heappop, heappush
from bisect import bisect_left, bisect_right
# Final
N = int(1e3 + 10)
INF = int(2e9)
# Define
sys.setrecursionlimit(INF)
read = lambda: map(int, input().split())
# —————————————————————Division line ————————————————————————————————————————
n, = read()
print(n // 2520)
-
-
B AcWing 4877. 最大价值
-
题意
略
-
思路
简化为：
- 第一个物品是完全背包问题
- 后面的物品是多重背包问题（即有物品数量限制）
这是第一个做背包叠加态的问题，其实对dp数组可以随意叠加，相当于就是给个状态
- 比如第一个物品是完全背包问题，那么就可以给状态，比如
dp[v] = w, dp[2v] = 2w, ... - 这样下面再做多重背包的时候，就可以在这些状态的基础上进行转化，比如当体积为2v的时候，是不是就可以用到
dp[v]转移到dp[2v]，只不过以前只有多重背包的时候，dp[v]可能没遍历到（因采用的是优化空间的递推式）
-
代码
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'''
Author: NEFU AB-IN
Date: 2023-03-31 16:28:46
FilePath: \Acwing\96cp\b\b1.py
LastEditTime: 2023-03-31 21:09:10
'''
# import
import sys, math
from collections import Counter, deque
from heapq import heappop, heappush
from bisect import bisect_left, bisect_right
# Final
N = int(1e3 + 10)
INF = int(2e9)
# Define
sys.setrecursionlimit(INF)
read = lambda: map(int, input().split())
# —————————————————————Division line ————————————————————————————————————————
dp = [0] * N
n, m, v, w = read()
for j in range(v, n + 1):
dp[j] = dp[j - v] + w
for i in range(m):
l, h, v, w = read()
for j in range(n, -1, -1):
k = 0
while k <= l / h and j - k * v >= 0:
dp[j] = max(dp[j], dp[j - k * v] + k * w)
k += 1
print(dp[n])
-
-
C AcWing 4878. 维护数组
-
题意
略
-
思路
简单来说，就是线段树或者树状数组的板子题，单点更新 + 区间查询
这不过这里的线段树结点属性要开两个sum- 一个维护和a比的最小值
- 一个维护和b比的最小值
-
代码
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
97
98
99
100
101
102
103
104/*
* @Author: NEFU AB-IN
* @Date: 2023-03-31 17:24:25
* @FilePath: \Acwing\96cp\c\c.cpp
* @LastEditTime: 2023-03-31 20:24:21
*/
using namespace std;
typedef pair<int, int> PII;
const int N = 2e5 + 10, INF = 0x3f3f3f3f;
struct Tree
{
int l, r, suma, sumb;
} tr[N << 2];
int w[N], n, k, a, b, q;
void pushup(int p)
{
tr[p].suma = tr[ls].suma + tr[rs].suma;
tr[p].sumb = tr[ls].sumb + tr[rs].sumb;
}
void build(int p, int l, int r)
{
tr[p] = {l, r, 0, 0};
if (l == r)
return;
int mid = l + r >> 1;
build(ls, l, mid);
build(rs, mid + 1, r);
pushup(p);
}
void update(int p, int L, int v)
{
if (tr[p].l == L && tr[p].r == L)
{
w[L] += v;
tr[p].suma = min(w[L], a);
tr[p].sumb = min(w[L], b);
return;
}
int mid = tr[p].l + tr[p].r >> 1;
if (L <= mid)
update(ls, L, v);
if (L > mid)
update(rs, L, v);
pushup(p);
}
int query(int p, int L, int R, int flag)
{
if (tr[p].l >= L && tr[p].r <= R)
{
return !flag ? tr[p].suma : tr[p].sumb;
}
int mid = tr[p].l + tr[p].r >> 1;
int res = 0;
if (L <= mid)
res += query(ls, L, R, flag);
if (R > mid)
res += query(rs, L, R, flag);
return res;
}
signed main()
{
IOS;
cin >> n >> k >> a >> b >> q;
build(1, 1, n);
while (q--)
{
int op;
cin >> op;
if (op == 1)
{
int x, y;
cin >> x >> y;
update(1, x, y);
}
else
{
int p;
cin >> p;
cout << query(1, 1, p - 1, 1) + query(1, p + k, n, 0) << '\n';
}
}
return 0;
}
-