http://codeforces.com/contest/1073/problem/C 题意:给你长度为n的字符串,每个字符为L, R, U, D。给你终点位置(x, y)。你每次出发的起点为(0, 0)。你可以改动每次的移动方向到达(x,y)点。求改动的MaxID-MinID+1是多少。
思路:
先分别求x轴,y轴上的前缀和,偏于之后判断区间是否满足条件。详细见代码。
固定左端点,二分枚举右端点。判断左右端点的区间是否能够达成目标(区间长度是否大于未完成量,奇偶性是否相同)
注意点:
strlen是O(n)的复杂度,超时了。
之前没遇到过固定一个点,然后另一个点二分逼近值的。
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <stack>
#define ll long long
#define localusing namespace std;const int MOD = 1e9+;
const int inf = 0x3f3f3f3f;
const double PI = acos(-1.0);
const int maxn = 2e5+;int n;
ll endx, endy;
ll total;
char str[maxn];
int sumx[maxn];
int sumy[maxn];bool ok(int l, int r) {
int nowx = sumx[n-]-sumx[r];
int nowy = sumy[n-]-sumy[r];
if (l > ) {
nowx += sumx[l-];
nowy += sumy[l-];
}
ll diff = abs(endx-nowx)+abs(endy-nowy);
if (diff <= r-l+ && ((diff&))==((r-l+)&)) return ;
else return ;
}int main() {
#ifdef local
if(freopen("/Users/Andrew/Desktop/data.txt", "r", stdin) == NULL) printf("can't open this file!\n");
#endif
scanf("%d", &n);
scanf("%s", str);
scanf("%lld%lld", &endx, &endy);
total = abs(endx)+abs(endy);//总的步数
//如果两者奇偶性不同也不行
if (total>n || ((total&) != (n&))) {
printf("-1\n");
return ;
}
sumx[] = ;
sumy[] = ;
int len = int(strlen(str));//strlen(str)是O(n)的复杂度 orz...
for (int i = ; i < len; ++i) {
int incx = ; int incy = ;
if (str[i] == 'U') {
incy = ;
} else if (str[i] == 'R') {
incx = ;
} else if (str[i] == 'D') {
incy = -;
} else {
incx = -;
}
if (i) {
sumx[i] += sumx[i-]+incx;
sumy[i] += sumy[i-]+incy;
}
else {
sumx[i] = incx;
sumy[i] = incy;
}
}
if (sumx[n-]==endx && sumy[n-]==endy) {
printf("0\n");
return ;
}
int mn = inf;
//枚举点
for (int i = ; i < n; ++i) {
int l = i-; int r = n-;
while (r-l > ) {
int m = (l+r)>>;
if (ok(i, m)) {
r = m;
} else {
l = m;
}
}
//判断一下r是否可行
if (ok(i, r)) mn = min(mn, r-i+);
}
printf("%d\n", mn);
#ifdef local
fclose(stdin);
#endif
return ;
}