专栏文章

题解：CF1902D Robot Queries

CCharllote_
CF1902D题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@minhcabc
此快照首次捕获于
2025/12/02 02:25
3 个月前
此快照最后确认于
2025/12/02 02:25
3 个月前
查看原文
题目传送门
更好的阅读体验

前置知识——向量的加减

(x1,y1)±(x2,y2)=(x1±x2,y1±y2)(x_1,y_1) \pm (x_2,y_2) = (x_1\pm x_2,y_1\pm y_2)。
满足交换律和结合律。

题目大意

有一个在 (0,0)(0,0) 的点。现在给出 nn 个操作序列 f{f}，每个指令形如 (x,y)←{(x±1,y)(x,y±1)(x, y) \gets \left\{\begin{matrix}(x \pm 1, y) \\(x, y \pm 1)\end{matrix}\right.。现在又有 qq 个互相独立的询问，每个询问为反转 al∼ara_l\sim a_r，给出 (x,y)(x, y) 是否被点经过。

思路

一、操作序列等价于一组向量：{(±1,0),(0,±1)}\{(\pm 1,0),(0,\pm 1)\}。对于每一个询问，等价于询问反转后的操作序列 b{b} 是否有 (x,y)=∑i−1nbi(x, y) = \sum_{i - 1}^n b_i。设 ai=∑j=1ifja_i = \sum_{j=1}^i f_j。
二、由向量加法满足交换律容易得到 ∀p∈[1,l)∪[r,n],ap不变\forall p\in[1,l)\cup[r,n], a_p \text{不变}。所以其中一种合法情况为 aia_i 等于 (x,y)(x, y) 且 ∀p∈[1,l)∪[r,n]\forall p\in[1,l)\cup[r,n]。
三、由找规律可得，反转一段区间等价于将这一段的路径 {b}\{b\} 旋转 180∘180^{\circ} 再把 b{b} 的起点平移到 al−1a_{l-1}。所以另外一种合法情况为 al−1+ar−(x,y)=bpa_{l - 1} + a_r - (x, y) = b_p 且 ∀p∈[l,r)\forall p \in [l, r)。

实现

使用一个 map<PII, vector<int>> mp 维护 b=aib = a_i 的 ii。对于第一种情况，直接判断 mp[{x, y}] 中是否有 p∈[1,l)∪[r,n]p\in[1,l)\cup[r,n] 即可。对于第二种情况，判断 mp[add(add(re(p), a[l - 1]), a[r])] 中是否有 p∈[l,r)p\in[l,r) 即可。判断可以使用二分。

code

CPP
#include <bits/stdc++.h>
 
#pragma GCC optimize("Ofast")
 
#define int long long
 
using namespace std;
 
const int N = 2e5 + 5;
 
using PII = pair<int, int>;
 
int n, q, x, y, l, r;
PII a[N];
map<PII, vector<int>> mp;
 
PII add(PII x, PII y) {
    return {x.first + y.first, x.second + y.second};
}
PII re(PII x) {
    return {-x.first, -x.second};
}
bool check(vector<int> &v, int l, int r) {
    auto it = lower_bound(v.begin(), v.end(), l);
    if (it == v.end()) return false;
    return *it <= r;
}
 
signed main() {
    cin.tie(0)->sync_with_stdio(0);
    cin >> n >> q;
    mp[{0, 0}].push_back(0);
    for (int i = 1; i <= n; i ++ ) {
        char ch;    cin >> ch;
        if (ch =='U') {     a[i] = add(a[i - 1], {0, 1}); } 
        else if (ch =='D') {a[i] = add(a[i - 1], {0, -1});}
        else if (ch =='L') {a[i] = add(a[i - 1], {-1, 0});}
        else if (ch =='R') {a[i] = add(a[i - 1], {1, 0});}
        mp[a[i]].push_back(i);
    }
 
    while (q -- ) {
        cin >> x >> y >> l >> r;
 
        PII p = {x, y};
        if (mp.count(p) && (check(mp[p], 0, l - 1) || check(mp[p], r, n))) {
            cout << "YES\n";
            continue;
        }

        PII finded = add(add(re(p), a[l - 1]), a[r]);
        if (mp.count(finded) && check(mp[finded], l, r - 1)) {
            cout << "YES\n";
            continue;
        }
        cout << "NO\n";
    }
    return 0;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...