Codeforces Round #753 (Div. 3) 题解(A-E)

今天题出的异常顺利,希望不要被hack。

A.Linear Keyboard

题意

给你一个钢琴,有26个琴键,分别对应26个字母。然后给出一个字符串,需要算出用钢琴弹出这个字符串的手指最大移动距离。

题解

签到题,建好map之后直接加绝对值。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int _;
    cin>>_;
    while(_--){
        string s1,s2;
        cin>>s1;
        cin>>s2;
        map<char,int> mp;
        for(int i=0;i<s1.size();i++){
            mp[s1[i]]=i;
        }
        int re=0;
        int c=mp[s2[0]];
        for(int i=1;i<s2.size();i++){
            re+=abs(c-mp[s2[i]]);
            c=mp[s2[i]];
        }
        cout<<re<<endl;
    }
    return 0;
}

B.Odd Grasshopper

题意

一只蚱蜢初始在x点,在数轴上跳n次,第i次跳跃距离为i。当前下标为偶数,则向左跳,否则向右跳,求n次跳跃后的位置。

题解

找规律,初始位置为偶数则-1+2+3-4-5+6+7-8-9…….除了第一个以外每四个符号循环一次。初始位置为奇数以此类推。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int _;
    cin>>_;
    while(_--){
        ll x,n;
        cin>>x>>n;
        if(n==0){
            cout<<x<<endl;
            continue;
        }
        if(x%2==0){
            n--;x--;
            if(n%4==0){
                cout<<x-4*(n/4)<<endl;
            }
            else if(n%4==1){
                cout<<x-4*(n/4)+n+1<<endl;
            }
            else if(n%4==2){
                cout<<x-4*(n/4)+n+n+1<<endl;
            }
            else{
                cout<<x-4*(n/4)+(n-1)+n-(n+1)<<endl;
            }
        }
        else{
            n--;x++;
            if(n%4==0){
                cout<<x+4*(n/4)<<endl;
            }
            else if(n%4==1){
                cout<<x+4*(n/4)-(n+1)<<endl;
            }
            else if(n%4==2){
                cout<<x+4*(n/4)-(n)-(n+1)<<endl;
            }
            else{
                cout<<x+4*(n/4)-(n-1)-(n)+n+1<<endl;
            }
        }

    }
    return 0;
}

C.Minimum Extraction

题意

给出一个数组,当数组内元素个数大于1时,我们可以选一个最小的数,让数组中所有元素都减去它,然后把它删除。我们可以执行这个操作任意次,直到数组大小为1。我们希望让数组中的最小值尽可能大,并输出这个值。

题解

排序之后记录前缀和,扫一遍就能求出结果。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int _;
    cin>>_;
    while(_--){
        ll n;
        cin>>n;
        vector<ll> num(n);

        for(int i=0;i<n;i++){
            cin>>num[i];

        }
        sort(num.begin(),num.end());
        if(num.size()==1){
            cout<<num.back()<<endl;
            continue;
        }
        ll pl=0;
        ll re=num.front();
        for(int i=0;i<num.size();i++){
            re=max(re,num[i]-pl);
            pl+=num[i]-pl;
        }
        cout<<re<<endl;

    }
    return 0;
}

D.Blue-Red Permutation

题意

给出一个数组,每个元素都有颜色。在一次操作中,我们可以选择一个蓝色的数-1,也可以选择一个红色表示+1。若干次操作之后,能否形成1-n的全排列?

题解

考虑贪心,蓝色的只能减,从小到大排,然后小的数我们优先给安排尽可能小的值,如果出现无法安排就NO。例如我们已经安排了3,下一个数还是3,由于只能减,所以一定不能构成全排列。
红色从大到小遍历,同理。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int _;
    cin>>_;
    while(_--){
        ll n;
        cin>>n;
        ll num[n];
        for(int i=0;i<n;i++){
            cin>>num[i];
        }
        vector<ll> bl;
        vector<ll> re;
        string s;
        cin>>s;
        for(int i=0;i<s.size();i++){
            if(s[i]=='R') re.push_back(num[i]);
            else bl.push_back(num[i]);
        }
        sort(bl.begin(),bl.end());
        sort(re.begin(),re.end(),greater<ll>());
        bool f=1;
        set<ll> s1;
        //cout<<1<<endl;
        for(int i=0;i<bl.size();i++){
            if(bl[i]<1){
                f=0;
                break;
            }

            //cout<<1<<endl;
            if(s1.empty()){
                s1.insert(1);
                continue;
            }
            auto j=s1.end();
            j--;
            if(bl[i]>=*j+1){
                s1.insert(*j+1);
                continue;
            }
            else{
                f=0;
                break;
            }
        }
        //if(f==0) cout<<"N"<<endl;
        set<ll> s2;
        for(int i=0;i<re.size();i++){
            if(re[i]>n){
                f=0;
                break;
            }
            if(s2.empty()){
                s2.insert(n);
                continue;
            }
            if(re[i]<=(*s2.begin())-1){
                s2.insert((*s2.begin())-1);
                continue;
            }
            else{
                //cout<<re[i]<<endl;
                f=0;
                break;
            }
        }
        if(f==1) cout<<"YES"<<endl;
        else cout<<"NO"<<endl;

    }
    return 0;
}

E.Robot on the Board 1

题意

给出n*m的格子和机器人每次的移动方向,机器人移出边界就停止运行,求机器人应该从哪个点出发能使移动次数最多。

题解

维护每次移动后机器人相对起始点走过的最高距离、最低距离、最左端距离、最右端距离的最大值,当某一次移动的(最高距离+最低距离)> n-1或(最左距离+最右距离)>m-1时,无论从哪个点出发都会停止运行,答案就是这个点之前的点可以放的位置,(最左距离+1,最上距离+1)。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct maxx{
    ll l=0,r=0,u=0,d=0;
};
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int _;
    cin>>_;
    while(_--){
        ll n,m;
        cin>>n>>m;
        string s;
        cin>>s;
        maxx mx[s.size()];
        ll x=0,y=0;
        for(int i=0;i<s.size();i++){
            if(s[i]=='L')x--;
            if(s[i]=='R')x++;
            if(s[i]=='U')y--;
            if(s[i]=='D')y++;
            if(i!=0) mx[i]=mx[i-1];
            if(x>0) mx[i].r=max(mx[i].r,x);
            else if(x<0) mx[i].l=max(mx[i].l,-x);
            if(y<0) mx[i].u=max(mx[i].u,-y);
            else if(y>0) mx[i].d=max(mx[i].d,y);
        }
        ll sx=1,sy=1;
        for(int i=0;i<s.size();i++){
           // cout<<mx[i].u<<" "<<mx[i].d<<" "<<mx[i].l<<" "<<mx[i].r<<endl;
            ll sxx=sx,syy=sy;
            if(mx[i].u+mx[i].d<n)sxx=mx[i].u+1;
            else break;
            if(mx[i].l+mx[i].r<m)syy=mx[i].l+1;
            else break;
            sx=sxx;sy=syy;
        }
        cout<<sx<<" "<<sy<<endl;

    }
    return 0;
}

知识共享许可协议
Text is available under CC BY-NC-SA 4.0 unless otherwise stated.

除非特殊声明,本站所有内容均以 CC BY-NC-SA 4.0协议授权。
暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇