Codeforces Contest 1073 problem C Vasya and Robot —— 尺取

69 阅读 0 评论 46 点赞

我是靠谱客的博主粗犷小蘑菇，最近开发中收集的这篇文章主要介绍Codeforces Contest 1073 problem C Vasya and Robot —— 尺取，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

Vasya has got a robot which is situated on an infinite Cartesian plane, initially in the cell (0,0). Robot can perform the following four kinds of operations:

U — move from (x,y) to (x,y+1);
D — move from (x,y) to (x,y−1);
L — move from (x,y) to (x−1,y);
R — move from (x,y) to (x+1,y).
Vasya also has got a sequence of n operations. Vasya wants to modify this sequence so after performing it the robot will end up in (x,y).

Vasya wants to change the sequence so the length of changed subsegment is minimum possible. This length can be calculated as follows: maxID−minID+1, where maxID is the maximum index of a changed operation, and minID is the minimum index of a changed operation. For example, if Vasya changes RRRRRRR to RLRRLRL, then the operations with indices 2, 5 and 7 are changed, so the length of changed subsegment is 7−2+1=6. Another example: if Vasya changes DDDD to DDRD, then the length of changed subsegment is 1.

If there are no changes, then the length of changed subsegment is 0. Changing an operation means replacing it with some operation (possibly the same); Vasya can’t insert new operations into the sequence or remove them.

Help Vasya! Tell him the minimum length of subsegment that he needs to change so that the robot will go from (0,0) to (x,y), or tell him that it’s impossible.

Input
The first line contains one integer number n (1≤n≤2⋅105) — the number of operations.

The second line contains the sequence of operations — a string of n characters. Each character is either U, D, L or R.

The third line contains two integers x,y (−109≤x,y≤109) — the coordinates of the cell where the robot should end its path.

Output
Print one integer — the minimum possible length of subsegment that can be changed so the resulting sequence of operations moves the robot from (0,0) to (x,y). If this change is impossible, print −1.

Examples
inputCopy
5
RURUU
-2 3
outputCopy
3
inputCopy
4
RULR
1 1
outputCopy
0
inputCopy
3
UUU
100 100
outputCopy
-1
Note
In the first example the sequence can be changed to LULUU. So the length of the changed subsegment is 3−1+1=3.

In the second example the given sequence already leads the robot to (x,y), so the length of the changed subsegment is 0.

In the third example the robot can’t end his path in the cell (x,y).

题意：

给你一个长度为n的串，仅含有4种字符
U — move from (x,y) to (x,y+1);
D — move from (x,y) to (x,y−1);
L — move from (x,y) to (x−1,y);
R — move from (x,y) to (x+1,y).
差不多这个意思，就是移动的位置。
起始位置是0,0，然后给你一个目标位置，问你不可以增加，不可以减小这个串的长度，仅可以在其中选一个区间修改内容，问你到目标位置最少需要改的长度是多少。

题解：

首先特判目标位置的x+y大于n和目标位置与初始到达的位置是一样的情况，之后就是尺取，以前我都是用while来做，但是听说for一遍r会更好一点？那就试试看。每一个r我们找最大的l，让(r-l+1)这个长度是能够从当前位置到达目标位置的长度，但是要判断这两个是否奇偶，举个例子:
6
RLRLRL
1 0
这种情况怎么样都不可能到达了，因为(r-l+1)与位置偏差大小不是同奇偶的。

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5;
char s[N];
map<int,int>mp;
int main()
{
int sx=0,sy=0;
int n;
scanf("%d",&n);
scanf("%s",s+1);
int fx,fy;
scanf("%d%d",&fx,&fy);
if(abs(fx)+abs(fy)>n)
return 0*printf("-1n");
for(int i=1;i<=n;i++)
{
if(s[i]=='U')
sy++;
else if(s[i]=='D')
sy--;
else if(s[i]=='L')
sx--;
else
sx++;
}
if(sx==fx&&sy==fy)
return 0*printf("0n");
int l=1,minn=n+1;
for(int r=1;r<=n;r++)
{
if(s[r]=='U')
sy--;
else if(s[r]=='D')
sy++;
else if(s[r]=='L')
sx++;
else
sx--;
while(l<=r&&abs(fx-sx)+abs(fy-sy)<=r-l+1)
{
if(((abs(fx-sx)+abs(fy-sy)))%2==(r-l+1)%2)
minn=min(minn,r-l+1);
if(s[l]=='U')
sy++;
else if(s[l]=='D')
sy--;
else if(s[l]=='L')
sx--;
else
sx++;
l++;
}
}
printf("%dn",minn==n+1?-1:minn);
return 0;
}