带修莫队-笔记 /「Luogu P1903」数颜色-题解

通过Luogu P1903 数颜色/维护序列这道题目来学习一下 带修莫队
顾名思义,带修莫队 不仅要支持普通莫队的查询操作,还要支持数据中途的修改

比如这道题目,需要实现以下目标

  1. 查询$[L,R]$区间内不同颜色画笔的种数
  2. 将$pos$处的画笔替换为$color$颜色

达到这个目标,可以在普通莫队的基础上加一个时间维度,实现 带修莫队

阅读全文

「Luogu P5020 P1621 P4942」小练习-题解

$\mathcal{「P5020」}$ 货币系统

表面上是数论,其实就是个__动态规划__

首先设$A = (n, a) \ \ B = (m, b)$
可以证明$B \subseteq A$
$proof:$
我们设$x\in A$且$x$不能被$A$集合内除它以外的元素组成。
然后我们假设$x \notin B$,那么就说明$B$集合中必然存在一些元素能够组成$x$。
那么这些元素至少存在一个不在集合$A$内并且不能被集合$A$里的元素组成的数(因为如果不存在的话集合$A$内的元素就可以组成$x$了),可以看到这与集合$B$的定义产生了矛盾。
综上所述,$A$集合内不能被其它数组成的数必然存在于$B$集合内
$Q.E.D$

然后动态规划
dp[i]表示$i$面值最多能被几张钱表示
则若其不能被表示dp[i] = -inf
能表示且只有它自己则dp[i] = 1
初始化dp[] = -inf; dp[0] = 0
状态转移方程为dp[j] = max(dp[j], dp[j - a[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
#include <bits/stdc++.h>
using namespace std;

int n, T, ans, a[1010], dp[30010];

int main() {
scanf("%d", &T);
while (T--) {
memset(dp, -0x3f, sizeof(dp));
memset(a, 0, sizeof(a));
ans = 0; dp[0] = 0;
scanf("%d", &n);
for (int i = 1; i <= n; ++i) {
scanf("%d", &a[i]);
}
for (int i = 1; i <= n; ++i) {
for (int j = a[i]; j <= 25010; ++j) {
dp[j] = max(dp[j], dp[j - a[i]] + 1);
}
}
for (int i = 1; i <= n; ++i) {
if (dp[a[i]] == 1) {
ans++;
}
}
printf("%d\n", ans);
}
return 0;
}
/* 862ms 944kB */

$\mathcal{「P1621」}$ 集合

使用__并查集埃氏筛法__(埃拉托斯特尼筛法)即可
具体操作是边筛边合并集合

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
#include <bits/stdc++.h>
using namespace std;

const int maxn = 100010;

int ufs[maxn], a, b, p, ans;
bool isprime[maxn];

int find(int x) {
return ufs[x] == x ? x : ufs[x] = find(ufs[x]);
}

int main() {
scanf("%d %d %d", &a, &b, &p);
ans = b - a + 1; //初始个数为区间内数的个数
for (int i = a; i <= b; ++i) { //初始化
ufs[i] = i;
}
for (int i = 2; i <= b; ++i) { //埃氏筛
if (!isprime[i]) {
if (i >= p) { //大于p才合并
for (int j = i * 2; j <= b; j += i) {
isprime[j] = true;
if (j - i >= a && find(j) != find(j - i)) { //合并
ufs[find(j)] = find(j - i);
--ans;
}
}
} else { //不大于p但要标记
for (int j = i * 2; j <= b; j += i) {
isprime[j] = true;
}
}
}
}
printf("%d\n", ans);
return 0;
}
/* 38ms 1312kB */

$\mathcal{「P4942」}$ 小凯的数字

类似于$NOIp2017\ D1T1$ 小凯的疑惑,推柿子即可

首先$l(l+1)(l+2)…(r-1)r$可以表示为$l\times 10^? + (l + 1)\times 10^? + … + r\times 10^?$
同时我们知道$10$的若干次方除以$9$的余数__恒为__$1$
所以$l(l+1)(l+2)…(r-1)r$除以$9$的余数就等于$l + (l + 1) + … + (r - 1) + r$的余数
并且$l,l+1,…,r$为等差数列,公差为$1$
运用等差数列求和公式即可求解

$a_1 = l\ d = 1$
$n = r - l + 1$
$S_n = n\times a_1 + n\times (n - 1)\times \frac{d}{2}$
所以
$$
\boxed{Ans = n\times l + n\times (n - 1) \div 2}
$$

另外要边算边取模,除以$2$要变成乘模$9$下的逆元$5$
所以公式如下
ans = (n * (l % 9) % 9 + n * (n - 1) % 9 * 5 % 9) % 9;

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <bits/stdc++.h>
using namespace std;

int T;
long long l, r, n, ans;

int main() {
scanf("%d", &T);
while (T--) {
scanf("%lld %lld", &l, &r);
n = (r - l + 1) % 9;
ans = (n * (l % 9) % 9 + n * (n - 1) % 9 * 5 % 9) % 9;
printf("%lld\n", ans);
}
return 0;
}
/* 32ms 888kB */

如有疑问,可以在下方评论区留言