XXI Open Cup Grand Prix of Korea J.Remote Control @ Wings            分类 ACM
发布于 星期六, 九月 11 日, 2021 年
更新于 星期六, 九月 11 日, 2021 年

题目

题意

无穷大的二位网格平面上, $(0, 0)$ 处有一个障碍物. 现在有一个由 R, L, U, D 组成的长度为 $n$ 的操作序列和一个机器人. 操作序列表示控制机器人如何走(上下左右), 如果机器人的下一步是障碍物(即原点), 那么他不行动. 现在有 $Q$ 次询问, 每次询问给出机器人的起点, 问终点. 保证机器人不在 $(0, 0)$.

$1 \le n, q \le 3 \cdot 10^5$

题解

jyz nb!

不要被"一个“给误导了, 把所有询问都放在图上, 然后同时开始执行操作, 想象一下, 是不是有种"背景在动"的感觉? 没错, 这就是**“相对运动”**. 与其操作 $Q$ 个机器人, 不如反向操作一个障碍物. 假设在障碍物移动的过程中, 没有碰到任何机器人, 那么障碍物移动的轨迹反一下, 就是所有机器人移动的轨迹了. 障碍物移动的轨迹可以通过二位向量前缀和求得. 统计答案每个机器人起点对它做差即可. 于是, 对于障碍物移动过程中碰到的机器人, 我们想办法改变机器人的起点, 使得其终点不变, 但不再碰见障碍物. 这是好办的, 因为障碍物碰见机器人了的话, 就证明机器人在这个时候会去撞障碍物(相对运动), 那么让机器人"后退"一步, 再执行这个操作, 后续操作是一模一样的. 所以做法就是, 相对运动移动障碍物, 碰到机器人就"推"一下. 需要注意的是, 障碍物移动一下最多推 $n$ 个机器人, 但是这些机器人在后续操作中就等价了, 所以只用搞一个代表出来就行, 用并查集合并一下即可.

复杂度 $O(\alpha n)$

代码
int fa[MAXN];

void init(int n) {
  for (int i = 1; i <= n; i++) fa[i] = i;
}

int find(int x) {
  return x == fa[x] ? x : fa[x] = find(fa[x]);
}

bool uni(int x, int y) {
  if (find(x) == find(y))
    return false;
  fa[find(x)] = find(y);
  return true;
}

struct Vec {
  int x, y;
  Vec operator + (const Vec &B) const { return Vec{x + B.x, y + B.y}; }
  Vec operator - (const Vec &B) const { return Vec{x - B.x, y - B.y}; }
  bool operator == (const Vec &B) const {
    return x == B.x && y == B.y;
  }
  bool operator < (const Vec &V) const {
    return x == V.x ? y < V.y : x < V.x;
  }
} d[256], ans[MAXN];

map<Vec, int> mp;
int n, q;
char str[MAXN];

int main() {
  d['U'] = {0, 1};
  d['D'] = {0, -1};
  d['L'] = {-1, 0};
  d['R'] = {1, 0};
  scanf("%d%s%d", &n, str, &q);
  init(q);
  for (int i = 1; i <= q; i++) {
    Vec cur;
    scanf("%d%d", &cur.x, &cur.y);
    if (mp[cur])
      uni(i, mp[cur]);
    else
      mp[cur] = i;
  }
  Vec cur = {0, 0};
  for (int i = 0; str[i]; i++) {
    cur = cur - d[str[i]];
    if (mp[cur]) {
      Vec nxt = cur - d[str[i]];
      if (mp[nxt])
        uni(mp[cur], mp[nxt]);
      else
        mp[nxt] = mp[cur];
      mp.erase(cur);
    }
  }
  for (auto [v, i] : mp)
    ans[i] = v - cur;
  for (int i = 1; i <= q; i++)
    printf("%d %d\n", ans[find(i)].x, ans[find(i)].y);
  return 0;
}
留下昵称和邮箱, 可在第一时间获悉回复通知哦~

2021 FLAG

  • 找个妹子
  • 进计科
  • XCPC拿块金牌
  • 补全算法知识, 整全板子
  • 学会Web开发相关知识
  • 在服务器上搭建电子书库
  • 写个游戏并上线
  • 能弹一首曲子
  • 写首完整的曲子
  • 练习悠悠球

个人简介

我叫 Wings, 来自江西上饶, 目前人在西安, 是西电的一名学生.

常以 WingsWingsZengWingsWings的ID在各大小网站上游走, 一般来说, Wings不是我 😔, WingsZeng 一定是我 😊.

热爱算法, 喜欢钻研各种计算机技术.

业余爱好广泛, 只要不是文化课基本上都感兴趣😏.

开发/项目经历

  1. Android游戏 小墨滴的复仇 (弃坑)
  2. Android游戏 Circle Run (弃坑)
  3. Windows游戏 Snague (可能弃坑了吧)
  4. Python后端 Fathy' (可能弃坑了吧)

to be continued

教育经历

时间 学历 学校
2008-2014 小学 上饶市第十二小学
2014-2017 初中 上饶市第四中学
2017-2020 高中 上饶市第一中学
2020-2024 本科 西安电子科技大学
to be continued

比赛/竞赛经历

太久远太小的记不到了…

  1. 2017 国学竞赛初赛江西 没有分数或排名 二乙
  2. 2018 NOIP提高 258 省二
  3. 2019 CSP-S江西专场 145 省二
  4. 2019 数学竞赛初赛 70 没排名 (复赛打铁qaq)
  5. 2020 Gitee|Python贪吃蛇魔改大赛 可能是第四? 二等奖
  6. 2020 西电ACM训练基地熊猫杯 第四 银牌
  7. 2020 西安三校微软学生俱乐部Hackathon 和二等奖最后一名差0.5分 三等奖
  8. 2020 西电星火杯 三等奖
  9. 2020 西电ACM新生赛 第九 金牌
  10. 2020 ICPC 亚洲区域赛 济南站 132名 铜牌
  11. 2020-2021 第二届全国大学生算法设计与编程挑战赛(冬季赛) 924名 铜牌 (别骂了别骂了)
  12. 2020 ICPC 亚洲区域赛 昆明站 打星
  13. 2020 ICPC Asia-East Continent Final 签完到溜 打铁
  14. 西电"智能星"第一届自动驾驶小车比赛 第五 优胜奖|极速奖 本来可以冠军的别骂了别骂了

to be continued

爱好

技术

  • 算法
  • 独立游戏开发

游戏

  • Minecraft
  • Black Survival
  • I Wanna
  • Celeste
  • Life is Strange
  • Need for speed

运动

  • 篮球
  • 桌球
  • 乒乓球
  • 羽毛球
  • 慢跑

音乐

  • 吉他
  • 词曲
  • 流行

玩具

  • 魔方
    • 三阶速拧
    • 三阶盲拧
    • 高阶
  • yoyo球

追星

  • VAE
  • Benedict Cumberbatch