$\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;
}
|
$\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) {
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 {
for (int j = i * 2; j <= b; j += i) {
isprime[j] = true;
}
}
}
}
printf("%d\n", ans);
return 0;
}
|
$\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;
}
|
如有疑问,可以在下方评论区留言