Day1

2. 货币系统

25pts

部分分类型:特判

剩余分错因:算法错误

根据数据满足的条件特判。

60pts

部分分类型:错误的结论

剩余分错因:算法错误

考场上想到的做法,不过因为读不懂NOI Linux上浮点数越界的报错提示,没改过来代码,只得了25分。

将所有数从小到大排序,分别为$a_1,a_2,…,a_n$. 统计每个数除以最小的数$a_1$的余数(包括$a_1$本身),然后扔到一个set里面,输出这个set的size即可.

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
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <cstring>
#include <climits>
#include <map>
#include <set>
#include <vector>
#include <string>
using namespace std;
typedef long long ll;
const int maxn=100010;
const int maxm=500050;
const int inf=INT_MAX;
inline int read() {
char c=' ';int v=0,f=1;
while(c<'0' || c>'9') {
c=getchar();if(c=='-') f=-1;
}
while(c>='0' && c<='9') {
v=v*10+c-'0';c=getchar();
}
return v*f;
}
int T;
int n,a[maxn];
inline int gcd(int a,int b) {
if(b==0) return a;
return gcd(b,a%b);
}
namespace solve1 {
void work() {
if(a[2]%a[1]==0) printf("1\n");
else printf("2\n");
}
}
namespace solve2 {
void work() {
set<int> s;
int mod=a[1];
for(int i=1;i<=n;i++) {
a[i]%=mod;
s.insert(a[i]);
}
printf("%d\n",s.size());
}
}
int main() {
//freopen("money.in","r",stdin);
//freopen("money.out","w",stdout);
T=read();
while(T--) {
n=read();bool ok=false;
for(int i=1;i<=n;i++) {
a[i]=read();
if(a[i]==1) {
ok=1;
}
}
if(ok) {
printf("1\n");continue;
}
sort(a+1,a+n+1);
if(n==1) printf("1\n");
else if(n==2) solve1::work();
else solve2::work();
}
//fclose(stdin);
//fclose(stdout);
return 0;
}

100pts

60分的做法能不能给我们一些启发呢?

首先根据数学知识进行一些推导,根据样例中3 19 10 6这组数据,答案为2. 我们发现19=10+6+3, 6=3+3,也就是说,如果货币系统中存在面值$i​$,使得$i​$元的货币可以被若干个比它小的面值之和来表示的话,那么$i​$元的货币没必要存在。因此,最终的答案一定小于等于给定的面值总数,且选定的面值一定是给定所有面值的子集

我们将所有的面值从小到大排序,循环一遍,看一下每个面值是否可以被比它小的面值表示出来,如果可以,那么没必要选择;如果不行,那么必须选择。在循环的过程中,统计所求的最小值并输出最终答案。

时间复杂度$O(Tna_i)$.

由于CCF抛弃了老爷机,换成了i7-8700k处理器和32GB内存,因此在时限内通过没有问题。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include<bits/stdc++.h>
using namespace std;
const int N=105;
int n,mx,ans=0,a[105],f[25005];
void sol() {
scanf("%d",&n);
for(int i=1;i<=n;i++)scanf("%d",&a[i]);
memset(f,0,sizeof(f));
sort(a+1,a+n+1);f[0]=1;mx=a[n];ans=0;
for(int i=1;i<=n;i++)if(!f[a[i]]) {
ans++;
for(int j=0;j+a[i]<=mx;j++)if(f[j])f[j+a[i]]=1;
}
printf("%d\n",ans);
}
int main() {
int T;scanf("%d",&T);
while(T--)sol();
return 0;
}