当前位置:首页 > 单调队列 > 正文
洛谷7116P7116微信步数(NOIP2020)
684+

题目大意:已知走法,共n步,每一步在某一维度的坐标增加1,需要多少步才走出规定范围?共有m个维度,请每个位置开始走,直到走出去位置,共走多少步?

题目描述

小 C 喜欢跑步,并且非常喜欢在微信步数排行榜上刷榜,为此他制定了一个刷微信步数的计划。

他来到了一处空旷的场地,处于该场地中的人可以用 维整数坐标 来表示其位置。场地有大小限制,第 维的大小为 ,因此处于场地中的人其坐标应满足 )。

小 C 打算在接下来的 天中,每天从场地中一个新的位置出发,开始他的刷步数计划(换句话说,他将会从场地中每个位置都出发一次进行计划)。

他的计划非常简单,每天按照事先规定好的路线行进,每天的路线由 步移动构成,每一步可以用 表示:若他当前位于 ,则这一步他将会走到 ,其中 。小 C 将会不断重复这个路线,直到他走出了场地的范围才结束一天的计划。(即走完第 步后,若小 C 还在场内,他将回到第 步从头再走一遍)。

小 C 对自己的速度非常有自信,所以他并不在意具体耗费的时间,他只想知道 天之后,他一共刷出了多少步微信步数。请你帮他算一算。

输入格式

第一行两个用单个空格分隔的整数 。分别表示路线步数与场地维数。
接下来一行 个用单个空格分隔的整数 ,表示场地大小。
接下来 行每行两个用单个空格分隔的整数 ,依次表示每一步的方向,具体意义见题目描述。

输出格式

仅一行一个整数表示答案。答案可能很大,你只需要输出其对 取模后的值。
若小 C 的计划会使得他在某一天在场地中永远走不出来,则输出一行一个整数

输入输出样例

输入 #1
3 2
3 3
1 1
2 -1
1 1
输出 #1
21
输入 #2
5 4
6 8 6 5
3 1
2 1
1 1
2 1
2 -1
输出 #2
10265
输入 #3
见附件中的 walk/walk3.in
输出 #3
见附件中的 walk/walk3.ans
输入 #4
见附件中的 walk/walk4.in
输出 #4
见附件中的 walk/walk4.ans

说明/提示

【样例 #1 解释】

出发将走 步,从 出发将走 步,从 出发将走 步。
出发将走 步,从 出发将走 步,从 出发将走 步。
出发将走 步,从 出发将走 步,从 出发将走 步。
共计 步。

【数据范围】

测试点编号

对于所有测试点,保证

解题思路

暴力30:枚举起点,暴力走出去即可,如果走不出去,那么步数比如超过1111,因为该维每个位置都走过了,如果n步能往右一点点或者往左一点点,再走n步必能走出去,走不出去的话,就是死循环。

逐维处理65:只有一维的情况告诉我们,可以分开处理每一维。首先,如果是一维,那么每个位置需要走多少步呢?求出来后累计求和即可。怎么求?要么n步以内解决,要么超过n步。n步以内,需要的步数不超过n,我们可以预处理往左往右走n步的最小操作次数(步数),后面就可以O(1)查询。超过n步,那么n步之后,位置到达哪里,至少经过多少轮之后,下一轮必能走出去?假设这一轮过后,往右走了s步,这一轮中,至多往右走x步。对于往右走的情况,能走出去,那么至少走到w+1-x这个位置,需要w+1-x除以s轮,向上取整即可。往左走同理,至少注意s是负的,向上取整、除的时候要转成正数。对于多维的情况,什么时候是这一维的步数先走出去呢?其他维的步数要大于这一维才行!每一维有多少个,乘起来就是方案数,再乘以步数就是即可。排序后二分查找第一个大于的位置,即可快速解决问题。

注意1:各维走出去的步数,一定不相同,因为每一步只操作一维。

注意2:因为要比较大小,所以预处理的时候,每个位置所需步数不能取模,最大值为n*w,超过即无穷大。

单调性80:排序有个log,二分查找有个log,可以利用单调性去掉。如果是往左走出去的,那么越靠右所需步数越多;如果是往右走出去的,那么越靠右步数越少。我们可以分别把往左、往右的步数放入两个单调队列d和q,再合并他们。对于查找第一个大于的位置,可以利用尺取法。

程序实现

暴力30,没特判-1,时间复杂度$O(w^k*n*w)$

逐维处理65,时间复杂度$O(w*k*k*log_2w)$

单调性80,时间复杂度$O(k*k*w)$

洛谷7116P7116微信步数(NOIP2020):等您坐沙发呢!

发表评论

😉😐😡😈🙂😯🙁🙄😛😳😮mrgreen.png😆💡😀👿😥😎😕

快捷键:Ctrl+Enter