753#div3(A~E）

A. Linear Keyboard

原题链接：https://codeforces.com/contest/1607/problem/A
题意：给两串字符串，第一串决定字母的映射顺序，第二串求映射后的差分数组（绝对值）之和。
如：
bca
abc
映射后b的下标为1，c下标2，a下标3
第二串的差分数组之和为：| 1 - 3 | + | 2 - 1| = 3
做法：用stl自带的哈希表unordered_map水

#include <bits/stdc++.h>
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
using namespace std;
int main(){
   
	int t;cin>>t;
	while (t--){
   
		string s1,s2;cin>>s1>>s2;
		int ans = 0;
		unordered_map<char,int>mp;
		for (int i=0;i<s1.size();i++){
   
			mp[s1[i]] = i + 1;
		}
		for (int i=0;i<s2.size()-1;i++){
   
			ans += abs(mp[s2[i]]-mp[s2[i+1]]);
		}
		cout<<ans<<endl;
	}
}

B. Odd Grasshopper

原题链接：https://codeforces.com/contest/1607/problem/B
题意：给一个原坐标x0,可以向左或向右跳t格（t为时间点，如果第一次跳就跳1格，第二次跳就跳2格，以此类推），如果在奇数坐标向右跳，在偶数就向左跳，问跳了n次后的坐标位置。
做法：纸上画一下可发现跳4次是一个循环节，也可打表找规律，再分类讨论一下原坐标x0的奇偶。

#include <bits/stdc++.h>
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
using namespace std;
int main(){
   
	int t;cin>>t;
	while (t--){
   
		long long x,y;cin>>x>>y;
		long long ans = 0;
		if (x%2==0){
   
			if (y%4==0) ans = x;
			else if (y%4==1) ans = x - y;
			else if (y%4==2) ans = x + 1;
			else if (y%4==3) ans = x + y + 1;
		}
		else {
   
			if (y%4==2) ans = x - 1;
			else if (y%4==0) ans = x;
			else if (y%4==1) ans = x + y;
			else if (y%4==3) ans = x - y - 1;
		}
		cout<<ans<<endl;
	}
}

C. Minimum Extraction

原题链接：https://codeforces.com/contest/1607/problem/C
题意：给一串序列，每次挑选最小值，并将最小值去掉后让其他项减去它，直到序列长度为1。求这个过程中最小值的最大值。
做法：排序后将过程模拟出来即可。

#include <bits/stdc++.h>
#define int long long
#define INF 0x7f7f7f7f
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
using namespace std;
signed main(){
   
	int t;cin>>t;
	while (t--){
   
		int n;cin>>n;
		int a[n+1];
		for (int i=1;i<=n;i++) cin>>a[i];
		sort(a+1,a+1+n);
		int add = a[1];
		int ans = a[1];
		for (int i=2;i<=n;i++){
   
			a[i] -= add;
			ans = max(ans,a[i]);
			add += a[i];
		}
		cout<<ans<<endl;
	}
}

D. Blue-Red Permutation

原题链接：https://codeforces.com/contest/1607/problem/D
题意：给一串长度为n的数组，每个数涂上红色或蓝色，红色可无限加，蓝色无限减，问能否变成n的全排列。
做法：贪心。把红色的数往后丢，蓝色的数往前，颜色相同时让数小的在前，排序重载。

#include <bits/stdc++.h>
using namespace std;
struct Node{
   
	int x;//存数
	char y;//存颜色
};
bool cmp(Node a,Node b){
   
	if (a.y==b.y) return a.x < b.x;
	else return a.y < b.y;//让蓝色数在前
}
int main(){
   
	int t;cin>>t;
	while (t--){
   
		int n;cin>>n;
		Node a[n+1];
		for (int i=1;i<=n;i++) cin>>a[i].x;
		string s;cin>>s;
		for (int i=0;i<s.size();i++) a[i+1].y = s[i];
		sort(a+1,a+1+n,cmp);
		bool flag = 0;
		for (int i=1;i<=n;i++){
   
			if (i==a[i].x) continue;
			else if (i<a[i].x){
   
				if (a[i].y=='B') continue;
				else {
   
					flag = 1;
					break;
				}
			}
			else {
   
				if (a[i].y=='R') continue;
				else {
   
					flag = 1;
					break;
				}
			}
		}
		if (flag) puts("NO");
		else puts("YES");
	}
}

E. Robot on the Board 1

原题链接：https://codeforces.com/contest/1607/problem/E
题意：给一张n行m列的表格，机器人根据上下左右的指令行动（碰到墙壁无法执行），起点任意，问挑选哪个起点可使机器人能够执行的指令最多。
做法：模拟+思维。默认起点为（1，1），用mxn、myn、mxx、myx分别记录机器人走的横纵坐标最小值和最大值，当最小值和最大值的差值大于等于表格范围时break，小于的话就用最小值调起点位置。

#include <bits/stdc++.h>
using namespace std;
int main(){
   
	int t;cin>>t;
	while (t--){
   
		int n,m;cin>>n>>m;
		string s;cin>>s;
		int xx = 0,yy = 0;
		int mnx = 0,mny = 0,mxx = 0,mxy = 0;
		int a = 1,b = 1;
		for (auto it:s){
   
			if (it=='R') yy++;
			else if (it=='L') yy--; 
			else if (it=='D') xx++;
			else if (it=='U') xx--;
			mnx = min(mnx,xx),mny = min(mny,yy);
			mxx = max(mxx,xx),mxy = max(mxy,yy);
			if ((mxx-mnx>=n)||(mxy-mny>=m)) break;
			a = 1 - mnx;
			b = 1 - mny;
		}
		cout<<a<<" "<<b<<endl;
	}
}