「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)

#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」}$ 集合

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

#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;

#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 */

---

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