N0lP 2018 货币系统
同步：buringstraw.win/archives/59/
N0lP 2018 货币系统
划水一周就写了个这玩意儿？
题目
货币种数为 \(n\)、面额数组为 \(a[1..n]\)的货币系统记作 \((n,a)\)。
两个货币系统$ (n,a)$ 和$ (m,b)\(是等价的，当且仅当对于任意非负整数\)x$，它要么均可以被两个货币系统表出，要么不能被其中任何一个表出。
找到一个货币系统 \((m,b)\)，满足 \((m,b)\)与原来的货币系统 \((n,a)\)等价，且 \(m\)尽可能的小。
输出最小的\(m\)
解法
如果一个货币系统里的某些货币能被另一些货币表示，那么就可以踢掉。
所以，先排序，然后对每一个a[i]，把它标记为可以被表示，
再利用完全背包的思想来筛（把能被填满的货币标记）
Code
#include <cstdio>
#include <algorithm>
using std::max;
using std::sort;
const int MAXN = 105, MAXA = 25000;
int main (void) {
int T;
scanf("%d", &T);
while (T--) {
int a[MAXN] = {0};
bool v[MAXA] = {0};
int n, maxa = 0, ans = 0;
scanf("%d", &n);
for (int i = 1; i <= n; ++i) {
scanf("%d", a + i);
maxa = max(maxa, a[i]);
}
sort(a + 1, a + 1 + n);
for (int i = 1; i <= n; ++i) {
if (v[a[i]]) continue;
++ans;
v[a[i]] = 1;
for (int j = a[i]; j <= maxa; ++j) {
if (v[j - a[i]]) v[j] = 1;
}
}
printf("%d\n", ans);
}
return 0;
}1、AES/DES加密工具类
2、[LUOGU] P1048 采药
3、如何使用 Visual C# 2005 或 Visual C# .NET 向 Excel 工作簿传输数据
4、Java基础——ArrayList与LinkedList（一）
5、JS 中 call 和 apply 的理解和使用