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

Educational Codeforces Round 60 (Rated for Div. 2)

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

A. Best Subsegment

题意：

给出n个数，选取一段区间[l,r]，满足(a_l+...+a_r)/(r-l+1)最大，这里l<=r，并且满足区间长度尽可能大。

题解：

因为l可以等于r，所以我们可以直接考虑最大值，因为题目要求，直接求连续的最大值的长度就是了。

代码如下：

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = 2e5+;

int n;

int a[N];

int main(){

    cin>>n;

    int cnt=,ans=;

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

    int mx=*max_element(a+,a+n+);

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

        if(a[i]==mx && a[i-]==mx){

            cnt++;

        }else{

            ans=max(ans,cnt);

            cnt=;

        }

    }

    cout<<max(ans,cnt);

    return ;

}

B. Emotes

题意：

输入n,m,k，n表示元素个数，每个元素都有其权值；m表示最多可以选取的个数；k表示同一个元素最多被连续选取多少次。

这里每种元素都有无限多个，问怎样选可以使得最终获得权值和最大。

题解：

这个直接贪心就好了。

代码如下：

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = 2e5+;

ll n,m,k;

ll a[N];

int main(){

    cin>>n>>m>>k;

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

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

    }

    sort(a+,a+n+);

    reverse(a+,a+n+);

    ll fir = a[],sec = a[];

    ll ans=;

    if(fir==sec){

        cout<<m*fir;

    }else{

        ans = k*fir+sec;

        ll tmp = m/(k+);

        ans*=tmp;

        tmp*=(k+);

        ans+=(m-tmp)*fir;

        cout<<ans;

    }

    return ;

}

C. Magic Ship

题意：

在二维坐标轴上给出起点和终点的坐标，然后会给n天的天气预报，表示风向，不同的风向对应那一天会多往哪个方向走。天气情况是循环来的 ，循环节为n。

现在问最少要多少天，可以让船从起点走到终点。如果无论如何走不到终点，输出-1。

题解：

这个题我一开始考虑复杂了。其实这里风向带来的位置变化，和船开动的位置变化，可以分开来，也就是说，如果考虑n天的位置变化，可以先看风向给船带来的影响(船会被吹到哪去)，再考虑船自身的航行方向。如果想清楚了这一点，那么直接二分天数就好了，最后通过曼哈顿距离来判断可行性。

这里单调性的证明也有点意思，很显然地，时间越短越不可能到终点；另一个方面，假设船在x时间可以到终点，那么时间越长，也更有可能到终点，因为船可以借助风向，在一个位置保持不变。

细节见代码吧(注意二分天数)：

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = 1e5+;

struct Point{

    ll x,y;

}st,ed,cur;

char s[N];

int n;

ll prex[N],prey[N];

int check(ll x){

    ll d = x/n;

    cur.x=st.x+d*prex[n];

    cur.y=st.y+d*prey[n];

    cur.x=cur.x+prex[x%n];

    cur.y=cur.y+prey[x%n];

    ll dis=abs(cur.x-ed.x)+abs(cur.y-ed.y);

    return dis<=x;

}

int main(){

    cin>>st.x>>st.y>>ed.x>>ed.y;

    cin>>n;

    scanf("%s",s+);

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

        prex[i]=prex[i-];prey[i]=prey[i-];

        prex[i]+=(s[i]=='R');

        prex[i]-=(s[i]=='L');

        prey[i]+=(s[i]=='U');

        prey[i]-=(s[i]=='D');

    }

    ll l=,r=1e15,mid;

    while(l<r){

        mid=l+r>>;

        if(check(mid)) r=mid;

        else l=mid+;

    }

    if(l==1e15) cout<<-;

    else cout<<l;

    return ;

}

D. Magic Gems

题意：

给出n和m，然后有n个可分解物品，连续的m个可分解物品可以被分解成m个不可分解物品。现在问一共有多少种分解方式，可以让最后都有n个物品(包含可分解与不可分解)。

题解：

这题可以考虑组合数来求解，枚举分解i组物品，那么答案就是C(n-i*(m-1),i)，但是这个题行不通，枚举i就爆掉了。

通过考虑第i个数的状态，可以考虑递推：设f_i为前i个物品的分解总数，那么f_i=f_i-1+f_i-m，分别对应第i个物品不参与分解以及参与分解。

结合题目数据范围，要用矩阵乘法来加速，具体矩阵构造什么的看代码吧：

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = ,MOD = 1e9+;

struct matrix{

    ll A[N][N];

    int n,m;

    matrix(){

        memset(A,,sizeof(A));

    }

    void Print(){

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

            for(int j=;j<=m;j++){

                cout<<A[i][j]<<" ";

            }

            cout<<endl;

        }

    }

};

matrix operator * (const matrix &a,const matrix &b){

    matrix ans;

    ans.n=a.n;ans.m=b.m;

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

        for(int j=;j<=ans.m;j++){

            for(int k=;k<=b.n;k++){

                ans.A[i][j]=(ans.A[i][j]+a.A[i][k]*b.A[k][j]%MOD)%MOD;

            }

        }

    }

    return ans ;

}

matrix operator + (const matrix &a,const matrix &b){

    matrix ans;

    ans.n=a.n;ans.m=a.m;

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

        for(int j=;j<=ans.m;j++){

            ans.A[i][j]=(a.A[i][j]+b.A[i][j])%MOD;

        }

    }

    return ans ;

}

matrix qp_Mat(matrix a,ll b){

    matrix ans;

    ans.n=ans.m=a.n;

    for(int i=;i<=ans.n;i++) ans.A[i][i]=;

    while(b){

        if(b&) ans=ans*a;

        a=a*a;

        b>>=;

    }

    return ans ;

}

int main(){

    ll n,m;

    cin>>n>>m;

    matrix trans;

    trans.n=m;trans.m=m;

    trans.A[][]=trans.A[][m]=;

    for(int i=;i<=m;i++) trans.A[i][i-]=;

    matrix ans;

    ans.n=m;ans.m=m;

    for(int i=;i<=m;i++) ans.A[i][]=;

    if(n<m){

        cout<<;

    }else{

        matrix Ans = qp_Mat(trans,n-m+);

        Ans=Ans*ans;

        cout<<Ans.A[][];

    }

    return ;

}

E. Decypher the String

题意：

每组数据会有n个交换操作，但是这是个交互题不会告诉你。他只会告诉你f(长度为n的串)，表示将串进行n次交换操作过后得到的串。

然后你只有三次询问机会，最后输出原串是什么。

题解：

这是一个很有意思的交互题。n最大只有10000，通过观察26^2<n<26^3，那么可以往26这方面考虑一下。

注意到当n<=26时，我们只需要一个所有26个字母的顺序排列，就很容易知道位置的变化情况。

然后构造这样的字符串:aaa...aaa(26*26)bbb....，并且称26*26为一个大段，那么类比上面的情况，通过询问，很容易知道目前第i个位置在原来哪个大段。

然后构造:aaa..aa(26)bbb...bb...zz....，上面每个大段中有26*26个数，也就是我们将每个数的范围限定在了某个长度为26*26的区间中，现在我们构造的字符串，可以进一步将第i个数范围缩小到长度为26的区间。

最后再构造ab..zabc...这样的串，就可以找到第i个数原来的位置在哪里了。

这三个操作的本质其实就是求a*26²+b*26¹+c中，每个位置i对应的a,b,c值，这里的a,b,c都是不超过25的。

是不是感觉十分巧妙...将问题转化为26进制的问题，据说还可以通过crt来搞，但目前我的姿势水平还不够呜呜。

代码如下：

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = 2e5+;

int n;

char str[N],s[N],ans[N];

ll f[N];

int main(){

    scanf("%s",str);

    int len=strlen(str);

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

        for(int j=;j<len;j++){

            if(i==) s[j]='a'+j%;

            if(i==) s[j]='a'+j/%;

            if(i==) s[j]='a'+j//%;

        }

        printf("? %s\n",s);

        fflush(stdout);

        char tmp[N];

        scanf("%s",tmp);

        for(int j=;j<len;j++){

            if(i==) f[j]+=tmp[j]-'a';

            if(i==) f[j]+=(tmp[j]-'a')*;

            if(i==) f[j]+=(tmp[j]-'a')**;

        }

    }

    char ans[N];

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

        ans[f[i]]=str[i];

    }

    printf("! ");

    printf("%s",ans);

    return ;

}

Educational Codeforces Round 60 (Rated for Div. 2) 题解的相关教程结束。