A. Three Friends

题意
给定 $a, b, c$ ，可以让每个数最多操作一次 $+ 1$ 或 $? 1$ ，问最小化得到的 $∣ a ? b ∣ + ∣ a ? c ∣ + ∣ b ? c ∣$ 值。
解题思路
贪心思考，我们可以对这 $3$ 个点进行排序，那么这样看我们易知，让这 $3$ 个点靠在一起最优。
所以我们分类讨论两者之间的大小关系，考虑是否进行操作。
当然，这道题也可以直接暴力枚举每个值的变化状态，然后取最小值输出即可。
AC代码

/**
  *@filename:A
  *@author: pursuit
  *@created: 2021-08-21 14:53
**/
#include <bits/stdc++.h>
#define debug(a) cout << "debug : " << (#a)<< " = " << a << endl

using namespace std;

typedef pair<int,int> pii;
typedef long long ll;
const int N = 1e5 + 10;
const int P = 1e9 + 7;
const int INF = 0x3f3f3f3f;

int t,a[3];
bool vis[N];
void solve(){
    sort(a,a + 3);
    if(a[1] > a[0]){
        a[0] ++;
        if(a[1] > a[0])a[1] --;
        if(a[2] > a[0])a[2] --;
    }
    else if(a[1] == a[0]){
        a[0] ++,a[1] ++;
        if(a[2] > a[0])a[2] --;
        else if(a[2] < a[0])a[2] ++;
    }
    int ans = abs(a[2] - a[1]) + abs(a[2] - a[0]) + abs(a[1] - a[0]);
    printf("%d\n", ans);
}
int main(){	
    scanf("%d", &t);
    while(t -- ){
        for(int i = 0; i < 3; ++ i)scanf("%d", &a[i]);
        solve();
    }
    return 0;
}

B. Snow Walking Robot

题意
给你一个指令顺序，从中删除最少的指令并重排使得机器人行走路线只会经过除 $(0, 0)$ 的点一次，且最后回到起点。
解题思路
我们知道，如果要回到起点，那么我们所用的指令 $cnt_l=cnt_r,cnt_u=cnt_d$ 。我们再细致分析，如果 $\ and\ min(U,D) > 0$ ，那么我们是可以利用其围成一个矩形的，这样能保证实现要求。否则，我们最多只能在 $x$ 或者 $y$ 轴上做移动，这个时候指令序列长度就最多只能为 $2$ 了，即踏出一步再返回。
至此，我们具体分析处理即可。
AC代码

/**
  *@filename:B
  *@author: pursuit
  *@created: 2021-08-21 15:05
**/
#include <bits/stdc++.h>
#define debug(a) cout << "debug : " << (#a)<< " = " << a << endl

using namespace std;

typedef pair<int,int> pii;
typedef long long ll;
const int N = 1e5 + 10;
const int P = 1e9 + 7;
const int INF = 0x3f3f3f3f;

int q,u,r,l,d;
string s;
/*
访问了除(0,0)单元格两次，就会中断。
有多少个R就要有多少个L，同理有多少个U就要有多少个D。
*/
void solve(){
    for(int i = 0; i < s.size(); ++ i){
        if(s[i] == 'U')u ++;
        else if(s[i] == 'R')r ++;
        else if(s[i] == 'L')l ++;
        else d ++;
    }
    int minn1 = min(u,d),minn2 = min(l,r);
    if(minn1 == 0 || minn2 == 0){
        if(minn1 >= 1 || minn2 >= 1){
            if(minn1 >= 1){
                cout << 2 << '\n' << "UD" << endl; 
            }
            else{
                cout << 2 << '\n' << "LR" << endl;
            }
        }
        else{
            cout << 0 << endl;
        }
    }
    else{
        u = d = minn1,l = r = minn2;
        cout << 2 * minn1 + 2 * minn2 << endl;
        //绕个正方形。
        for(int i = 0; i < u; ++ i){
            cout << 'U';
        }
        for(int i = 0; i < l; ++ i){
            cout << 'R';
        }
        for(int i = 0; i < d; ++ i){
            cout << 'D';
        }
        for(int i = 0; i < r; ++ i){
            cout << 'L';
        }
        cout << endl;
    }
}
int main(){	
    cin >> q;
    while(q -- ){
        u = r = l = d = 0;
        cin >> s;
        solve();
    }
    return 0;
}

C. Yet Another Broken Keyboard

题意
给定不能敲打的字符和一个字符串 $s$ ，问能敲出多少个合法的子串。
解题思路
如果一个字符串是合法字符串，那么其所有子串都是合法的，不难得出如果一个合法字符串长度为 $n$ ，那么其所有合法子串的数量为 $\frac{n\times(n + 1)}{2}$ 。所以我们可以找到最长的合法子串，然后计算统计即可，再跳到下一个直到遍历完字符串即可。这个过程可以用双指针实现。
AC代码

/**
  *@filename:C
  *@author: pursuit
  *@created: 2021-08-21 15:26
**/
#include <bits/stdc++.h>
#define debug(a) cout << "debug : " << (#a)<< " = " << a << endl

using namespace std;

typedef pair<int,int> pii;
typedef long long ll;
const int N = 2e5 + 10;
const int P = 1e9 + 7;
const int INF = 0x3f3f3f3f;

int n,k;
char s[N];
bool vis[200];
void solve(){
    int l = 1,r = 1;
    ll ans = 0;
    while(l <= n){
        while(r <= n && vis[s[r]])r ++;
        //[l,r - 1]都是有效的。
        ans += 1LL * (r - l + 1) * (r - l) / 2;
        l = r;
        if(!vis[s[l]])l ++;
        r = l;
    }
    cout << ans << endl;
}
int main(){
    cin >> n >> k >> s + 1;	
    char c;
    for(int i = 0; i < k; ++ i){
        cin >> c;
        vis[c] = true;
    }
    solve();
    return 0;
}

D. Remove One Element

题意
给定一个序列，你最多可以删除一个元素。问能产生的最长连续上升子序列长度是多少？
解题思路
我们可以用 $d p 1 [i]$ 来表示最后一位元素为 $a [i]$ 的最长连续上升子序列长度， $d p 2 [i]$ 来表示最开始的元素为 $a [i]$ 的最长连续上升子序列长度。
那么当我们枚举删除元素的时候，我们即是判断前面子序列和后面子序列能否拼接在一起，即是判断 $a [i ? 1] < a [i + 1]$ 。如果是相等的，那么不难发现构成的拼接连续子序列为 $d p [i ? 1] + d p [i + 1$ 。枚举删除元素取最大值即可。
AC代码

/**
  *@filename:D
  *@author: pursuit
  *@created: 2021-08-21 15:37
**/
#include <bits/stdc++.h>
#define debug(a) cout << "debug : " << (#a)<< " = " << a << endl

using namespace std;

typedef pair<int,int> pii;
typedef long long ll;
const int N = 2e5 + 10;
const int P = 1e9 + 7;
const int INF = 0x3f3f3f3f;

int n,a[N],dp1[N],dp2[N];
void solve(){
    for(int i = 2; i <= n; ++ i){
        if(a[i] > a[i - 1]){
            dp1[i] = dp1[i - 1] + 1;
        }
    }
    for(int i = n - 1; i >= 1; -- i){
        if(a[i] < a[i + 1]){
            dp2[i] = dp2[i + 1] + 1;
        }
    }
    //枚举删除的元素。
    int maxx = 0;
    for(int i = 1; i <= n; ++ i){
        maxx = max(maxx,dp1[i]);
        if(i >= 2 && i <= n - 1 && a[i - 1] < a[i + 1]){
            //debug(i);
            maxx = max(maxx,dp1[i - 1] + dp2[i + 1]);
        }
    }
    printf("%d\n", maxx);
}
int main(){	
    scanf("%d", &n);
    for(int i = 1; i <= n; ++ i){
        scanf("%d", &a[i]);
        dp1[i] = 1;
        dp2[i] = 1;
    }
    solve();
    return 0;
}

E. Nearest Opposite Parity

题意
给你一个序列 $a$ ，在 $i$ 位置上的元素能跳到 $i ? a [i]$ 或者 $i + a [i]$ 上。求出每个元素跳到值奇偶不同的最小步骤。
解题思路
一开始想的是 $d f s$ ，即从每个点开始记忆化搜索处理。但随着好几发Wa之后才懵懂，我们 $d f s$ 是不能保证是最小路径的，同时，我们还很难处理环，即很容易出现TLE。这个时候就要想到 $b f s$ 求最短路了，由于我们 $i$ 是由 $i + a [i]$ 和 $i ? a [i]$ 得到的，所以即可看成是从 $i + a [i], i ? a [i]$ 到 $i$ 的，我们建立边。然后由于我们是要找到奇偶性不同的，所以我们可以将所有奇数点和偶数点分开存放。然后从奇数点出发跑 $b f s$ ，得到到偶数点的最短路，同理同偶数点出发，得到到奇数点的最短路。
至此题解。
AC代码

/**
  *@filename:E_New
  *@author: pursuit
  *@created: 2021-08-21 18:53
**/
#include <bits/stdc++.h>
#define debug(a) cout << "debug : " << (#a)<< " = " << a << endl

using namespace std;

typedef pair<int,int> pii;
typedef long long ll;
const int N = 2e5 + 10;
const int P = 1e9 + 7;
const int INF = 0x3f3f3f3f;

//反向建边。
int n,a[N],dp[N][2];
struct edge{
    int to,next;
}edges[N];
int head[N],tot;
vector<int> odd,even,ans;
void add(int u,int v){
    edges[++ tot].to = v;
    edges[tot].next = head[u];
    head[u] = tot;
}
void bfs(vector<int> &st, vector<int> &ed){
    vector<int> dp(n + 1,INF);//初始化。
    queue<int> q;
    for(auto &u : st)dp[u] = 0,q.push(u);
    while(!q.empty()){
        int u = q.front();
        q.pop();
        for(int i = head[u]; i; i = edges[i].next){
            int v = edges[i].to;
            if(dp[v] == INF){
                dp[v] = dp[u] + 1;
                q.push(v);
            }
        }
    }
    for(auto &v : ed){
        if(dp[v] != INF){
            ans[v] = dp[v];
        }
    }
}
void solve(){
    ans.resize(n + 1, - 1);
    bfs(odd,even);
    bfs(even,odd);
    for(int i = 1; i <= n; ++ i){
        printf("%d ", ans[i]);
    }
    puts("");
}
int main(){	
    scanf("%d", &n);
    for(int i = 1; i <= n; ++ i){
        scanf("%d", &a[i]);
        if(a[i] & 1)odd.push_back(i);
        else even.push_back(i);
        int idx1 = i - a[i], idx2 = i + a[i];
        if(idx1 >= 1)add(idx1,i);
        if(idx2 <= n)add(idx2,i);
    }
    solve();
    return 0;
}