• 微信公众号:美女很有趣。 工作之余,放松一下,关注即送10G+美女照片!

CCPC网络选拔赛Round2 Monopoly 题解

开发技术 开发技术 5小时前 1次浏览

题意

你有一个长度为(n)的序列(a),你的起始分数为(0),你第一次跳跃会从(0)(1),然后接下来你每次跳跃都会从(i)号点跳跃到(i+1)号点,特殊的,如果你在(n)号点,那么你的下一个点就是(1)号点,你每到达一个点一次,那么你就能获得这个点的值(a_i),现在给你(m)次询问每次询问给你一个(x),问你要获得(x)的得分只要要跳跃几次

分析

开始的时候想的是发现一个显然的结论,最后你一定会走若干圈然后停在某个点上,那么你最后要得到的就是某个前缀和加上若干圈,但是当时发现每一圈的值(S)可能会小于(0),因此圈数并没有单调性,所以就放弃了这个思路。但是如果分(S>0)的情况讨论的话,我们可以发现当(S)大于(0)时,走的圈数越多,最后的值一定就越大,那么我们的得分就是(s_j+k times S),发现(s_j+k times S = x)等价于(s_jequiv x pmod{S}),所以我们要找到一个(s_j)使得(sj)(x)在膜(S)下同余并且(s_j leq x),所以我们就可以预处理出所有的前缀和,然后把所有的前缀和按照膜(S)分类,然后再在和(x)同余的所有(s)中找到一个小于(x)的并且下标最小的,然后答案就是(j+(x-s_j/S)).
然后对于(S<0)的情况,我们把所有数字取反,再把要查询的(x)也取反即可(我当时咋就没想到。。。

代码

代码好难写,先咕了(

心得

当时不只是没有考虑到把(S)分情况讨论,而且也没有考虑到当(S>0)时,要找的是小于(x)(s_j)wi(估计想到了也不会写代码),感觉以后还是要多做这种与数学结合起来的题


程序员灯塔
转载请注明原文链接:CCPC网络选拔赛Round2 Monopoly 题解
喜欢 (0)