题解：AT_abc421_d [ABC421D] RLE Moving

· · 题解

赛时最后三秒切掉！

为什么现在才写题解，因为我敢肯定题解不会满。

思路

我们拆解一下问题，题目要使得两个人的位置一样，那么可以转化成要使得两人的横坐标和纵坐标的差都是 0。

我们可以先一开始求出来两个人的横坐标和纵坐标的差，然后我们再用两个变量记录第一个人当前这一次的剩余移动次数和第二个人当前这一次的剩余移动次数。

然后我们同时遍历两个序列，看一下，求出两个人这一次移动一次位置差的变化的值，也用两个变量来存储，然后我们要分四种情况讨论：

  1. 种是当前位置不变。

  2. 是横坐标不变。

  3. 是纵坐标不变。

  4. 是横坐标和纵坐标都变了。

在这过程中，我们就要顺便更新答案，因为如果这一次可以移动到同一个位置，那么就只能移动到同一个位置一次而已，就是往同一个方向走，不可能多次经过同一个位置。

处理好了之后，我们就要更新位置差的变化，用刚刚的计算结果乘 k 次来更新。但是这里的 k 并不是走的次数，而是第一个人当前这一次的剩余移动次数和第二个人当前这一次的剩余移动次数的最小值。最后统一更新即可。

代码

#include<bits/stdc++.h>
using namespace std;
#define int long long
int rt,ct,ra,ca,n,m,l,a;
vector<tuple<int,int,int>> s,t;
char c;
signed main(){
    cin >> rt >> ct >> ra >> ca >> n >> m >> l;
    for (int i = 1;i <= m;i++){
        cin >> c >> a;
        if (c == 'U') s.emplace_back(-1,0,a);
        if (c == 'D') s.emplace_back(1,0,a);
        if (c == 'L') s.emplace_back(0,-1,a);
        if (c == 'R') s.emplace_back(0,1,a);
    }
    for (int i = 1;i <= l;i++){
        cin >> c >> a;
        if (c == 'U') t.emplace_back(-1,0,a);
        if (c == 'D') t.emplace_back(1,0,a);
        if (c == 'L') t.emplace_back(0,-1,a);
        if (c == 'R') t.emplace_back(0,1,a);
    }
    int ans = 0,dx = rt - ra,dy = ct - ca,i = 0,j = 0,sr = get<2>(s[0]),tr = get<2>(t[0]);
    while (i < m && j < l){
        int k = min(sr,tr);
        auto [x,y,_] = s[i];
        auto [xx,yy,__] = t[j];
        int xxx = x - xx,yyy = y - yy,x0 = dx,y0 = dy;
        if (xxx == 0 && yyy == 0){
            if (x0 == 0 && y0 == 0) ans += k;
        } else if (xxx == 0){
            if (x0 == 0 && (-y0) % yyy == 0){
                int tv = (-y0) / yyy;
                if (tv >= 1 && tv <= k) ans++;
            }
        } else if (yyy == 0){
            if (y0 == 0 && (-x0) % xxx == 0){
                int tv = (-x0) / xxx;
                if (tv >= 1 && tv <= k) ans++;
            }
        } else {
            bool ok1 = (-x0) % xxx == 0,ok2 = (-y0) % yyy == 0;
            if (ok1 && ok2){
                int tv = (-x0) / xxx,tu = (-y0) / yyy;
                if (tv == tu && tv >= 1 && tv <= k) ans++;
            }
        }
        dx += xxx * k,dy += yyy * k,sr -= k,tr -= k;
        if (!sr && ++i < m) sr = get<2>(s[i]);
        if (!tr && ++j < l) tr = get<2>(t[j]);
    }
    cout << ans << endl;
}