AT_abc421_d [ABC421D] RLE Moving

· · 题解

只能说这个 D 难度不高，但是要点耐心。

赛时快速切了。

\texttt{solution}

首先考虑逐秒模拟两人的行动，发现这样显然超时。

发现 m 和 l 并不大，所以可以一段一段的模拟，使用两个指针维护两人现在分别处于哪一段行动区间内。

怎么统计答案呢？

其实我们并不关心两人最初的坐标位置，只关心相对坐标差，那么我们可以计算两人所处的两段区间的行动方向对两人相对位置差的贡献，然后分类讨论即可，详见代码。

\texttt{Code}

复杂度是显然不会超时的，分讨细节注意一下就行了。

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
int rt, ct, ra, ca;
int n, m, l;
typedef pair <char, int> pci;
typedef pair <int, int> pii;
vector <pci> s, t;
pii getsss(char c) { // 处理出每个方向对相对坐标差的贡献
    if(c == 'U') {
        return {-1, 0};
    }
    if(c == 'D') {
        return {1, 0};
    }
    if(c == 'L') {
        return {0, -1};
    }
    return {0, 1};
}
pii operator - (pii a, pii b) {
    pii c;
    c.first = a.first - b.first;
    c.second = a.second - b.second;
    return c;
}
int delr, delc;
int ans;
signed main(void) {
    ios :: sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> rt >> ct >> ra >> ca;
    cin >> n >> m >> l;
    s.push_back({'!', 0});
    t.push_back({'!', 0});
    for (int i = 1; i <= m; i ++) {
        char c;
        int k;
        cin >> c >> k;
        s.push_back({c, k});
    }
    for (int i = 1; i <= l; i ++) {
        char c;
        int k;
        cin >> c >> k;
        t.push_back({c, k});
    }
    int nows, nowt;
    nows = nowt = 1; // 两个指针维护当前所在段
    delr = rt - ra, delc = ct - ca; // 相对坐标差
    while (nows <= m && nowt <= l) {
        int len = min(s[nows].second, t[nowt].second); // 取两段中长度较小的段，那么在这个长度为 len 的段内两人都不会改变行动方向
        auto ways = getsss(s[nows].first), wayt = getsss(t[nowt].first);
        auto del = ways - wayt;
        int ndelr = del.first, ndelc = del.second; // 分别表示两人在一次行动内对相对横坐标差和相对纵坐标差的贡献
        if(ndelr == 0 && ndelc == 0) { // 两人行动方向相同
            if(delr == 0 && delc == 0) { // 两人原来就在同一个点上了，注意不要写成 delr + delc == 0，因为会有负数
                ans += len; // 这一整段两人都在同一个格子上
            }
        }
        else if(!ndelr) { // 两人横坐标差为零
            if(!delr) { // 这一段中横坐标没有相对的变化
                int invol = delc;
                if(invol % ndelc == 0) { // 如果能够一步一步凑到 delc
                    int chu = invol / ndelc;
                    chu = -chu; // 因为是要补原来的坐标差，所以两者应当正负相反，可以直接 invol = -invol，会好理解一点
                    if(chu > 0 && chu <= len) ans ++; // 如果小于零就说明这一段只会让差距越来越大，大于 len 就无法在这个区间内实现，这里请读者思考一下
                }
            }
        }
        else if(!ndelc) { // 同上
            if(!delc) {
                int invol = delr;
                if(invol % ndelr == 0) {
                    int chu = invol / ndelr;
                    chu = -chu;
                    if(chu > 0 && chu <= len) ans ++;
                }
            }
        }
        else { // 否则就是两个坐标同时凑
            if(ndelc * delr == ndelr * delc) {
                int invol1 = delr, invol2 = delc;
                if(invol1 % ndelr == 0 && invol2 % ndelc == 0) { // 必须都整除才行
                    int chu = invol1 / ndelr;
                    chu = -chu;
                    if(chu > 0 && chu <= len) ans ++;
                }
            }
        }
        delr += len * ndelr;
        delc += len * ndelc; // 改变坐标差
        s[nows].second -= len;
        t[nowt].second -= len;
        if(s[nows].second <= 0) nows ++; // 这一段走完了，移动指针
        if(t[nowt].second <= 0) nowt ++;
    }
    cout << ans;
    return 0;
}