玄关求调

机器人（robot） 【题目描述】 在一个二维坐标平面上有一个机器人，初始位于 (0, 0)。小明可以通过遥控器向机器 人发送一串移动指令序列。 • U 机器人从 (x, y) 移动到 (x, y + 1)。 • D 机器人从 (x, y) 移动到 (x, y − 1)。 • L 机器人从 (x, y) 移动到 (x − 1, y)。 • R 机器人从 (x, y) 移动到 (x + 1, y)。 机器人收到指令序列后开始移动，如 URRD，机器人会从 (0, 0) 移动到 (2, 0)。小明 希望机器人能移动到他指定的位置 (x, y)。现在他可以修改指令序列中的某些指令，修改 规则是 R → L, L → R, U → D, D → U，也就是说，机器人收到某一个指令后可以向 指令相反的方向移动。已知长度为 n 的指令序列 s1s2 · · · sn,si ∈ {U, D, L, R} 和目标位置 (x, y)，小明可以选定一个区间 [l, r] (1 ≤ l ≤ r ≤ n)，并对 slsl+1 · · · sr 中的 .某 .些指令执行 修改操作。请最小化区间 [l, r] 的长度 r − l + 1 使得小明可以通过修改指令使得机器人移 动到 (x, y)。 如果无法通过修改指令使得机器人移动到 (x, y) 请输出 Impossible。如果机器人可 以不需要通过修改操作到达 (x, y) 请输出 0。否则请输出区间的最短长度。 【输入格式】 从文件 robot.in 中读入数据。 .本 .题 .的 .测 .试 .点 .包 .含 .有 .多 .组 .测 .试 .数 .组 输入的第一行包含一个整数 T，表示测试数据组数。 每组测试数据第一行包含三个正整数 n, x, y，表示指令序列的长度和目标位置。 接下来一行一个长度为 n 的字符串 s1s2 · · · sn 表示指令序列。 【输出格式】 输出到文件 robot.out 中。 输出 T 行，第 i 行表示第 i 组测试数据的答案

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+10;
int n,x,y;
char str[N];
int sx[N],sy[N];
bool check(int len){
	for(int i=1;i+len-1<=n;++i){
		int j=i+len-1;
		int xx=sx[n]-(sx[j]-sx[i-1]),yy=sy[n]-(sy[j]-sy[i-1]);
		if(abs(x-xx)+abs(y-yy)<=len and (len-abs(x-xx)-abs(y-yy))%2==0)  return true;
	}
	return false;
} 
void solve(){
	cin>>n>>x>>y;
	cin>>str+1;
	if(abs(x-y)>n or (n-x-y)%2){
		cout<<"Impossible"<<endl;
		return ;
	}
	for(int i=1;i<=n;++i){
		sx[i]=sx[i-1];
		sy[i]=sy[i-1];
		if(str[i]=='U')  sy[i]++;
		else if(str[i]=='D')  sy[i]--;
		else if(str[i]=='L')  sx[i]--;
		else if(str[i]=='R')  sx[i]++;
	}
	int l=0,r=n;
	while(l<r){
		int mid=l+r>>1;
		if(check(mid))  r=mid;
		else l=mid+1;
	}
	cout<<l<<endl;
	return ;
}
signed main(){
	int T;
	cin>>T;
	while(T--){
		solve();
	}
	return 0;
}