【Codeforces 331D3】Escaping on Beaveractor
2021-06-05 23:07
标签：方向 max dir 就是 actor 需要 code 另一个 查询 题意：给\(b\times b\)的网格，其中有\(n\)个不交叉的箭头。 现在有\(q\)个询问，每个询问包含一个点\((x,y)\)，以及一个方向\(dir\)、时间\(t\)。 要求从\((x,y)\)开始沿\(dir\)方向走\(t\)秒，每秒前进一格，到了箭头上就把方向改为箭头的方向。 问最后会到哪里。如果会走出网格的话就输出最后一个在网格内的点。 思路：线段树+倍增。 先想一个naive的做法。 我们先naive地求出每一个点下一步会朝向那个方向， 然后倍增地搞从某个点走多少步会到哪里。 那么这个是\(O(b^2\ log\ t)\)的。 下面来考虑优化。 首先发现我们肯定不用把所有的点都拎出来。 我们只需要可能会用到的点。 首先每一个箭头的尾端肯定会用到。 从尾端、询问点走出去碰到的第一个在箭头上的点肯定会用到。 其它的就不用了。 给一堆点和一堆方向，求从它们走出去会碰到箭头上的哪一点。 那分方向讨论后就变成一个区间赋最大值，单点求值的问题。 果断zkw线段树优化。但是分方向讨论好难写啊qwq 那么后面就倍增从某个点开始走几条边（边就是碰到另一个可能会用到的点）之后到了那个点，需要多少时间。 然后就是这里爆long long了，\((1！\(wa43\)了半天。 那么查询的时候倍增完最后直接沿着那时的方向再走一点就好了。 【Codeforces 331D3】Escaping on Beaveractor 标签：方向 max dir 就是 actor 需要 code 另一个 查询 原文地址：https://www.cnblogs.com/denverjin/p/10793589.html
那么我们现在要求的是一堆这样的询问：
文章标题：【Codeforces 331D3】Escaping on Beaveractor
文章链接：http://soscw.com/essay/91021.html