Codeforces Round #753 (Div. 3)

过了五题，友好度++

想着补完第六题再来，又鸽了

F题dfs做爆MLE

A题按题意将差的绝对值相加即可

B题找规律，每4步都会回到原地，然后按原点奇偶分类讨论

C题，先将数排序，注意到每次操作中都会将前一次消去，所以只需维护排序后的两数之差即可，需要留意的是这个初始情况

D题，考虑最坏情况，蓝色数填满，红色数填满。于是只需判断蓝色数是不是均大于等于自身索引，红色数字是不是均小于等于减去自身索引

E题按题意模拟，模拟到break后撤销操作，然后输出答案

---

A:

LL t;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>t;
    f(sb,1,t){
        map<char,int> m;
        string s;
        cin>>s;
        f(i,0,25){
            m[s[i]]=i+1;
        }
        cin>>s;
        auto it=s.begin();
        it++;
        LL ans=0;
        while(it!=s.end()){
            ans+=abs(m[(*it)]-m[(*(it-1))]);
            it++;
        }
        cout<<ans<<"\n";
    }
    return 0;
}

B:

LL tt,n,a;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>tt;
    f(sb,1,tt){
        cin>>n>>a;
        if(n&1){
            int t=a%4;
            if(t==1){
                n+=a;
            }
            else if(t==2){
                n-=1;
            }
            else if(t==3){
                n-=(a+1);
            }
        }
        else {
            int t=a%4;
            if(t==1){
                n-=a;
            }
            else if(t==2){
                n+=1;
            }
            else if(t==3){
                n+=(a+1);
            }
        }
        cout<<n<<"\n";
    }
    return 0;
}

C:

LL t,n,te;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>t;
    f(b,1,t){
        vi v;
        cin>>n;
        f(i,1,n){
            cin>>te;
            v.pb(te);
        }
        sort(all(v));
        auto it =v.begin();
        LL ans=(*it);
        it++;
        while(it!=v.end()){
            ans=max(ans,(*it)-(*(it-1)));
            it++;
        }
        cout<<ans<<"\n";
    }
    return 0;
}

D:

LL t,n;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>t;
    f(sb,1,t){
        cin>>n;
        vi a,b,r;
        f(i,1,n){
            LL temp;
            cin>>temp;
            a.pb(temp);
        }
        string s;
        cin>>s;
        LL cnt=0;
        for(auto it:s){
            if(it=='B') b.pb(a[cnt]);
            else r.pb(a[cnt]);
            cnt++;
        }
        sort(all(b));
        sort(rall(r));
        bool ok=1;
        LL lb=b.size(),lr=r.size();
        if(ok&&lb){
            LL tt=1;
            for(auto it:b){
                if(it<tt)
                {
                    ok=0;
                    break;
                }
                tt++;
            }
        }
       // cout<<ok;
        if(ok&&lr){
            LL tt=n;
            for(auto it:r){
                //cout<<"\n::"<<it<<tt;
                if(it>tt){
                    ok=0;
                    break;
                }
                tt--;
            }
        }
        if(ok) cout<<"YES\n";
        else cout<<"NO\n";
    }
    return 0;
}

E:

LL t,n,m;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>t;
    f(sb,1,t){
        cin>>n>>m;
        string s;
        cin>>s;
        f(i,2,n){
            string temp;
            cin>>temp;
            s+=temp;
        }
        LL r,c,rz,rf,cz,cf;
        r=c=rz=rf=cz=cf=0;
        LL cnt=0;
        for(auto it:s){
             cnt+=1;
            if(it=='L') c-=1;
            if(it=='R') c+=1;
            if(it=='U') r-=1;
            if(it=='D') r+=1;
            //cout<<c<<"::"<<r<<"\n";
            if(c<0) cf=max(cf,-c);
            else cz=max(cz,c);
            if(r<0) rf=max(rf,-r);
            else rz=max(rz,r);
            if(cf+cz+1>m||rz+rf+1>n){
            if(it=='L') cf-=1;
            if(it=='R') cz-=1;
            if(it=='U') rf-=1;
            if(it=='D') rz-=1;
                break;
            }
            if((cf||cz||rf||rz)&&c==0&&r==0)
            break;
        }
        //cout<<rz<<"MJij";
        cout<<(n-rz)<<" "<<(m-cz)<<" "<<cnt<<"\n";
    }
    return 0;
}