今天题出的异常顺利，希望不要被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;
}