Educational Codeforces Round 53 (Rated for Div. 2) C. Vasya and Robot（二分或者尺取）

题意：给出一个序列，序列有四个字母组成，U:y+1,D:y-1 , L:x-1 , R:x+1; 这是规则。给出（x,y) 问可不可以经过最小的变化这个序列可以由（0,0) 变到(x,y)

注意！！！！是可以变任意序列的！不是只有y变y ， x变x ，比赛看错题意导致没A ,

分析：这需要借助前置和与后缀和，这样的话我就可以知道[L , R] 这个区间需要变化什么，没错你可以理解为题目的范围n变为[L , R] , x变为x-xl[L+1]-xr[R+1] ,y同理；这样我们就可以运用尺取法，不断的枚举区间就好了。我用的是尺取法，许多人用的是二分，不过思想是一样的，这个一样贴出代码

需要理解下判断条件问题（结合代码）：很容易就知道n<abs(x)+abs(y) 这样是不行的，还有就是n与（abs(x)+abs(y))的奇偶性也必须一样，因为不可能有偶数次运算后变奇数（建议模拟一遍）；既然前面说到是理解为题目的范围n变为[L , R] , x变为x-xl[L+1]-xr[R+1] ,y同理，那在二分或者尺取的时候的判断也是如此

尺取：

#include<bits/stdc++.h>
using namespace std ;
const int maxn = 2*1e5+1;
#define ll long long
ll xl[maxn],xr[maxn],yl[maxn],yr[maxn];
char s[maxn];
int main( )
{
    int n,x,y;

    scanf("%d",&n);
    getchar();
    scanf("%s",s+1);
    scanf("%d%d",&x,&y);
    int NOWX=0,NOWY=0;
    int MIN=n;
    for(int i=1 ; i<=n ; i++)
    {
        xl[i]=xl[i-1];
        yl[i]=yl[i-1];
        if(s[i]=='U')
        {
          yl[i]++;
          NOWY++;
        }
        if(s[i]=='D')
        {
          yl[i]--;
          NOWY--;
        }
        if(s[i]=='L')
        {
           xl[i]--;
           NOWX--;
        }
        if(s[i]=='R')
        {
          xl[i]++;
          NOWX++;
        }
    }

    if(NOWX==x&&NOWY==y)
    {
        puts("0");
        return 0;
    }
    if(abs(x)+abs(y)>n)
    {
        puts("-1");
        return 0;
    }
    if((n-(abs(x)+abs(y)))%2!=0)
    {
        puts("-1");
        return 0;
    }
    for(int i=n ; i>=1 ; i--)
    {
        xr[i]=xr[i+1];
        yr[i]=yr[i+1];
        if(s[i]=='U')
        {
          yr[i]++;
        }
        if(s[i]=='D')
        {
          yr[i]--;
        }
        if(s[i]=='L')
        {
           xr[i]--;
        }
        if(s[i]=='R')
        {
          xr[i]++;
        }
    }
    int head,tail;
    head=1;
    tail=1;
    while(1)
    {

        int X=xr[tail+1]+xl[head-1];
        int Y=yr[tail+1]+yl[head-1];
        int D=tail-head+1;
      //  printf("%d %d (%d %d)
",head,tail,X,Y);
        if((D>=abs(x-X)+abs(y-Y))&&(D-abs(X-x)-abs(Y-y))%2==0)
        {
            head++;
            MIN=min(MIN,D);
        }
        else
            tail++;
        if(tail>n)
        break;

    }
    printf("%d
",MIN);
}

View Code

二分：

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
int xl[N],yl[N],xr[N],yr[N];
int n;
int x,y;
int check(int mid)
{
    int l=1;
    for(int r=mid;r<n;r++)
    {
       int tx=xl[l-1]+xr[r+1];
       int ty=yl[l-1]+yr[r+1];
       int rx=abs(x-tx);
       int ry=abs(y-ty);
       if(mid>=rx+ry && (mid-(rx+ry))%2==0)
        return 1;
       l++;
    }
    return 0;
}
int main()
{
    cin>>n;
    string s;
    cin>>s;
    s='@'+s;
    n++;
    for(int i=1;i<n;i++)
    {
        xl[i]=xl[i-1],
        yl[i]=yl[i-1];
        if(s[i]=='U')
        {
          yl[i]++;
        }
        if(s[i]=='D')
        {
          yl[i]--;
        }
        if(s[i]=='L')
        {
           xl[i]--;
        }
        if(s[i]=='R')
        {
          xl[i]++;
        }
    }
    for(int i=n-1;i>0;i--)
    {
        xr[i]=xr[i+1],
        yr[i]=yr[i+1];
        if(s[i]=='U')
        {
          yr[i]++;
        }
        if(s[i]=='D')
        {
          yr[i]--;
        }
        if(s[i]=='L')
        {
          xr[i]--;
        }
        if(s[i]=='R')
        {
          xr[i]++;
        }
    }
    cin>>x>>y;
    int l=-1,h=n;
    while(h-l>1)
    {
       int mid=(h+l)/2;
       if(check(mid))
        h=mid;
       else l=mid;
    }
    if(h==n)cout<<"-1";
    else
    cout<<h;
}

View Code