Codeforces Round

发表于 | 更新于: | 分类于 | | 阅读数

差点掉分，D2有思路最后bug多多。然后A题让我们知道了自己英语是白学了

A.Drinks Choosing

题意：#%…￥%￥%…￥%……&………&%#￥%#￥…#^#**&#@$#()

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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,k;
const int maxn=1100;
int a[maxn];
int vis[maxn];
int b[maxn];
int main(){
    scanf("%d %d",&n,&k);
    //memset(vis,2,sizeof vis);
    for(int i=0; i<n; i++){
        scanf("%d",&a[i]);
        b[a[i]]++;
    }
    sort(b+1,b+1+k);
    int all=n/2+n%2;
    int ans=0;
    for(int i=1; i<=k; i++){
        if(b[i]%2==0 && b[i]!=0){
            ans+=b[i];
            all-=(b[i]/2);
            b[i]=0;
        }
        else if(b[i]%2==1 && b[i]>1){
            ans+=(b[i]-1);
            all-=(b[i]/2);
            b[i]=1;
        }
    }
    printf("%d\n",ans+all);
}

B.Sport Mafia

推公式，答案就是: $n- \frac { { \sqrt {8 * k + 8 * n + 9 } } - 3 } {2}$

1
2
3
4
5
6
7
8
9
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
    ll n,k;
    scanf("%lld %lld",&n,&k);
    ll tmp=n-(-3+(ll)sqrt(9+8*n+8*k))/2;
    printf("%lld\n",tmp);
}

C.Basketball Exercise

dp

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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll maxn=1e5+10;
ll a[maxn],b[maxn];
ll n;
ll dp[maxn][3];
int main(){
    scanf("%lld",&n);
    for(ll i=0; i<n; i++){
        scanf("%lld",&a[i]);
    }
    for(ll i=0; i<n; i++){
        scanf("%lld",&b[i]);
    }
    dp[0][0]=a[0];
    dp[0][1]=b[0];
    dp[1][0]=a[1]+b[0];
    dp[1][1]=a[0]+b[1];
    for(ll i=2; i<n; i++){
        dp[i][0]=max(dp[i-1][1],max(dp[i-2][0],dp[i-2][1]))+a[i];
        dp[i][1]=max(dp[i-1][0],max(dp[i-2][1],dp[i-2][0]))+b[i];
 
    }
    printf("%lld\n",max(dp[n-1][0],dp[n-1][1]));
}

D1.Submarine in the Rybinsk Sea

求贡献

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=998244353;
ll n;
ll a[100010];
char s[20];
int main(){
    scanf("%lld",&n);
    ll ans=0;
    for(ll i=0; i<n; i++){
        scanf("%s",s);
        ll len=strlen(s);
        ll tmp=0;
        for(ll i=0; i<len; i++){
            tmp=(tmp+(s[i]-'0'))%mod;
            if(i<len-1) tmp=(tmp*100)%mod;
        }
        //printf("%lld %lld\n",tmp,tmp*10);
        ans=(ans+tmp)%mod;
        ans=(ans+tmp*10)%mod;
    }
    printf("%lld\n",ans*n%mod);
}

D2.Submarine in the Rybinsk Sea

与D1不同的是，每个数的长度不一样。

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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=998244353;
ll n;
char s[100010][20];
ll vis[20];
ll ba[25];
ll sum[20];
int main(){
    ba[0]=1;
    for(ll i=1; i<25; i++){
        ba[i]=ba[i-1]*10%mod;
    }
    scanf("%lld",&n);
    ll ans=0;
    for(ll i=0; i<n; i++){
        scanf("%s",s[i]);
        ll len=strlen(s[i]);
        vis[len]++;
    }
    for(ll i=18; i>0; i--){
        sum[i]=sum[i+1]+vis[i];
        //printf("%lld %lld %lld\n",i,sum[i],vis[2]);
    }
    ll cnt=0;
    for(ll ii=0; ii<n; ii++){
        ll c=strlen(s[ii]);
        for(ll i=c; i>=0; i--){
            if(vis[i]==0) continue;
            ll tmp=0;
            ll f=-1;
            //puts(s[ii]);
            for(ll k=0; k<c-i; k++){
                tmp=(tmp*10)%mod;
                tmp=(tmp+s[ii][k]-'0')%mod;
                f=k;
            }
            tmp=(tmp*ba[(i)*2])%mod*(vis[i]*2)%mod;
            //printf("%lld && %lld %lld %lld\n",tmp,f,ba[i*2],c);
            f++;
            ll tmpp=0;
            for(ll k=f; k<c; k++){
                tmpp=(tmpp+(s[ii][k]-'0'))%mod;
                //printf("%c %lld\n",s[ii][k],tmpp);
                if(k<c-1) tmpp=(tmpp*100)%mod;
            }
            //printf("%lld %lld %lld\n",tmpp,tmpp*10,sum[c]);
            if(tmp==0) tmp=(tmp+((tmpp+tmpp*10)*sum[c]%mod))%mod;
            else tmp=(tmp+((tmpp+tmpp*10)*vis[i]%mod))%mod;
            ans=(ans+tmp)%mod;
        }
        //printf("%lld %lld\n",tmp,tmp*10);
    }
    printf("%lld\n",ans%mod);
}
thanks!