Codeforces Round #494 (Div. 3) 1003 A/C/D题解

A题:非常简单,只要找重复数字的最大个数即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include<iostream>
#include<algorithm>
using namespace std;
int arr[105];
int main(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        int tmp;
        cin>>tmp;
        arr[tmp]++;
    }
    int maxn=0;
    for(int i=1;i<=100;i++){
        maxn=max(maxn,arr[i]);
    }
    cout<<maxn;
}

C题:用个前缀和优化一下,剩下的暴力去吧。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<string>
using namespace std;
int n,k;
double arr[5005];
int main(){
    cin>>n>>k;
    for(int i=1;i<=n;i++)cin>>arr[i];
    for(int i=2;i<=n;i++)arr[i]+=arr[i-1];
    double maxavg=0,curavg;
    for(int i=k;i<=n;i++){
        for(int j=i;j<=n;j++){
            curavg=(arr[j]-arr[j-i])/i;
            maxavg=max(maxavg,curavg);
        }
    }
    printf("%.15lf",maxavg);
}

D题:把所有二的次幂数全部搞到桶里,然后按照次幂由高到低往下减,看最后能不能减到0,如果能即可,不能就不能。

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
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<string>
using namespace std;
int n,q;
int bucket[32];
int powarr[32];
int checkpower(int num){
    if(num==1)return 0;
    int cnter=0;
    while(num!=1){
        num/=2;
        cnter++;
    }
    return cnter;
}
void program_init(){
    powarr[0]=1;
    for(int i=1;i<=30;i++){
        powarr[i]=powarr[i-1]*2;
    }
}
int main(){
    program_init();
    cin>>n>>q;
    for(int i=1;i<=n;i++){
        int num;
        cin>>num;
        bucket[checkpower(num)]++;
    }
    for(int i=1;i<=q;i++){
        int num,cnter=0;
        cin>>num;
        for(int i=30;i>=0;i--){
            cnter+=min(num/powarr[i],bucket[i]);
            num-=min(num/powarr[i],bucket[i])*powarr[i];
        }
        if(num!=0)cout<<-1<<endl;
        else cout<<cnter<<endl;
    }
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注