Educational Codeforces Round 60 (Rated for Div. 2)（ABC）

╰+攻爆jí腚メ 2023-06-03 13:52 20阅读 0赞

A. Best Subsegment

题意：给你一组数字，让你找到最长且平均数最大且没有小数的长度

解：平均数最大，直接找最大值，然后找最大值的长度（注意处理最后一个）

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include <bits/stdc++.h>
    using namespace std;
    const int maxn=1e5+10;
    typedef long long ll;
    int a[maxn];
    int main(){
        int n;
        cin>>n;
        int maxx=-1;
        for(int i=1;i<=n;i++){
            cin>>a[i];
            maxx=max(maxx,a[i]);
        }
        int ans=1;
        int cnt=0;
        for(int i=1;i<=n;i++){
            if(a[i]==maxx&&a[i+1]==maxx&&i!=n){
                cnt++;
            }
            else{
                if(a[i]==a[i-1])cnt++;
                ans=max(cnt,ans);
                cnt=0;
            }
            //cout<<cnt<<endl;
        }
        cout<<ans<<endl;
     
     
        return 0;
    }

B. Emotes

题意：n个数，让你找出m个数，使得和最大，每个数可以重复选择，最多选择k次；

解：排序，选k个最大+1个次大搭配；

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include <bits/stdc++.h>
    using namespace std;
    const int maxn=2e5+10;
    typedef long long ll;
    ll a[maxn];
    bool cmp(ll x,ll y){
        return x>y;
    }
    int main(){
        int n;
        ll k,m;
        cin>>n>>k>>m;
        for(int i=1;i<=n;i++){
            cin>>a[i];
        }
        sort(a+1,a+1+n,cmp);
        if(m>=k){
            cout<<k*a[1]<<endl;
        }
        else if(k%(m+1)==0){
            cout<<(a[1]*m+a[2])*(k/(m+1))<<endl;
        }
        else {
            //cout<<(k/(m+1))<<endl;
            //cout<<(k%(m+1))<<endl;
            cout<<(a[1]*m+a[2])*(k/(m+1))+a[1]*(k%(m+1))<<endl;
        }
     
     
        return 0;
    }
    /*
    6 9 6
    6 6 6 6 6 6
    6 6 9
    6 6 6 6 6 6
    */

C. Magic Ship

题意：航海，给你起点和终点，每天的风向，航行的轨迹就是风向+你要行驶的方向，你也可以选择不动（只跟着风），求最少到达终点的天数；

解：刚看一头雾水，后来看一下大佬的巧妙做法~

二分答案，直接找第x天风能让船到的地方，然后再判断一下x天用自己的方向能否到达终点；

风的走向用前缀和 来存一下。1e9还不行，要分1e18~

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include <bits/stdc++.h>
    using namespace std;
    const int maxn=1e5+10;
    typedef long long ll;
    ll sx,sy;
    ll gx,gy;
    ll n;
    ll dx[maxn],dy[maxn];
    char s[maxn];
    bool check(ll mid){
        ll x=sx+mid/n*dx[n]+dx[mid%n];
        ll y=sy+mid/n*dy[n]+dy[mid%n];
        if(abs(x-gx)+abs(y-gy)<=mid)return true;
        return false;
    }
    int main(){
        cin>>sx>>sy>>gx>>gy;
        cin>>n;
        cin>>s+1;
        dx[0]=0,dy[0]=0;
        for(int i=1;i<=n;i++){
            dx[i]=dx[i-1];
            dy[i]=dy[i-1];
            if(s[i]=='U')dy[i]++;
            else if(s[i]=='D')dy[i]--;
            else if(s[i]=='L')dx[i]--;
            else if(s[i]=='R')dx[i]++;
        }
        ll l=0,r=1e18;
        ll mid;
        ll ans=1LL*(1e18+10);
        while(l<=r){
            mid=(l+r)>>1;
            if(check(mid)){
                r=mid-1LL;
                ans=mid;
            }
            else l=mid+1LL;
        }
        if(ans==1e18+10)cout<<"-1"<<endl;
        else cout<<ans<<endl;
    
    
        return 0;
    }

转载于:https://www.cnblogs.com/lin1874/p/11410981.html

[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20230601/e836b9f583b247bb82f3043e9c29f8bd.png