题解：P7745 [COCI2011-2012#3] ROBOT

· · 题解

这道题应该不需要用到二分。

Solution

大体：

通过题目描述，我们可以维护出在当前位置的上面、下面、左面、右面各有多少个控制点，这样我们只需要求出一开始时的距离总和同一个 x 坐标的控制点数量以及同一个 y 坐标的控制点数量，每次移动通过上次求出的距离总和来更新当前的位置总和。

具体：

（我把当前与机器人同一个 x 坐标的控制点归入右边，同一个 y 坐标的控制点归入上边，当然你也可以不这样，但做法还是一致的。）

首先输入时，我们统计出机器人在 (0,0) 的时候上下左右各有多少控制点和同一个 x 坐标的控制点数量以及同一个 y 坐标的控制点数量，并且算出此时的距离总和。

然后，我们按照题目要求模拟：

  1. 当输入的是 S 时：

我们发现蓝色部分的距离是 -1 的，绿色部分的距离是 +1 的，显然与原来的 y 坐标相同的控制点距离要 +1，与现在的 y 坐标相同的控制点距离要 -1 。

改完距离后，我们再更新机器人上面的控制点个数和下面的控制点个数。

  1. 当输入的是 J 时：

由于移动的距离为 1 ，所以移动后，蓝色部分的距离是 +1 的，绿色部分是 -1 的。

改完距离后，我们再更新机器人上面的控制点个数和下面的控制点个数。

  1. 当输入的是 I 时：

原理同输入为 S。

  1. 当输入的是 Z 时：

原理同输入为 J。

AC code

#include <bits/stdc++.h>
#define int long long
using namespace std;
int x, y;//当前机器人坐标为 (x,y) 
int n, m;
int sum; //距离总和 
string opt;
int sumx[40000004];
int sumy[40000004];
int up, down, _left, _right; //上下左右各有多少控制点 
int _hash(int x) { return x + 10000010; } //由于坐标有负数不能直接当下标，所以来个简单的hash 
int hash_(int x) { return x - 10000000; }
signed main() {
    scanf("%lld%lld", &n, &m);
    sum = 0;
    for (int i = 1; i <= n; i++) {
        int x, y;
        scanf("%lld%lld", &x, &y);
        sum += abs(x) + abs(y);  
        if (y >= 0)
            up++;
        if (y < 0)
            down++;
        if (x >= 0)
            _right++;
        if (x < 0)
            _left++;
        x = _hash(x), y = _hash(y);
        sumx[x]++; //更新横坐标为 x 的控制点个数 
        sumy[y]++;// 更新纵坐标为 y 的控制点个数 
    }
    cin >> opt;
    x = 0, y = 0;
    for (int j = 0; j < m; j++) {
        if (opt[j] == 'S') {
            sum += (down + sumy[_hash(y)]);
            sum -= (up - sumy[_hash(y)]);
            down += sumy[_hash(y)];
            up -= sumy[_hash(y)];
            y++;//更新位置 
        }
        if (opt[j] == 'J') {
            sum += up;
            sum -= down;
            y--;//更新位置 
            down -= sumy[_hash(y)];
            up += sumy[_hash(y)];
        }
        if (opt[j] == 'I') {
            sum += (_left + sumx[_hash(x)]);
            sum -= (_right - sumx[_hash(x)]);
            _right -= sumx[_hash(x)];
            _left += sumx[_hash(x)];
            x++;//更新位置 
        }
        if (opt[j] == 'Z') {
            sum += _right;
            sum -= _left;
            x--;//更新位置 
            _left -= sumx[_hash(x)];
            _right += sumx[_hash(x)];
        }
        cout << sum << endl;
    }
}