Codeforces Round #753 (Div. 3) A B C D E F

Rank 2072/10812 div3难得勉强没掉分，时间太赶了，E不是很难，赛后能做掉。

A. Linear Keyboard

思路：不愧是$div3$的A题，裸模拟就好，在$26$个键盘中查找所求字符串每两个相邻的$abs$距离，然后加起来即可。

• 参考代码

#include<bits/stdc++.h>
using namespace std;
#define snow ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define re register int
#define int long long 
#define fer(i,a,b) for(re i = a ; i <= b ; i ++)
#define der(i,a,b) for(re i = a ; i >= b ; i --)
#define lowbit(x) (x&-x)
int gcd(int a,int b){return b?gcd(b,a%b):a;}
int lcm(int a,int b){return a*b/gcd(a,b);}
typedef pair<int,int>PII;
typedef pair<int,string>PIS;
void solve(){
    string s;
    cin>>s;
    string s1;
    cin>>s1;
    int cnt=0;
    for(int i=1;i<s1.size();i++){
        int a=s.find(s1[i]);
        int b=s.find(s1[i-1]);
        cnt+=abs(a-b);
    }
    cout<<cnt<<endl;
}
signed main(){
    snow;
    int t;
    cin>>t;
    while(t--){
        solve();
    }
    return 0;
}

B. Odd Grasshopper

思路：小数学，我是根据输入A，B的奇偶性进行选择。不管A是奇数还是偶数，B只要非$0$，那么能影响B的只有B%$4$的几个数，然后模拟一下找规律，当A是偶数的时候符号变化是$-++-$，当A是奇数的时候符号变化是$+–+$
应该有更简单的不管A的奇偶性直接加个偏移量做，大致思路就是这样。

• 参考代码

#include<bits/stdc++.h>
using namespace std;
#define snow ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define re register int
#define int long long 
#define fer(i,a,b) for(re i = a ; i <= b ; i ++)
#define der(i,a,b) for(re i = a ; i >= b ; i --)
#define lowbit(x) (x&-x)
int gcd(int a,int b){return b?gcd(b,a%b):a;}
int lcm(int a,int b){return a*b/gcd(a,b);}
typedef pair<int,int>PII;
typedef pair<int,string>PIS;
void solve(){
    int a,b;
    cin>>a>>b;
    if(b==0){
        cout<<a<<endl;
        return ;
    }
    if(a%2==0){
            int k=b%4;
            int f=b/4;
            b-=f*4;
            int gg=f*4;
            for(int i=1;i<=b;i++){
                if(i==1)a-=gg+i;
                if(i==2)a+=gg+i;
                if(i==3)a+=gg+i;
                if(i==4)a-=gg+i;
            }
            cout<<a<<endl;
            return ;
    }
    else{
        int k=b%4;
            int f=b/4;
            b-=f*4;
            int gg=f*4;
            for(int i=1;i<=b;i++){
                if(i==1)a+=gg+i;
                if(i==2)a-=gg+i;
                if(i==3)a-=gg+i;
                if(i==4)a+=gg+i;
            }
            cout<<a<<endl;
            return ;
    }
}
signed main(){
    snow;
    int t;
    cin>>t;
    while(t--){
        solve();
    }
    return 0;
}

C. Minimum Extraction

思路：很容易想到的是暴力情况下，将一个数组中每次删去一个当前局最小的数，同时更新$MAX$的大小(这里的$MAX$指的是当前局数组中最小的元素)，但是明显，如果暴力查找更新的话时间复杂度会爆炸。之后再进行思考如何进行优化操作，发现我们可以将数组排个序，因为每次减去的都是局中最小的元素，根据$Y$总的曲线救国思想，后面的数同时加上或减去一个数并不影响他们之间的相对关系。所以出局顺序是固定的，因为前者经历的后者必定会经历(经历就是前面出局数对当前数的影响)，因为后者比前者晚出局，而真正能影响后者与前者的关系是前者出局即后者成为下一个准备出局的数，所以前者出局之后后者的大小就变成了后者数减去前面状态的更迭和前者数。最后每次更新一下$MAX$就变成了一个$O(n)$做法。

• 参考代码

#include<bits/stdc++.h>
using namespace std;
#define snow ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define re register int
#define int long long 
#define fer(i,a,b) for(re i = a ; i <= b ; i ++)
#define der(i,a,b) for(re i = a ; i >= b ; i --)
#define lowbit(x) (x&-x)
int gcd(int a,int b){return b?gcd(b,a%b):a;}
int lcm(int a,int b){return a*b/gcd(a,b);}
typedef pair<int,int>PII;
typedef pair<int,string>PIS;
const int N=2e5+10;
int a[N];
void solve(){
    int n;
    cin>>n;
    for(int i=0;i<n;i++)cin>>a[i];
    sort(a,a+n);
    int MA=a[0];
    for(int i=1;i<n;i++){
        MA=max(MA,a[i]-a[i-1]);
    }
    cout<<MA<<endl;

}
signed main(){
    snow;
    int t;
    cin>>t;
    while(t--){
        solve();
    }
    return 0;
}

D. Blue-Red Permutation

思路：$排序+贪心$，判断能否操作红蓝元素使得数组变成一个全排列，我们可以将$a$数组排个序，判断每一位是否合法，遇到不合法的话直接$Puts(“NO”)$返回就好了，否则就是都是合法的，最后输出$YES$。然后进行贪心操作即可。

• 参考代码

#include<bits/stdc++.h>
using namespace std;
#define snow ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define re register int
#define int long long 
#define fer(i,a,b) for(re i = a ; i <= b ; i ++)
#define der(i,a,b) for(re i = a ; i >= b ; i --)
#define lowbit(x) (x&-x)
int gcd(int a,int b){return b?gcd(b,a%b):a;}
int lcm(int a,int b){return a*b/gcd(a,b);}
typedef pair<int,int>PII;
typedef pair<int,string>PIS;
const int N=2e5+10;
pair<int,char>a[N];
bool st[N];
void solve(){
   int n;
   cin>>n;
   for(int i=0;i<n;i++)cin>>a[i].first;
   string s;
   cin>>s;
   for(int i=0;i<n;i++)a[i].second=s[i];
   sort(a,a+n);
   int cnt=0;
   for(int i=0;i<n;i++){
       int x=a[i].first;
       char y=a[i].second;
       if(y=='B'){
           if(x<=cnt){
               cout<<"NO"<<endl;
               return ;
           }
           else if(x>cnt){
               cnt++;
           }
       }
   }
   for(int i=0;i<n;i++){
       int x=a[i].first;
       char y=a[i].second;
       if(y=='R'){
       if(x>cnt+1){
               cout<<"NO"<<endl;
               return;
          }
           else cnt++;
       }
   }
    cout<<"YES"<<endl;
    return;
}
signed main(){
    snow;
    int t;
    cin>>t;
    while(t--){
        solve();
    }
    return 0;
}

E. Robot on the Board 1

思路：先从朴素入手，所有点跑一遍取能最大的移动的点(多个的话去任一)，那么本题其实也是一个静态问题，我们只需要找到优化点，将其复杂度降为$O(n)$即可。我的想法是将题目转化为一个红线扫描问题，有上下左右四个扫描线，一开始初始化左和上的扫描线为0，右扫描线为m+1，下扫描线为n+1，根据通过统计$”LRUD”$出现的次数以及”LR”、”UD”之间的关系来更新扫描线的位置，当四个扫描线内无法存下格点说明已经超了robot的移动极限，因此取上一状态存下来的任一四个扫描线内的格点输出即可。代码更易理解！！如下：

• 参考代码：

#include<bits/stdc++.h>
using namespace std;
#define snow ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define re register int
#define int long long 
#define fer(i,a,b) for(re i = a ; i <= b ; i ++)
#define der(i,a,b) for(re i = a ; i >= b ; i --)
#define lowbit(x) (x&-x)
int gcd(int a,int b){return b?gcd(b,a%b):a;}
int lcm(int a,int b){return a*b/gcd(a,b);}
typedef pair<int,int>PII;
typedef pair<int,string>PIS;
const int N=1e6+10;
int t;
void solve(){
    int n,m;
    cin>>n>>m;//行列
    string s;
    cin>>s;
    int l=0,u=0,d=n+1,r=m+1;//初始化四个扫描线的初始位置(格子不能触碰到扫描线且必须在扫描线区内才有效)
    pair<int,int>end;//用来存最终答案
    end={1,1};
    int suml=0,sumr=0,sumu=0,sumd=0;//统计字符出现的数量。
    for(int i=0;i<s.size();i++){
        if(s[i]=='U')sumu++;
        else if(s[i]=='L')suml++;
        else if(s[i]=='R')sumr++;
        else sumd++;
        //以下四个操作是为了取扫描线的最极位置,因为在极限外的格子已经不予考虑。
        l=max(l,suml-sumr);
        r=min(r,m+1-(sumr-suml));
        u=max(u,sumu-sumd);
        d=min(d,n+1-(sumd-sumu));
        if(l+1>=r||u+1>=d){//如果两个出现至少一个,那么扫描线区无法容纳格点,输出存入的最终格点即可。
            cout<<end.first<<' '<<end.second<<endl;
            return ;
        }
        else{
            end={u+1,l+1};//如果至少还能放一个格点,那么肯定会有x=u+1,y=l+1的格点存在我们使新格点为它即可。
        }
    }
    cout<<end.first<<' '<<end.second<<endl;//如果所有字符跑完了还有格点能生存,那么我们输出就好了。
}
signed main(){
    cin>>t;
    while(t--){
        solve();
    }
    return 0;
}

F. Robot on the Board 2

每个格子都有一个符号表示它到达的下一个位置，那么实则问题就转化成了有很多条链子，我们需要找到最长链子的初始格子即可。我们只需要分析三种状态。$1:$跑出界外 $2:$碰到了之前已经更新过的点 $3:$当前链子更新的时候碰到了 本次更新过的点，也就是构成了回路(回路中所有点距离一样)

• 参考代码：

#include<bits/stdc++.h>
using namespace std;
#define snow ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define re register int
#define int long long 
#define fer(i,a,b) for(re i = a ; i <= b ; i ++)
#define der(i,a,b) for(re i = a ; i >= b ; i --)
#define lowbit(x) (x&-x)
int gcd(int a,int b){return b?gcd(b,a%b):a;}
int lcm(int a,int b){return a*b/gcd(a,b);}
typedef pair<int,int>PII;
typedef pair<int,string>PIS;
const int N=2010;
char s[N][N];
int f[N][N],d[N][N];
int stk[N*N*2];
signed main(){
    int t;
    cin>>t;
    while(t--){
        int n,m;
        cin>>n>>m;
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){cin>>s[i][j];f[i][j]=0;d[i][j]=0;}
        }
        for(int i=1;i<=n;i++)
            for(int j=1;j<=m;j++)
                if(!f[i][j]){
                    int x=i,y=j;
                    int tt=0;
                    while(x&&y&&x<=n&&y<=m&&!d[x][y]){
                        stk[++tt]=x,stk[++tt]=y;
                        d[x][y]=tt;
                        if(s[x][y]=='L')y-=1;
                        else if(s[x][y]=='R')y+=1;
                        else if(s[x][y]=='U')x-=1;
                        else if(s[x][y]=='D')x+=1;
                    }
                    if(x&&y&&x<=n&&y<=m&&!f[x][y]){
                        int ty=stk[tt--],tx=stk[tt--];
                        int ti=(d[tx][ty]-d[x][y])/2+1;
                        while(tx!=x||ty!=y){
                            f[tx][ty]=ti;
                            ty=stk[tt--],tx=stk[tt--];
                        }
                        f[x][y]=ti;
                    }
                    for(int i=(x&&y&&x<=n&&y<=m?f[x][y]:0)+1;tt;i++){
                        int y=stk[tt--],x=stk[tt--];
                        f[x][y]=i;
                    }
                }
        int x=1,y=1,sum=1;
        for(int i=1;i<=n;i++)
            for(int j=1;j<=m;j++)
                if(f[i][j]>sum){
                    sum=f[i][j];
                    x=i,y=j;
                }
        cout<<x<<' '<<y<<' '<<sum<<endl;
    }
    return 0;
}