Educational Codeforces Round 57 (Rated for Div. 2) ABCDEF题解

题目总链接：https://codeforces.com/contest/1096

A. Find Divisible

题意：

给出l,r，在[l,r]里面找两个数x,y，使得y%x==0，保证有解。

题解：

直接输出l,2*l就好啦，但我还是写了个循环...

代码如下：

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = ;

int T;

ll l,r;

int main(){

    cin>>T;

    while(T--){

        scanf("%I64d%I64d",&l,&r);

        for(ll i=l;i<=r;i++){

            if(i*<=r){

                printf("%I64d %I64d\n",i,*i);

                break ;

            }

        }

    }

    return ;

}

B. Substring Removal

题意：

给出一个字符串，现在要你删掉一个子串，使得剩下的串有不多于一个的字符。

题解：

从两端找连续的相同字符串并且统计个数，然后算算就可以了。

注意一下所有字符串都相等的情况。

还有一种情况就是两段连续的字符串字符都相等，那么这时就可以删掉中间的，这个个数也比较好统计。

具体见代码（注意中间计算过程不要爆int）:

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = 2e5+,MOD = ;

int n;

char s[N];

int main(){

    scanf("%d",&n);

    scanf("%s",s);

    char fir = s[];

    int i;

    ll cnt1=,cnt2=;

    for(i=;i<n;i++){

        if(s[i]==fir) cnt1++;

        else break ;

    }

    char last = s[n-];

    for(i=n-;i>=;i--){

        if(s[i]==last) cnt2++;

        else break ;

    }

    ll ans = (cnt1+cnt2+)%MOD;

    if(last==fir){

        ans=(ans+cnt1*cnt2)%MOD;

    }

    cout<<ans<<endl;

    return ;

}

C. Polygon for the Angle

题意：

给出一个角度(0<=angle<180)，求出最小的正多边形，满足其中存在一个内接三角形的内角与给出的角度相等。

题解:

我的做法比较暴力了，先说说我的吧：

n边形的内角和为(n-2)*180，然后可以知道其每个内角为(n-2)*180/n，利用外接圆+一些圆的性质(圆心角等于二倍圆周角)可以知道一个正n边形的内接三角形的最小角为180/n。

之后只要判断angle%(180/n)是否为0就是了。注意最小角可以为小数，所以我直接是暴力循环...

正解是这样的，首先推出最小角为180/n，然后如果满足angle%(180/n)==0的话，则有n*angle=t*180。

由于180和angle为已知量，我们就可以求出g=gcd(angle,180)，然后等式则有n*angle/g = t*180/g。

由这可以知道n=x*180/g , t=y*angle/g，我们知道，这里的t满足t*180/n=angle，当t=n-2时，这时就是正多边形的内角，所以有限制条件：1<=t<=n-2。

我们取x=y=1，这里的n就是答案了（贪心），但是可能会存在这种情况：t=n-1，这时不符合限制条件的，这里我们只要取x=2就行了。

可以证明，当x>=2时，t<=n-2恒成立。

给出我的暴力代码....

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

int T;

int ang;

int main(){

    cin>>T;

    while(T--){

        scanf("%d",&ang);

        double ans ;

        int flag;

        for(int i=;i<=;i++){

            ans = (double)/i;

            flag=;

            if(%i!=) for(int j=;;j++){

                if(j*ans>ang){

                    flag=;

                    break ;

                }else if((double)j*ans==(double)ang){

                    cout<<i<<endl;

                    flag=;

                    break ;

                }

            }

            if(flag==) continue ;

            else if(flag==) break ;

            if(ang%(int)ans==&&ans*(i-)>=ang){

                cout<<i<<endl;

                break ;

            }

        }

    }

    return ;

}

D. Easy Problem

题意：

给出一个字符串，现在要求删去一些字符，使得字符串中不含"hard"子序列，删去一个字符有相应代价，问最小代价。

题解:

如果不存在"hard"子序列的话，我们只需要将其中一个字符删完就行。

我们考虑用动态规划来做，dp(i,j)表示长度为i的字符串中，将第j个删完的最小代价。因为对于每一个字符都有删与不删两种选择。

那么转移方程就为:if(s[j]=='r')（举例）dp(i,j)=min(dp(i,j-1),dp(i-1,j)+a[j]) ; else dp(i,j)=dp(i-1,j).

意思第一个方程的意思即为要么将"r"字符删完，要么将之前的"h"或者"a"的字符删完，求两者的最小代价。

最后求min(dp(n,0),dp(n,1),dp(n,2),dp(n,3))即可。

代码如下:

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = 1e5+;

ll dp[N][];

//dp(i,j):前i个位置，将第j个删完的最小代价。

char s[N];

ll a[N];

int n;

int main(){

    scanf("%d",&n);

    scanf("%s",s+);

    for(int i=;i<=n;i++) scanf("%d",&a[i]);

    for(int i=;i<=n;i++){

        dp[i][]=dp[i-][]+(s[i]=='h')*a[i];

        dp[i][]=min(dp[i-][],dp[i-][]+(s[i]=='a')*a[i]);

        dp[i][]=min(dp[i-][],dp[i-][]+(s[i]=='r')*a[i]);

        dp[i][]=min(dp[i-][],dp[i-][]+(s[i]=='d')*a[i]);

    }

    cout<<min({dp[n][],dp[n][],dp[n][],dp[n][]});

    return ;

}

E. The Top Scorer

题意：

给出p,s,r，p即人头数，s即每个人得分的总和，r即主人公的分数下限。

现在每个人都忘了自己的分数是多少，只有主人公知道自己的分数下限，问最后主人公获胜的概率是多少。

ps：当有多个人分数相同时，获胜概率为其除以相应人数。

题解:

这题全场A的人数最少，但也的确有点难度。

通过每个人去划分s，可以联想到“插板法”的计算方法。

我们可以看看一个类似的问题:x1+x2+x3+x4+x5=20,0<=xi<=5，问解的情况有多少种。

这实际上是有上界的问题，如果存在的话应该用容斥原理去解。

我们也可以将这个题限定一个上界，设g(s,p,m):p个人，分数和为s，每个人分数不超过m的情况数，这就类似于刚才说的问题。

主要问题是g的计算，我们首先算出总情况：C(s-1+p,p-1)。在这些情况中会有些不符合要求的情况，那么我们减去至少有一个人分数大于m的情况:C(p,1)*C(s-1+p-1*(m+1),p-1)。

这里会多减去一些情况（可以将每个人看做一个独立的集合），然后再加回来....

最后可以得出g的计算方法为：

然后观察一下数据范围，发现可以枚举，那么我们就枚举主人公的得分，再枚举有多少个人分数与之相同，最后计算一下就OK。

本体细节有点多，写的时候注意下，提示:组合。

代码如下：

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = ,MOD = ;

ll p,s,r;

ll fac[N+N];

ll qp(ll a,ll b){

    ll ans = ;

    while(b){

        if(b&) ans=ans*a%MOD;

        a=a*a%MOD;

        b>>=;

    }

    return ans ;

}

ll inv(ll x){

    return qp(x,MOD-);

}

ll C(ll n,ll m){

    if(n==m) return ;

    if(m>n) return ;

    return fac[n]*inv(fac[m]*fac[n-m]%MOD)%MOD;

}

ll g(ll S,ll P,ll m){

    ll ans=,tmp;

    if(!S && !P) return ;  //!!

    for(int i=;i<=P;i++){

        tmp = C(P,i)*C(S+P--i*(m+),P-)%MOD;

        if(i&) ans-=tmp;

        else ans+=tmp;

        ans%=MOD;

        if(ans<) ans+=MOD;

    }

    return ans ;

}

int main(){

    cin>>p>>s>>r;

    fac[]=;

    for(int i=;i<=1e4;i++) fac[i]=fac[i-]*i%MOD;

    ll w=;

    for(int t=r;t<=s;t++){

        for(int q=;q<=p;q++){

            if(s-q*t<) continue ;

            w=(w+(C(p-,q-)*g(s-q*t,p-q,t-)%MOD)*inv(q)%MOD)%MOD;

        }

    }

    cout<<w*inv(C(s--r+p,p-))%MOD;

    return ;

}

F. Inversion Expectation

题意:

给你一个1-n的排列，但现在缺失了一些数字，现在要求逆序对个数的期望值。

题解：

注意这里是期望，期望是线性的，可以分开来算。

这个题主要考虑四种情况：（假设-1的个数为cnt）

1.未知与未知。这种情况的期望值为(cnt-1)*cnt/4，因为对于一个排列，都会存在另一个与之相反的排列，他们的总逆序对个数为(cnt-1)*cnt/2。我们就可以看作每个排列的逆序对个数为(cnt-1)*cnt/4。

2.左边未知与右边已知；

3.左边已知与右边未知。

上面两种情况思考的方式都是一样的，拿第二种情况来说吧，我们只需要统计未出现的数字中有多少个比当前这个已知数大（假设为num），以及当前已知数左边有多少个位置为-1（假设为len）。

那么对于每个位置，产生一个逆序对的概率为num/cnt，其期望也为num/cnt，那么对于当前这个已知数，它对答案的贡献为len*num/cnt。

另外一种情况同样的求法。

4.已知与已知。这时的期望值就是逆序对的个数，用树状数组或者归并排序求一下就好了。

代码如下：

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = 2e5+,MOD = ;

int n;

int a[N],c[N],large[N],vis[N];

int lowbit(int x){

    return x&(-x);

}

ll qp(ll A,ll B){

    ll ans=;

    while(B){

        if(B&) ans=ans*A%MOD;

        A=A*A%MOD;

        B>>=;

    }

    return ans ;

}

ll inv(ll x){

    return qp(x,MOD-);

}

void update(int p,int x){

    for(;p<=n;p+=lowbit(p)) c[p]+=x;

}

ll getsum(int p){

    ll cnt = ;

    for(;p>;p-=lowbit(p)) cnt+=c[p];

    return cnt ;

}

int main(){

    scanf("%d",&n);

    ll cnt = ,ans =,num;

    for(int i=;i<=n;i++){

        scanf("%d",&a[i]);

        if(a[i]==-) cnt++;

        else vis[a[i]]=;

    }

    int cur = ;

    for(int i=n;i>=;i--){

        large[i]=cur;

        cur+=!vis[i];

    }

//Case1:

    ans=(ans+(cnt-)*cnt%MOD*inv()%MOD)%MOD;

//Case2:

    num = ;

    for(int i=;i<=n;i++){

        if(a[i]==-) num++;

        else{

            ll len = large[a[i]];

            ans=(ans+num*len%MOD*inv(cnt)%MOD)%MOD;

        }

    }

//Case3:

    num = ;

    for(int i=n;i>=;i--){

        if(a[i]==-) num++;

        else{

            ll len = cnt-large[a[i]];

            ans=(ans+num*len%MOD*inv(cnt)%MOD)%MOD;

        }

    }

//Case4:

    for(int i=n;i>=;i--){

        if(a[i]==-) continue ;

        ans=(ans+getsum(a[i]))%MOD;

        update(a[i],);

    }

    cout<<ans;

    return ;

}

巴特西

Educational Codeforces Round 57 (Rated for Div. 2) ABCDEF题解

最新文章

热门文章